Table of Content

  1. Problem Statement
  2. Problem Input
  3. Solution

Problem statement

622. 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.

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

Input

class MyCircularQueue:
    def __init__(self, k: int):
        """
        Initialize your data structure here. Set the size of the queue to be k.
        """
        self.queue = [ None ] * k
        self.size = 0
        self.capacity = k
        self.head, self.tail = 0, -1


    def enQueue(self, value: int) -> bool:
        """
        Insert an element into the circular queue. Return true if the operation is successful.
        """
        if self.isFull():
            return False


        self.tail = (self.tail + 1) % self.capacity
        self.queue[self.tail] = value
        self.size += 1
        return True


    def deQueue(self) -> bool:
        """
        Delete an element from the circular queue. Return true if the operation is successful.
        """
        if self.isEmpty():
            return False


        self.head = (self.head + 1) % self.capacity
        self.size -= 1
        return True


    def Front(self) -> int:
        """
        Get the front item from the queue.
        """


        return -1 if self.isEmpty() else self.queue[self.head]


    def Rear(self) -> int:
        """
        Get the last item from the queue.
        """


        return -1 if self.isEmpty() else self.queue[self.tail]


    def isEmpty(self) -> bool:
        """
        Checks whether the circular queue is empty or not.
        """
        return self.size <= 0


    def isFull(self) -> bool:
        """
        Checks whether the circular queue is full or not.
        """
        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()

Standard Solution

Source code

Time Complexity: O(N) for deQueue, O(1) for the rest

Space Complexity: O(N)

The easiest and most straightforward solution for the circular queue is to use an array. Your mileage may vary depending on which programming language you’re using, but in python, [] also acts similar like a queue due to public methods, such as pop, and push.

To implement the circular queue, we just need a capacity to hold k, which is the maximum size of the circular queue. For enQueue and deQueue, we can leverage the builtin pop to remove an element and push to add an element.

class MyCircularQueue:
    def __init__(self, k: int):
        """
        Initialize your data structure here. Set the size of the queue to be k.
        """
        self.queue = []
        self.capacity = k


    def enQueue(self, value: int) -> bool:
        """
        Insert an element into the circular queue. Return true if the operation is successful.
        """
        if self.isFull():
            return False
        self.queue.append(value)
        # print(self.queue)
        return True


    def deQueue(self) -> bool:
        """
        Delete an element from the circular queue. Return true if the operation is successful.
        """
        if self.isEmpty():
            return False
        self.queue.pop(0)
        return True


    def Front(self) -> int:
        """
        Get the front item from the queue.
        """


        return -1 if self.isEmpty() else self.queue[0]


    def Rear(self) -> int:
        """
        Get the last item from the queue.
        """


        return -1 if self.isEmpty() else self.queue[-1]


    def isEmpty(self) -> bool:
        """
        Checks whether the circular queue is empty or not.
        """
        return len(self.queue) <= 0


    def isFull(self) -> bool:
        """
        Checks whether the circular queue is full or not.
        """
        return len(self.queue) == self.capacity

Complexity Explanation

It should be clear why the time complexity of all of the methods are O(1), except for deQueue, which is O(N). deQueue uses pop(0), which removes the first element from the array, forcing rest of the elements to be shifted.

The space complexity is O(N) or O(k) because our circular queue can hold k elements,

Two pointers Solution

Source code

Time Complexity: O(1) for everything

Space Complexity: O(N)

The previous solution is kind of cheating because we’re using builtin methods for []. To implement a circular queue without using those builtin methods, we can use two pointers to keep track of the beginning and the end of the array. This solution can be implemented in almost any programming language.

To implement this, we need:

  1. A queue array initialized with the size of k.
  2. A size to count the current number of elements in the circular queue.
  3. A capacity to hold k.
  4. Two pointers, head and tail to keep track of the front and end of the circular queue.

Everything is similar to the previous solution, except for enQueue and deQueue.

enQueue will increment the tail and save the value. It is important that we also mod/% the tail with the capacity to handle the case when tail > capacity. Because of this, we initialize tail to -1, since initially, there’s nothing inside the array and the first enQueue will place value at tail when tail = 0. We also need to increment the size.

Similarly, deQueue will do the same thing as enQueue except with the head. Although, there are two key differences.

  1. head is initialized to 0 because in the case when we call Front, we need the first element, which is in the first index.
  2. We need to decrement the size instead of incrementing.
class MyCircularQueue:
    def __init__(self, k: int):
        """
        Initialize your data structure here. Set the size of the queue to be k.
        """
        self.queue = [ None ] * k
        self.size = 0
        self.capacity = k
        self.head, self.tail = 0, -1


    def enQueue(self, value: int) -> bool:
        """
        Insert an element into the circular queue. Return true if the operation is successful.
        """
        if self.isFull():
            return False


        self.tail = (self.tail + 1) % self.capacity
        self.queue[self.tail] = value
        self.size += 1
        return True


    def deQueue(self) -> bool:
        """
        Delete an element from the circular queue. Return true if the operation is successful.
        """
        if self.isEmpty():
            return False


        self.head = (self.head + 1) % self.capacity
        self.size -= 1
        return True


    def Front(self) -> int:
        """
        Get the front item from the queue.
        """


        return -1 if self.isEmpty() else self.queue[self.head]


    def Rear(self) -> int:
        """
        Get the last item from the queue.
        """


        return -1 if self.isEmpty() else self.queue[self.tail]


    def isEmpty(self) -> bool:
        """
        Checks whether the circular queue is empty or not.
        """
        return self.size <= 0


    def isFull(self) -> bool:
        """
        Checks whether the circular queue is full or not.
        """
        return self.size == self.capacity

Complexity Explanation

Unlike the previous solution, all the methods in this solution are O(1), especially deQueue because we replaced pop(0) with an indexing solution, which is constant.

The space complexity is still O(N) or O(k) with a little bit more constant overhead from the introduction of additional variables.