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