Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called "Ring Buffer".
One of the benefits of the circular queue is that we can make use of the spaces in front of the queue. In a normal queue, once the queue becomes full, we cannot insert the next element even if there is a space in front of the queue. But using the circular queue, we can use the space to store new values.
Your implementation should support following operations:
MyCircularQueue(k): Constructor, set the size of the queue to be k.
Front: Get the front item from the queue. If the queue is empty, return -1.
Rear: Get the last item from the queue. If the queue is empty, return -1.
enQueue(value): Insert an element into the circular queue. Return true if the operation is successful.
deQueue(): Delete an element from the circular queue. Return true if the operation is successful.
isEmpty(): Checks whether the circular queue is empty or not.
isFull(): Checks whether the circular queue is full or not.
Example
MyCircularQueue circularQueue = new MyCircularQueue(3); // set the size to be 3
circularQueue.enQueue(1); // return true
circularQueue.enQueue(2); // return true
circularQueue.enQueue(3); // return true
circularQueue.enQueue(4); // return false, the queue is full
circularQueue.Rear(); // return 3
circularQueue.isFull(); // return true
circularQueue.deQueue(); // return true
circularQueue.enQueue(4); // return true
circularQueue.Rear(); // return 4
Note
本质有点类似双端队列,所以可以用数组实现或者链表实现
注意一下特殊情况,比如deQueue的时候,如果是最后一个元素,front和rear都要设为-1
Code
class MyCircularQueue {
final int[] a;
int front, rear = -1, len = 0;
public MyCircularQueue(int k) { a = new int[k];}
public boolean enQueue(int val) {
if (!isFull()) {
rear = (rear + 1) % a.length;
a[rear] = val;
len++;
return true;
} else return false;
}
public boolean deQueue() {
if (!isEmpty()) {
front = (front + 1) % a.length;
len--;
return true;
} else return false;
}
public int Front() { return isEmpty() ? -1 : a[front];}
public int Rear() {return isEmpty() ? -1 : a[rear];}
public boolean isEmpty() { return len == 0;}
public boolean isFull() { return len == a.length;}
}
classMyCircularQueue {LinkedList<Integer> q;int cap;int front =-1;int rear =-1; /** Initialize your data structure here. Set the size of the queue to be k. */publicMyCircularQueue(int k) {this.cap= k;this.q=newLinkedList<>(); } /** Insert an element into the circular queue. Return true if the operation is successful. */publicbooleanenQueue(int value) {if (isFull()) {returnfalse; }if (isEmpty()) { front = value; }q.add(value); rear = value;returntrue; } /** Delete an element from the circular queue. Return true if the operation is successful. */publicbooleandeQueue() {if (isEmpty()) {returnfalse; }q.removeFirst();if (isEmpty()) { front =-1; rear =-1; } else { front =q.get(0); }returntrue; } /** Get the front item from the queue. */publicintFront() {return front; } /** Get the last item from the queue. */publicintRear() {return rear; } /** Checks whether the circular queue is empty or not. */publicbooleanisEmpty() {return q ==null||q.size() ==0; } /** Checks whether the circular queue is full or not. */publicbooleanisFull() {returnq.size() == cap; }}