Algorithm
Problem Name: 622. Design Circular Queue
Problem Link: 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.
Implement the MyCircularQueue class:
MyCircularQueue(k)Initializes the object with the size of the queue to bek.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. Returntrueif the operation is successful.boolean deQueue()Deletes an element from the circular queue. Returntrueif 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.
You must solve the problem without using the built-in queue data structure in your programming language.
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 <= 10000 <= value <= 1000- At most
3000calls will be made toenQueue,deQueue,Front,Rear,isEmpty, andisFull.
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class MyCircularQueue {
private Integer[] queue;
private int valueCursor;
private int emptyCursor;
public MyCircularQueue(int k) {
this.queue = new Integer[k];
this.valueCursor = 0;
this.emptyCursor = 0;
}
public boolean enQueue(int value) {
if (queue[emptyCursor] != null) {
return false;
}
queue[emptyCursor++] = value;
if (emptyCursor == queue.length) {
emptyCursor = 0;
}
return true;
}
public boolean deQueue() {
if (queue[valueCursor] == null) {
return false;
}
queue[valueCursor++] = null;
if (valueCursor == queue.length) {
valueCursor = 0;
}
return true;
}
public int Front() {
return queue[valueCursor] == null ? -1 : queue[valueCursor];
}
public int Rear() {
int idx = emptyCursor == 0 ? queue.length - 1 : emptyCursor - 1;
return queue[idx] == null ? -1 : queue[idx];
}
public boolean isEmpty() {
return queue[valueCursor] == null;
}
public boolean isFull() {
return queue[emptyCursor] != null;
}
}
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]
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const MyCircularQueue = function (k) {
this.a = new Array(k).fill(0)
this.front = 0
this.rear = -1
this.len = 0
}
MyCircularQueue.prototype.enQueue = function (value) {
if (!this.isFull()) {
this.rear = (this.rear + 1) % this.a.length
this.a[this.rear] = value
this.len++
return true
} else return false
}
MyCircularQueue.prototype.deQueue = function () {
if (!this.isEmpty()) {
this.front = (this.front + 1) % this.a.length
this.len--
return true
} else return false
}
MyCircularQueue.prototype.Front = function () {
return this.isEmpty() ? -1 : this.a[this.front]
}
MyCircularQueue.prototype.Rear = function () {
return this.isEmpty() ? -1 : this.a[this.rear]
}
MyCircularQueue.prototype.isEmpty = function () {
return this.len === 0
}
MyCircularQueue.prototype.isFull = function () {
return this.len == this.a.length
}
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]
#3 Code Example with Python Programming
Code -
Python Programming
class Node:
def __init__(self, value):
self.val = value
self.next = self.pre = None
class MyCircularQueue:
def __init__(self, k):
self.size = k
self.curSize = 0
self.head = self.tail = Node(-1)
self.head.next = self.tail
self.tail.pre = self.head
def enQueue(self, value):
if self.curSize < self.size:
node = Node(value)
node.pre = self.tail.pre
node.next = self.tail
node.pre.next = node.next.pre = node
self.curSize += 1
return True
return False
def deQueue(self):
if self.curSize > 0:
node = self.head.next
node.pre.next = node.next
node.next.pre = node.pre
self.curSize -= 1
return True
return False
def Front(self):
return self.head.next.val
def Rear(self):
return self.tail.pre.val
def isEmpty(self):
return self.curSize == 0
def isFull(self):
return self.curSize == self.size
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]