622. Design Circular Queue
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.
Implementation 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.
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 to 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.
/**
* @param {number} k
*/
var MyCircularQueue = function(k) {
this.data = new Uint16Array(k)
this.maxSize = k
this.head = 0
this.tail = -1
};
/**
* @param {number} value
* @return {boolean}
*/
MyCircularQueue.prototype.enQueue = function(value) {
if (this.isFull()) return false
this.tail = (this.tail + 1) % this.maxSize
this.data[this.tail] = value
return true
};
/**
* @return {boolean}
*/
MyCircularQueue.prototype.deQueue = function() {
if (this.isEmpty()) return false
if (this.head === this.tail) this.head = 0, this.tail = -1
else this.head = (this.head + 1) % this.maxSize
return true
};
/**
* @return {number}
*/
MyCircularQueue.prototype.Front = function() {
return this.isEmpty() ? -1 : this.data[this.head]
};
/**
* @return {number}
*/
MyCircularQueue.prototype.Rear = function() {
return this.isEmpty() ? -1 : this.data[this.tail]
};
/**
* @return {boolean}
*/
MyCircularQueue.prototype.isEmpty = function() {
return this.tail === -1
};
/**
* @return {boolean}
*/
MyCircularQueue.prototype.isFull = function() {
return !this.isEmpty() && (this.tail + 1) % this.maxSize === this.head
};
/**
* Your MyCircularQueue object will be instantiated and called as such:
* var obj = new MyCircularQueue(k)
* var param_1 = obj.enQueue(value)
* var param_2 = obj.deQueue()
* var param_3 = obj.Front()
* var param_4 = obj.Rear()
* var param_5 = obj.isEmpty()
* var param_6 = obj.isFull()
*/class ListNode {
constructor(val, next=null) {
this.val = val
this.next = next
}
}
class MyCircularQueue {
constructor(k) {
this.maxSize = k
this.size = 0
this.head = null
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.head = this.head.next
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
};
};That’s all folks! In this post, we solved LeetCode problem #622. Design Circular Queue
I hope you have enjoyed this post. Feel free to share your thoughts on this.
You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.
In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!
Comments
Post a Comment