seanpgallivan

Posted on

# Solution: Design Circular Queue

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

#### Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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.

Implementation the MyCircularQueue class:

• `MyCircularQueue(k)` Initializes the object with the size of the queue to be `k`.
• `int Front()` Gets the front item from the queue. If the queue is empty, return `-1`.
• `int Rear()` Gets the last item from the queue. If the queue is empty, return `-1`.
• `boolean enQueue(int value)` Inserts an element into the circular queue. Return `true` if the operation is successful.
• `boolean deQueue()` Deletes an element from the circular queue. Return `true` if the operation is successful.
• `boolean isEmpty()` Checks whether the circular queue is empty or not.
• `boolean isFull()` Checks whether the circular queue is full or not.

#### Examples:

Example 1:
Input: ["MyCircularQueue", "enQueue", "enQueue", "enQueue", "enQueue", "Rear", "isFull", "deQueue", "enQueue", "Rear"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output: [null, true, true, true, false, 3, true, true, true, 4]
Explanation: MyCircularQueue myCircularQueue = new MyCircularQueue(3);
myCircularQueue.enQueue(1); // return True
myCircularQueue.enQueue(2); // return True
myCircularQueue.enQueue(3); // return True
myCircularQueue.enQueue(4); // return False
myCircularQueue.Rear(); // return 3
myCircularQueue.isFull(); // return True
myCircularQueue.deQueue(); // return True
myCircularQueue.enQueue(4); // return True
myCircularQueue.Rear(); // *return 4

#### Constraints:

• `1 <= k <= 1000`
• `0 <= value <= 1000`
• At most `3000` calls will be made to `enQueue`, `deQueue`, `Front`, `Rear`, `isEmpty`, and `isFull`.

#### Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

(Update: On my initial read of the problem, I skipped the second half of the first paragraph which talks about connecting the end of the data structure to its beginning, so I chose a linked list approach with the idea of saving on unused data structure memory allocation. But with the full description in mind, the more correct interpretation would be an array-based approach with rolling indexes for the head and the tail of the queue. I've left the code for the linked list approach below, but I've updated this solution to effect the change in approach.)

Since this problem tasks us with creating a queue data structure that is connected front-to-back, but with a set size, we should be thinking of the standard array-based queue structure, but modified with a modulo index system in order to reuse the cleared space at the beginning of the queue without the need to constantly reallocate with push and shift operations.

Otherwise, the code here is fairly straightforward. We'll use a modulo index system to seamlessly connect the back to the front of the queue and separate pointers for the head and tail.

One challenge will be defining our isEmpty state. There are several options, but rather than using any other variables, and since the enQueue method will naturally increment tail, we can use tail = -1 to represent an empty queue, which will conveniently lead into tail = 0 once we add our first entry.

That means that our deQueue method will need to reset back to this initial condition if there's only one element left (head = tail) prior to its removal.

Finally, the queue isFull when the tail is just behind the head, except for the case of an empty queue.

#### Javascript Code:

##### w/ Array Modulo:
``````class MyCircularQueue {
constructor(k) {
this.data = new Uint16Array(k)
this.maxSize = k
this.tail = -1
}
enQueue(val) {
if (this.isFull()) return false
this.tail = (this.tail + 1) % this.maxSize
this.data[this.tail] = val
return true
}
deQueue() {
if (this.isEmpty()) return false
return true
}
Front() {
return this.isEmpty() ? -1 : this.data[this.head]
}
Rear() {
return this.isEmpty() ? -1 : this.data[this.tail]
}
isEmpty() {
return this.tail === -1
}
isFull() {
return !this.isEmpty() && (this.tail + 1) % this.maxSize === this.head
};
};
``````
``````class ListNode {
constructor(val, next=null) {
this.val = val
this.next = next
}
}
class MyCircularQueue {
constructor(k) {
this.maxSize = k
this.size = 0
this.tail = null
}
enQueue(val) {
if (this.isFull()) return false
let newNode = new ListNode(val)
if (this.isEmpty()) this.head = this.tail = newNode
else this.tail.next = newNode, this.tail = this.tail.next
this.size++
return true
}
deQueue() {
if (this.isEmpty()) return false
this.size--
return true
}
Front() {
return this.isEmpty() ? -1 : this.head.val
}
Rear() {
return this.isEmpty() ? -1 : this.tail.val
}
isEmpty() {
return this.size === 0
}
isFull() {
return this.size === this.maxSize
};
};
``````

#### Python Code:

##### w/ Array Modulo:
``````class MyCircularQueue:
def __init__(self, k: int):
self.data = [0] * k
self.maxSize = k
self.tail = -1
def enQueue(self, val: int) -> bool:
if self.isFull(): return False
self.tail = (self.tail + 1) % self.maxSize
self.data[self.tail] = val
return True
def deQueue(self) -> bool:
if self.isEmpty(): return False
return True
def Front(self) -> int:
return -1 if self.isEmpty() else self.data[self.head]
def Rear(self) -> int:
return -1 if self.isEmpty() else self.data[self.tail]
def isEmpty(self) -> bool:
return self.tail == -1
def isFull(self) -> bool:
return not self.isEmpty() and (self.tail + 1) % self.maxSize == self.head
``````
``````class ListNode:
def __init__(self, val: int, nxt: ListNode = None):
self.val = val
self.next = nxt
class MyCircularQueue:
def __init__(self, k: int):
self.maxSize = k
self.size = 0
self.tail = None
def enQueue(self, val: int) -> bool:
if self.isFull(): return False
newNode = ListNode(val)
if self.isEmpty(): self.head = self.tail = newNode
else:
self.tail.next = newNode
self.tail = self.tail.next
self.size += 1
return True
def deQueue(self) -> bool:
if self.isEmpty(): return False
self.size -= 1
return True
def Front(self) -> int:
return -1 if self.isEmpty() else self.head.val
def Rear(self) -> int:
return -1 if self.isEmpty() else self.tail.val
def isEmpty(self) -> bool:
return self.size == 0
def isFull(self) -> bool:
return self.size == self.maxSize
``````

#### Java Code:

##### w/ Array Modulo:
``````class MyCircularQueue {
int maxSize, head = 0, tail = -1;
int[] data;
public MyCircularQueue(int k) {
data = new int[k];
maxSize = k;
}
public boolean enQueue(int val) {
if (isFull()) return false;
tail = (tail + 1) % maxSize;
data[tail] = val;
return true;
}
public boolean deQueue() {
if (isEmpty()) return false;
tail = -1;
return true;
}
public int Front() {
return isEmpty() ? -1 : data[head];
}
public int Rear() {
return isEmpty() ? -1 : data[tail];
}
public boolean isEmpty() {
return tail == -1;
}
public boolean isFull() {
return !isEmpty() && (tail + 1) % maxSize == head;
}
``````
``````class ListNode {
int val;
ListNode next;
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
class MyCircularQueue {
int maxSize, size = 0;
ListNode head = null, tail = null;
public MyCircularQueue(int k) {
maxSize = k;
}
public boolean enQueue(int val) {
if (isFull()) return false;
ListNode newNode = new ListNode(val, null);
if (isEmpty()) head = tail = newNode;
else {
tail.next = newNode;
tail = tail.next;
}
size++;
return true;
}
public boolean deQueue() {
if (isEmpty()) return false;
size--;
return true;
}
public int Front() {
return isEmpty() ? -1 : head.val;
}
public int Rear() {
return isEmpty() ? -1 : tail.val;
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == maxSize;
}
}
``````

#### C++ Code:

##### w/ Array Modulo:
``````class MyCircularQueue {
public:
MyCircularQueue(int k) {
data.resize(k);
maxSize = k;
}
bool enQueue(int val) {
if (isFull()) return false;
tail = (tail + 1) % maxSize;
data[tail] = val;
return true;
}
bool deQueue() {
if (isEmpty()) return false;
return true;
}
int Front() {
return isEmpty() ? -1 : data[head];
}
int Rear() {
return isEmpty() ? -1 : data[tail];
}
bool isEmpty() {
return tail == -1;
}
bool isFull() {
return !isEmpty() && (tail + 1) % maxSize == head;
}
private:
int maxSize, head = 0, tail = -1;
vector<int> data;
};
``````
``````struct Node {
public:
int val;
Node* next;
Node(int v, Node* n=nullptr) {
val = v;
next = n;
}
};
class MyCircularQueue {
public:
MyCircularQueue(int k) {
maxSize = k;
}
bool enQueue(int val) {
if (isFull()) return false;
Node* newNode = new Node(val);
if (isEmpty()) head = newNode, tail = newNode;
else tail->next = newNode, tail = tail->next;
size++;
return true;
}
bool deQueue() {
if (isEmpty()) return false;
size--;
return true;
}
int Front() {
return isEmpty() ? -1 : head->val;
}
int Rear() {
return isEmpty() ? -1 : tail->val;
}
bool isEmpty() {
return size == 0;
}
bool isFull() {
return size == maxSize;
}
private:
int maxSize, size = 0;
Node *head = new Node(0), *tail = new Node(0);
};
``````

Rohith V

Here is my Java Solution using Array

``````class MyCircularQueue {

int [] queue;
int front;
int rear = -1;
int length = 0;
public MyCircularQueue(int k) {
queue = new int [k];
}

public boolean enQueue(int value) {
if (!isFull()) {
rear = (rear + 1) % queue.length;
queue[rear] = value;
length += 1;
return true;
}
return false;
}

public boolean deQueue() {
if (!isEmpty()) {
front = (front + 1) % queue.length;
length -= 1;
return true;
}
return false;
}

public int Front() {
return isEmpty() ? -1 :queue[front];
}

public int Rear() {
return isEmpty() ? -1 : queue[rear];
}

public boolean isEmpty() {
return length == 0;
}

public boolean isFull() {
return queue.length == 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();
*/
``````

My Github Repo : (github.com/Rohithv07/LeetCodeTopIn...)