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; } } }
-
// 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(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()