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:
All values will be in the range of [0, 1000].
The number of operations will be in the range of [1, 1000].
Please do not use the built-in Queue library.
Analysis
Array 数组实现：
重点在于确定循环队列空和满的情况，以及确定下一个rear和front的下标位置。
设定一个 int length 可以记录当前queue的元素个数，和循环队列的大小比较就可以得到是否满，检查length是否为0，则检测队列是否为空。
class MyCircularQueue {
private int length;
private int rear, front;
private int[] q;
/** Initialize your data structure here. Set the size of the queue to be k. */
public MyCircularQueue(int k) {
q = new int[k];
length = 0;
front = 0;
rear = -1;
}
/** Insert an element into the circular queue. Return true if the operation is successful. */
public boolean enQueue(int value) {
if (isFull()) {
return false;
}
rear = (rear + 1) % (q.length);
q[rear] = value;
length++;
return true;
}
/** Delete an element from the circular queue. Return true if the operation is successful. */
public boolean deQueue() {
if (isEmpty()) {
return false;
}
front = (front + 1) % (q.length);
length--;
return true;
}
/** Get the front item from the queue. */
public int Front() {
return isEmpty() ? -1 : q[front];
}
/** Get the last item from the queue. */
public int Rear() {
return isEmpty() ? -1 : q[rear];
}
/** Checks whether the circular queue is empty or not. */
public boolean isEmpty() {
return length == 0;
}
/** Checks whether the circular queue is full or not. */
public boolean isFull() {
return length == q.length;
}
}
/**
* Your MyCircularQueue object will be instantiated and called as such:
* MyCircularQueue obj = new MyCircularQueue(k);
* boolean param_1 = obj.enQueue(value);
* boolean param_2 = obj.deQueue();
* int param_3 = obj.Front();
* int param_4 = obj.Rear();
* boolean param_5 = obj.isEmpty();
* boolean param_6 = obj.isFull();
*/
Array Implementation 2 - init front = 0, rear = 0
class MyCircularQueue {
private int length;
private int rear, front;
private int[] q;
/** Initialize your data structure here. Set the size of the queue to be k. */
public MyCircularQueue(int k) {
q = new int[k];
length = 0;
front = 0;
rear = 0;
}
/** Insert an element into the circular queue. Return true if the operation is successful. */
public boolean enQueue(int value) {
if (isFull()) {
return false;
}
q[rear] = value;
rear = (rear + 1) % (q.length);
length++;
return true;
}
/** Delete an element from the circular queue. Return true if the operation is successful. */
public boolean deQueue() {
if (isEmpty()) {
return false;
}
front = (front + 1) % (q.length);
length--;
return true;
}
/** Get the front item from the queue. */
public int Front() {
return isEmpty() ? -1 : q[front];
}
/** Get the last item from the queue. */
public int Rear() {
return isEmpty() ? -1 : q[(rear + q.length - 1) % q.length];
}
/** Checks whether the circular queue is empty or not. */
public boolean isEmpty() {
return length == 0;
}
/** Checks whether the circular queue is full or not. */
public boolean isFull() {
return length == q.length;
}
}
/**
* Your MyCircularQueue object will be instantiated and called as such:
* MyCircularQueue obj = new MyCircularQueue(k);
* boolean param_1 = obj.enQueue(value);
* boolean param_2 = obj.deQueue();
* int param_3 = obj.Front();
* int param_4 = obj.Rear();
* boolean param_5 = obj.isEmpty();
* boolean param_6 = obj.isFull();
*/
LeetCode Official Solution - Array Implementation
class MyCircularQueue {
private int[] data;
private int head;
private int tail;
private int size;
/** Initialize your data structure here. Set the size of the queue to be k. */
public MyCircularQueue(int k) {
data = new int[k];
head = -1;
tail = -1;
size = k;
}
/** Insert an element into the circular queue. Return true if the operation is successful. */
public boolean enQueue(int value) {
if (isFull() == true) {
return false;
}
if (isEmpty() == true) {
head = 0;
}
tail = (tail + 1) % size;
data[tail] = value;
return true;
}
/** Delete an element from the circular queue. Return true if the operation is successful. */
public boolean deQueue() {
if (isEmpty() == true) {
return false;
}
if (head == tail) {
head = -1;
tail = -1;
return true;
}
head = (head + 1) % size;
return true;
}
/** Get the front item from the queue. */
public int Front() {
if (isEmpty() == true) {
return -1;
}
return data[head];
}
/** Get the last item from the queue. */
public int Rear() {
if (isEmpty() == true) {
return -1;
}
return data[tail];
}
/** Checks whether the circular queue is empty or not. */
public boolean isEmpty() {
return head == -1;
}
/** Checks whether the circular queue is full or not. */
public boolean isFull() {
return ((tail + 1) % size) == head;
}
}
/**
* Your MyCircularQueue object will be instantiated and called as such:
* MyCircularQueue obj = new MyCircularQueue(k);
* boolean param_1 = obj.enQueue(value);
* boolean param_2 = obj.deQueue();
* int param_3 = obj.Front();
* int param_4 = obj.Rear();
* boolean param_5 = obj.isEmpty();
* boolean param_6 = obj.isFull();
*/
Using (Doubly) Linked List
class ListNode {
int val;
ListNode prev, next;
public ListNode(int x) {
val = x;
prev = null;
next = null;
}
}
class MyCircularQueue {
int queueSize, currSize;
ListNode head, tail;
/** Initialize your data structure here. Set the size of the queue to be k. */
public MyCircularQueue(int k) {
queueSize = k;
currSize = 0;
head = new ListNode(-1);
tail = new ListNode(-1);
head.next = tail;
tail.prev = head;
}
/** Insert an element into the circular queue. Return true if the operation is successful. */
public boolean enQueue(int value) {
if (isFull()) {
return false;
}
ListNode newNode = new ListNode(value);
newNode.next = tail;
newNode.prev = tail.prev;
tail.prev.next = newNode;
tail.prev = newNode;
currSize++;
return true;
}
/** Delete an element from the circular queue. Return true if the operation is successful. */
public boolean deQueue() {
if (isEmpty()) {
return false;
}
ListNode toBeDeleted = head.next;
head.next = toBeDeleted.next;
toBeDeleted.next.prev = head;
toBeDeleted.next = null;
toBeDeleted.prev = null;
currSize--;
return true;
}
/** Get the front item from the queue. */
public int Front() {
if(isEmpty()) {
return -1;
}
return head.next.val;
}
/** Get the last item from the queue. */
public int Rear() {
if(isEmpty()) {
return -1;
}
return tail.prev.val;
}
/** Checks whether the circular queue is empty or not. */
public boolean isEmpty() {
return currSize == 0;
}
/** Checks whether the circular queue is full or not. */
public boolean isFull() {
return currSize == queueSize;
}
}