Design Circular Queue

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,则检测队列是否为空。
对于rear和front的下标位置有两种可行思路:
  1. 1.
    front代表queue的头部元素位置,rear代表queue的尾部元素位置;初始化rear=-1, front=0
  2. 2.
    front代表queue的头部元素位置,rear代表queue的尾部可以填充新元素的位置;初始化时:rear=0, front=0
Tricky之处在于对于1,读取Front()和Rear()可以直接用front和rear作为下标,但是对于2,读取Rear()时,需要计算下标:(rear + q.length - 1) % q.length

Solution

Array Implementation 1 - init front = 0, rear = -1
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;
}
}