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 {
constructor(k) {
this.k = k;
this.queue = new Array(k);
this.head = 0;
this.tail = -1;
this.size = 0;
}
enQueue(value) {
if (this.isFull()) return false;
this.tail = (this.tail + 1) % this.k;
this.queue[this.tail] = value;
this.size++;
return true;
}
deQueue() {
if (this.isEmpty()) return false;
this.head = (this.head + 1) % this.k;
this.size--;
return true;
}
Front() {
if (this.isEmpty()) return -1;
return this.queue[this.head];
}
Rear() {
if (this.isEmpty()) return -1;
return this.queue[this.tail];
}
isEmpty() {
return this.size === 0;
}
isFull() {
return this.size === this.k;
}
}
Follow-up:
How would you implement a dynamic circular queue that can resize itself when it becomes full?
