Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/622.html
622. Design Circular Queue
Level
Medium
Description
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.
Solution
Use an array to act as a queue and store the elements. Besides the array that is a data field of the class MyCircularQueue
, the other data fields include capacity
which is the capacity of the queue, start
and end
which are the indices of the first element and the last element, and size
which is the number of elements in the queue.
For the constructor, given capacity k
, initialize the array to be an array of length k
and filled with -1, set capacity = k
, and set start
, end
and size
to 0.
For method enQueue
, return false
if the queue is full (checked by calling isFull
). If size == 0
, then set both start
to end
to 0. Otherwise, move end
one step forward (note that the queue is circular, so if end
was previously capacity - 1
, then end
will become 0 after moving one step forward). Set the element at index end
in the array to be the given value, increase size
by 1, and return true
.
For method deQueue
, return false
if the queue is empty (checked by calling isEmpty
). Set the element at index start
to -1, move start
one step forward (note that the queue is circular, so if start
was previously capacity - 1
, then start
will become 0 after moving one step forward), decrease size
by 1, and return true
.
For method Front
, return the element at index start
.
For method Rear
, return the element at index end
.
For method isEmpty
, return true
if and only if size == 0
.
For method isFull
, return true
if and only if size == capacity
.
-
public class Design_Circular_Queue { class MyCircularQueue { int[] arr; int size; int capacity; int front; int back; /** * Initialize your data structure here. Set the size of the queue to be k. */ public MyCircularQueue(int k) { arr = new int[k]; capacity = k; size = 0; front = 0; back = -1; } /** * Insert an element into the circular queue. Return true if the operation is successful. */ public boolean enQueue(int value) { if (size == capacity) { return false; } ++back; arr[back % arr.length] = value; ++size; return true; } /** * Delete an element from the circular queue. Return true if the operation is successful. */ public boolean deQueue() { if (size == 0) return false; ++front; --size; return true; } /** * Get the front item from the queue. */ public int Front() { if (size == 0) return -1; return arr[front % arr.length]; } /** * Get the last item from the queue. */ public int Rear() { if (size == 0) return -1; return arr[back % arr.length]; } /** * Checks whether the circular queue is empty or not. */ public boolean isEmpty() { return size == 0; } /** * Checks whether the circular queue is full or not. */ public boolean isFull() { return size == capacity; } } } ############ class MyCircularQueue { private int[] q; private int front; private int size; private int capacity; public MyCircularQueue(int k) { q = new int[k]; capacity = k; } public boolean enQueue(int value) { if (isFull()) { return false; } int idx = (front + size) % capacity; q[idx] = value; ++size; return true; } public boolean deQueue() { if (isEmpty()) { return false; } front = (front + 1) % capacity; --size; return true; } public int Front() { if (isEmpty()) { return -1; } return q[front]; } public int Rear() { if (isEmpty()) { return -1; } int idx = (front + size - 1) % capacity; return q[idx]; } public boolean isEmpty() { return size == 0; } public boolean isFull() { return size == 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(); */
-
// OJ: https://leetcode.com/problems/design-circular-queue/ // Time: O(1) for all // Space: O(K) class MyCircularQueue { private: vector<int> v; int start = 0, len = 0; public: MyCircularQueue(int k): v(k) {} bool enQueue(int value) { if (isFull()) return false; v[(start + len++) % v.size()] = value; return true; } bool deQueue() { if (isEmpty()) return false; start = (start + 1) % v.size(); --len; return true; } int Front() { if (isEmpty()) return -1; return v[start]; } int Rear() { if (isEmpty()) return -1; return v[(start + len - 1) % v.size()]; } bool isEmpty() { return !len; } bool isFull() { return len == v.size(); } };
-
class MyCircularQueue: def __init__(self, k: int): self.q = [0] * k self.front = 0 self.size = 0 self.capacity = k def enQueue(self, value: int) -> bool: if self.isFull(): return False idx = (self.front + self.size) % self.capacity self.q[idx] = value self.size += 1 return True def deQueue(self) -> bool: if self.isEmpty(): return False self.front = (self.front + 1) % self.capacity self.size -= 1 return True def Front(self) -> int: return -1 if self.isEmpty() else self.q[self.front] def Rear(self) -> int: if self.isEmpty(): return -1 idx = (self.front + self.size - 1) % self.capacity return self.q[idx] def isEmpty(self) -> bool: return self.size == 0 def isFull(self) -> bool: return self.size == self.capacity # Your MyCircularQueue object will be instantiated and called as such: # obj = MyCircularQueue(k) # param_1 = obj.enQueue(value) # param_2 = obj.deQueue() # param_3 = obj.Front() # param_4 = obj.Rear() # param_5 = obj.isEmpty() # param_6 = obj.isFull() ############ class MyCircularQueue(object): def __init__(self, k): """ Initialize your data structure here. Set the size of the queue to be k. :type k: int """ self.queue = [] self.size = k self.front = 0 self.rear = 0 def enQueue(self, value): """ Insert an element into the circular queue. Return true if the operation is successful. :type value: int :rtype: bool """ if self.rear - self.front < self.size: self.queue.append(value) self.rear += 1 return True else: return False def deQueue(self): """ Delete an element from the circular queue. Return true if the operation is successful. :rtype: bool """ if self.rear - self.front > 0: self.front += 1 return True else: return False def Front(self): """ Get the front item from the queue. :rtype: int """ if self.isEmpty(): return -1 else: return self.queue[self.front] def Rear(self): """ Get the last item from the queue. :rtype: int """ if self.isEmpty(): return -1 else: return self.queue[self.rear - 1] def isEmpty(self): """ Checks whether the circular queue is empty or not. :rtype: bool """ return self.front == self.rear def isFull(self): """ Checks whether the circular queue is full or not. :rtype: bool """ return self.rear - self.front == self.size # Your MyCircularQueue object will be instantiated and called as such: # obj = MyCircularQueue(k) # param_1 = obj.enQueue(value) # param_2 = obj.deQueue() # param_3 = obj.Front() # param_4 = obj.Rear() # param_5 = obj.isEmpty() # param_6 = obj.isFull()
-
type MyCircularQueue struct { front int size int capacity int q []int } func Constructor(k int) MyCircularQueue { q := make([]int, k) return MyCircularQueue{0, 0, k, q} } func (this *MyCircularQueue) EnQueue(value int) bool { if this.IsFull() { return false } idx := (this.front + this.size) % this.capacity this.q[idx] = value this.size++ return true } func (this *MyCircularQueue) DeQueue() bool { if this.IsEmpty() { return false } this.front = (this.front + 1) % this.capacity this.size-- return true } func (this *MyCircularQueue) Front() int { if this.IsEmpty() { return -1 } return this.q[this.front] } func (this *MyCircularQueue) Rear() int { if this.IsEmpty() { return -1 } idx := (this.front + this.size - 1) % this.capacity return this.q[idx] } func (this *MyCircularQueue) IsEmpty() bool { return this.size == 0 } func (this *MyCircularQueue) IsFull() bool { return this.size == this.capacity } /** * Your MyCircularQueue object will be instantiated and called as such: * obj := Constructor(k); * param_1 := obj.EnQueue(value); * param_2 := obj.DeQueue(); * param_3 := obj.Front(); * param_4 := obj.Rear(); * param_5 := obj.IsEmpty(); * param_6 := obj.IsFull(); */
-
class MyCircularQueue { private queue: number[]; private left: number; private right: number; private capacity: number; constructor(k: number) { this.queue = new Array(k); this.left = 0; this.right = 0; this.capacity = k; } enQueue(value: number): boolean { if (this.isFull()) { return false; } this.queue[this.right % this.capacity] = value; this.right++; return true; } deQueue(): boolean { if (this.isEmpty()) { return false; } this.left++; return true; } Front(): number { if (this.isEmpty()) { return -1; } return this.queue[this.left % this.capacity]; } Rear(): number { if (this.isEmpty()) { return -1; } return this.queue[(this.right - 1) % this.capacity]; } isEmpty(): boolean { return this.right - this.left === 0; } isFull(): boolean { return this.right - this.left === this.capacity; } } /** * 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() */
-
struct MyCircularQueue { queue: Vec<i32>, left: usize, right: usize, capacity: usize, } /** * `&self` means the method takes an immutable reference. * If you need a mutable reference, change it to `&mut self` instead. */ impl MyCircularQueue { fn new(k: i32) -> Self { let k = k as usize; Self { queue: vec![0; k], left: 0, right: 0, capacity: k, } } fn en_queue(&mut self, value: i32) -> bool { if self.is_full() { return false; } self.queue[self.right % self.capacity] = value; self.right += 1; true } fn de_queue(&mut self) -> bool { if self.is_empty() { return false; } self.left += 1; true } fn front(&self) -> i32 { if self.is_empty() { return -1; } self.queue[self.left % self.capacity] } fn rear(&self) -> i32 { if self.is_empty() { return -1; } self.queue[(self.right - 1) % self.capacity] } fn is_empty(&self) -> bool { self.right - self.left == 0 } fn is_full(&self) -> bool { self.right - self.left == self.capacity } } /** * Your MyCircularQueue object will be instantiated and called as such: * let obj = MyCircularQueue::new(k); * let ret_1: bool = obj.en_queue(value); * let ret_2: bool = obj.de_queue(); * let ret_3: i32 = obj.front(); * let ret_4: i32 = obj.rear(); * let ret_5: bool = obj.is_empty(); * let ret_6: bool = obj.is_full(); */ */