Design Circular Queue

QueueDesign

25 min

Problem Statement

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.

Example

Example 1:

Operation Sequence:

MyCircularQueue(3)returns:

enQueue(1)returns: true

enQueue(2)returns: true

enQueue(3)returns: true

enQueue(4)returns: false

Rear()returns: 3

isFull()returns: true

deQueue()returns: true

enQueue(4)returns: true

Rear()returns: 4

Solution

A circular queue can be implemented using an array and two pointers, `head` and `tail`. The key is to use the modulo operator to wrap around the array, creating the circular behavior.

Algorithm Steps

Initialize an array of a fixed size, and pointers for head and tail.
`enQueue`: Add an element at the tail. If the queue is full, return false. Otherwise, add the element and move the tail pointer.
`deQueue`: Remove an element from the head. If the queue is empty, return false. Otherwise, move the head pointer.
`Front` and `Rear`: Return the element at the head or tail respectively.
`isEmpty` and `isFull`: Check the conditions based on the head and tail pointers.

Initialize an empty queue of size 3.

Design Circular Queue Solution


class MyCircularQueue:
    def __init__(self, k: int):
        self.q = [0] * k
        self.head = 0
        self.cnt = 0
        self.size = k

    def enQueue(self, value: int) -> bool:
        if self.isFull(): return False
        self.q[(self.head + self.cnt) % self.size] = value
        self.cnt += 1
        return True

    def deQueue(self) -> bool:
        if self.isEmpty(): return False
        self.head = (self.head + 1) % self.size
        self.cnt -= 1
        return True

    def Front(self) -> int:
        if self.isEmpty(): return -1
        return self.q[self.head]

    def Rear(self) -> int:
        if self.isEmpty(): return -1
        return self.q[(self.head + self.cnt - 1) % self.size]

    def isEmpty(self) -> bool:
        return self.cnt == 0

    def isFull(self) -> bool:
        return self.cnt == self.size