class MyCircularDeque:
def __init__(self, k: int):
self.k = k
self.deque = [0] * k
self.front = 0
self.rear = 0
self.size = 0
def insertFront(self, value: int) -> bool:
if self.isFull():
return False
self.front = (self.front - 1 + self.k) % self.k
self.deque[self.front] = value
self.size += 1
return True
def insertLast(self, value: int) -> bool:
if self.isFull():
return False
self.deque[self.rear] = value
self.rear = (self.rear + 1) % self.k
self.size += 1
return True
def deleteFront(self) -> bool:
if self.isEmpty():
return False
self.front = (self.front + 1) % self.k
self.size -= 1
return True
def deleteLast(self) -> bool:
if self.isEmpty():
return False
self.rear = (self.rear - 1 + self.k) % self.k
self.size -= 1
return True
def getFront(self) -> int:
if self.isEmpty():
return -1
return self.deque[self.front]
def getRear(self) -> int:
if self.isEmpty():
return -1
return self.deque[(self.rear - 1 + self.k) % self.k]
def isEmpty(self) -> bool:
return self.size == 0
def isFull(self) -> bool:
return self.size == self.k
class MyCircularDeque {
public:
MyCircularDeque(int k) {
deque.resize(k);
this->k = k;
front = 0;
rear = 0;
size = 0;
}
bool insertFront(int value) {
if (isFull()) return false;
front = (front - 1 + k) % k;
deque[front] = value;
size++;
return true;
}
bool insertLast(int value) {
if (isFull()) return false;
deque[rear] = value;
rear = (rear + 1) % k;
size++;
return true;
}
bool deleteFront() {
if (isEmpty()) return false;
front = (front + 1) % k;
size--;
return true;
}
bool deleteLast() {
if (isEmpty()) return false;
rear = (rear - 1 + k) % k;
size--;
return true;
}
int getFront() {
if (isEmpty()) return -1;
return deque[front];
}
int getRear() {
if (isEmpty()) return -1;
return deque[(rear - 1 + k) % k];
}
bool isEmpty() {
return size == 0;
}
bool isFull() {
return size == k;
}
private:
vector<int> deque;
int k, front, rear, size;
};
class MyCircularDeque {
private int[] deque;
private int front, rear, size, k;
public MyCircularDeque(int k) {
this.k = k;
deque = new int[k];
front = 0;
rear = 0;
size = 0;
}
public boolean insertFront(int value) {
if (isFull()) return false;
front = (front - 1 + k) % k;
deque[front] = value;
size++;
return true;
}
public boolean insertLast(int value) {
if (isFull()) return false;
deque[rear] = value;
rear = (rear + 1) % k;
size++;
return true;
}
public boolean deleteFront() {
if (isEmpty()) return false;
front = (front + 1) % k;
size--;
return true;
}
public boolean deleteLast() {
if (isEmpty()) return false;
rear = (rear - 1 + k) % k;
size--;
return true;
}
public int getFront() {
if (isEmpty()) return -1;
return deque[front];
}
public int getRear() {
if (isEmpty()) return -1;
return deque[(rear - 1 + k) % k];
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == k;
}
}
var MyCircularDeque = function(k) {
this.k = k;
this.deque = new Array(k);
this.front = 0;
this.rear = 0;
this.size = 0;
};
MyCircularDeque.prototype.insertFront = function(value) {
if (this.isFull()) return false;
this.front = (this.front - 1 + this.k) % this.k;
this.deque[this.front] = value;
this.size++;
return true;
};
MyCircularDeque.prototype.insertLast = function(value) {
if (this.isFull()) return false;
this.deque[this.rear] = value;
this.rear = (this.rear + 1) % this.k;
this.size++;
return true;
};
MyCircularDeque.prototype.deleteFront = function() {
if (this.isEmpty()) return false;
this.front = (this.front + 1) % this.k;
this.size--;
return true;
};
MyCircularDeque.prototype.deleteLast = function() {
if (this.isEmpty()) return false;
this.rear = (this.rear - 1 + this.k) % this.k;
this.size--;
return true;
};
MyCircularDeque.prototype.getFront = function() {
if (this.isEmpty()) return -1;
return this.deque[this.front];
};
MyCircularDeque.prototype.getRear = function() {
if (this.isEmpty()) return -1;
return this.deque[(this.rear - 1 + this.k) % this.k];
};
MyCircularDeque.prototype.isEmpty = function() {
return this.size === 0;
};
MyCircularDeque.prototype.isFull = function() {
return this.size === this.k;
};
You are asked to design and implement a circular double-ended queue (deque) with a fixed capacity k. The deque should support the following operations:
insertFront(value): Adds an item at the front. Returns true if successful, false if full.insertLast(value): Adds an item at the rear. Returns true if successful, false if full.deleteFront(): Deletes the front item. Returns true if successful, false if empty.deleteLast(): Deletes the last item. Returns true if successful, false if empty.getFront(): Returns the front item, or -1 if empty.getRear(): Returns the last item, or -1 if empty.isEmpty(): Returns true if the deque is empty.isFull(): Returns true if the deque is full.
The implementation must use only k spaces, and all operations must be efficient. The data structure should behave like a ring buffer: when you reach the end, you wrap around to the beginning.
At first, it might be tempting to use a simple array or a built-in list to simulate the deque. However, inserting or deleting at the front of a normal array is not efficient because it requires shifting all elements. Since we need both ends to work efficiently, and the size is fixed, using a circular buffer (ring buffer) is the best approach.
The circular buffer idea means we use an array of size k and two pointers (or indices): front and rear. The trick is to manage these pointers so that they wrap around the array and always point to the correct positions for insertions and deletions. We also need to distinguish between the empty and full states, which can be tricky when the pointers overlap.
By keeping a separate size variable, we can easily check if the deque is empty (size == 0) or full (size == k), and avoid ambiguity.
k to store the elements.front: Points to the position of the current front element.rear: Points to the position where the next rear element will be inserted.size to track the current number of elements.front (wrapping if needed) and place the value there.rear, then increment rear (wrapping if needed).front (wrapping if needed).rear (wrapping if needed).getFront() returns the element at front if not empty.getRear() returns the element just before rear (wrapping if needed) if not empty.size == 0.size == k.All operations are O(1) because they only involve pointer arithmetic and array access.
Suppose k = 3 and we perform the following operations:
insertLast(1): rear moves to 1, array: [1, _, _], size: 1insertLast(2): rear moves to 2, array: [1, 2, _], size: 2insertFront(3): front moves to 2, array: [1, 2, 3], size: 3insertFront(4): fails, deque is fullgetRear(): returns 2 (at (rear-1)%3 = 1)isFull(): returns truedeleteLast(): rear moves to 1, size: 2insertFront(4): front moves to 1, array: [1, 4, 3], size: 3getFront(): returns 4 (at front = 1)
At each step, the front and rear pointers wrap around the array as needed, and the size variable ensures correctness for empty/full checks.
insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, isFull) are O(1) because they only involve index arithmetic and array access.
The "Design Circular Deque" problem is elegantly solved using a circular buffer (ring buffer) with two pointers and a size counter. This design ensures that all operations are performed in constant time and within the fixed space constraint. The key insight is managing the front and rear pointers with modular arithmetic to wrap around the array, and using a size variable to distinguish between empty and full states. This approach is both efficient and robust for implementing a double-ended queue with a fixed capacity.