https://leetcode.com/problems/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.
Approach 1: Array
Insert: int index = (this.headIndex + this.count) % this.capacity;
Delete: this.headIndex = (this.headIndex + 1) % this.capacity;
Front: queue[this.headIndex];
Rear: (this.headIndex + this.count - 1) % this.capacity;
Complexity
- Time complexity: O(1). All of the methods in our circular data structure is of constant time complexity.
- Space Complexity: O(N). The overall space complexity of the data structure is linear, where N is the pre-assigned capacity of the queue. However, it is worth mentioning that the memory consumption of the data structure remains as its pre-assigned capacity during its entire life cycle.
class MyCircularQueue {
private int[] queue;
private int headIndex;
private int count;
private int capacity;
/** Initialize your data structure here. Set the size of the queue to be k. */
public MyCircularQueue(int k) {
this.capacity = k;
this.queue = new int[k];
this.headIndex = 0;
this.count = 0;
}
/** Insert an element into the circular queue. Return true if the operation is successful. */
public boolean enQueue(int value) {
if (this.count == this.capacity) return false;
int index = (this.headIndex + this.count) % this.capacity;
this.queue[index] = value;
this.count += 1;
return true;
}
/** Delete an element from the circular queue. Return true if the operation is successful. */
public boolean deQueue() {
if (this.count == 0) return false;
this.headIndex = (this.headIndex + 1) % this.capacity;
this.count -= 1;
return true;
}
/** Get the front item from the queue. */
public int Front() {
if (this.count == 0) return -1;
return this.queue[this.headIndex];
}
/** Get the last item from the queue. */
public int Rear() {
if (this.count == 0) return -1;
int tailIndex = (this.headIndex + this.count - 1) % this.capacity;
return this.queue[tailIndex];
}
/** Checks whether the circular queue is empty or not. */
public boolean isEmpty() {
return (this.count == 0);
}
/** Checks whether the circular queue is full or not. */
public boolean isFull() {
return (this.count == this.capacity);
}
}
/**
* 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();
*/Approach #2 Singly-Linked List
Two nodes: Head and tail
class Node {
public int value;
public Node nextNode;
public Node(int value) {
this.value = value;
this.nextNode = null;
}
}
class MyCircularQueue {
private Node head, tail;
private int count;
private int capacity;
/** Initialize your data structure here. Set the size of the queue to be k. */
public MyCircularQueue(int k) {
this.capacity = k;
}
/** Insert an element into the circular queue. Return true if the operation is successful. */
public boolean enQueue(int value) {
if (this.count == this.capacity)
return false;
Node newNode = new Node(value);
if (this.count == 0) {
head = tail = newNode;
} else {
tail.nextNode = newNode;
tail = newNode;
}
this.count += 1;
return true;
}
/** Delete an element from the circular queue. Return true if the operation is successful. */
public boolean deQueue() {
if (this.count == 0)
return false;
this.head = this.head.nextNode;
this.count -= 1;
return true;
}
/** Get the front item from the queue. */
public int Front() {
if (this.count == 0)
return -1;
else
return this.head.value;
}
/** Get the last item from the queue. */
public int Rear() {
if (this.count == 0)
return -1;
else
return this.tail.value;
}
/** Checks whether the circular queue is empty or not. */
public boolean isEmpty() {
return (this.count == 0);
}
/** Checks whether the circular queue is full or not. */
public boolean isFull() {
return (this.count == this.capacity);
}
}