Design Circular Queue
Design a circular queue with a fixed size.201Question and said but not limited to the following methods: enQueue(), deQueue(), Front(), Rear(), isEmpty(), isFull().
Constraints:
- 1 <= k <= 10000
- 0 <= value <= 10000
- At most 3000 operations will be performed.
Examples:
Input: MyCircularQueue k = new MyCircularQueue(3); k.enQueue(1); k.enQueue(2); k.enQueue(3); k.enQueue(4); k.Rear(); k.isFull(); k.deQueue(); k.enQueue(4); k.Rear();
Output: [null, null, null, null, 3, true, null, null, 4]
Explanation: The queue is initially empty. We add elements 1, 2, and 3. When we try to add 4, it fails because the queue is full. We then remove an element and add 4, which succeeds.
Solutions
Array-based implementation
We use an array to store the elements of the queue. The head and tail pointers are used to keep track of the front and rear of the queue. The size variable keeps track of the number of elements in the queue.
class MyCircularQueue {
private: int* data;
int head, tail, size, k;
public: MyCircularQueue(int k) {
data = new int[k];
this->k = k;
head = tail = size = 0;
}
bool enQueue(int value) {
if (isFull()) return false;
data[tail] = value;
tail = (tail + 1) % k;
size++;
return true;
}
bool deQueue() {
if (isEmpty()) return false;
head = (head + 1) % k;
size--;
return true;
}
int Front() {
if (isEmpty()) return -1;
return data[head];
}
int Rear() {
if (isEmpty()) return -1;
return data[(tail - 1 + k) % k];
}
bool isEmpty() {
return size == 0;
}
bool isFull() {
return size == k;
}Follow-up:
How would you implement a dynamic circular queue that can resize itself when it becomes full?
