# 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 数组实现：

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 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];
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) {
}
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;
}
tail = -1;
return true;
}
return true;
}
/** Get the front item from the queue. */
public int Front() {
if (isEmpty() == true) {
return -1;
}
}
/** 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() {
}
/** 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();
*/
class ListNode {
int val;
ListNode prev, next;
public ListNode(int x) {
val = x;
prev = null;
next = null;
}
}
class MyCircularQueue {
int queueSize, currSize;
/** Initialize your data structure here. Set the size of the queue to be k. */
public MyCircularQueue(int k) {
queueSize = k;
currSize = 0;
tail = new ListNode(-1);
}
/** 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;
}
toBeDeleted.next = null;
toBeDeleted.prev = null;
currSize--;
return true;
}
/** Get the front item from the queue. */
public int Front() {
if(isEmpty()) {
return -1;
}
}
/** 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;
}
}