LeetCode Solutions Blog

Design Circular Queue

Number: 860

Difficulty: Medium

Paid? No

Problem Description

Design a circular queue that supports the following operations: enQueue, deQueue, Front, Rear, isEmpty, and isFull. The circular queue should efficiently reuse empty spaces and maintain a FIFO (first in, first out) logic. The challenge is to implement these operations without using the built-in queue data structure.

Key Insights

Leverage a fixed-size array to store the queue elements.
Use two pointers: one for the front and one for the rear.
Maintain a count variable (or use pointer arithmetic) to differentiate between an empty and a full queue.
Use modulo arithmetic to wrap pointers when they reach the end of the array.
Ensure all operations (enQueue, deQueue, Front, Rear, isEmpty, isFull) have O(1) time complexity.

Space and Time Complexity

Time Complexity: O(1) per operation for enQueue, deQueue, Front, Rear, isEmpty, and isFull. Space Complexity: O(k), where k is the capacity of the circular queue.

Solution

We implement the circular queue using a fixed-size array alongside two pointers, front and rear, and a counter to keep track of the number of elements in the queue. The front pointer indicates the index of the first element, and the rear pointer indicates the index where the next element will be enqueued. When enqueuing an element, we insert the element at the rear index and then increment the rear pointer modulo the size of the array. Similarly, when dequeuing, we remove the element at the front index and increment the front pointer modulo the size. The counter helps in quickly checking if the queue is empty or full (count equals 0 or count equals capacity, respectively). This design ensures all operations remain O(1) and correctly wraps around, forming a circular structure.

Code Solutions

# Python implementation of MyCircularQueue

class MyCircularQueue:
    def __init__(self, k):
        # Initialize the queue with capacity k
        self.capacity = k
        self.queue = [0] * k  # fixed-size array
        self.front = 0        # pointer to the front element
        self.rear = 0         # pointer to the next insertion position
        self.count = 0        # current number of elements in the queue

    def enQueue(self, value):
        # Check if the queue is full
        if self.isFull():
            return False
        # Insert element at rear pointer and update pointer using modulo for circularity
        self.queue[self.rear] = value
        self.rear = (self.rear + 1) % self.capacity
        self.count += 1
        return True

    def deQueue(self):
        # Check if the queue is empty
        if self.isEmpty():
            return False
        # Move front pointer to the next element using modulo for circularity
        self.front = (self.front + 1) % self.capacity
        self.count -= 1
        return True

    def Front(self):
        # Return -1 if the queue is empty, else return the front element
        if self.isEmpty():
            return -1
        return self.queue[self.front]

    def Rear(self):
        # Return -1 if the queue is empty
        if self.isEmpty():
            return -1
        # Since rear points to the next insertion position, get the last element index
        return self.queue[(self.rear - 1 + self.capacity) % self.capacity]

    def isEmpty(self):
        # Check if count is 0
        return self.count == 0

    def isFull(self):
        # Check if the queue has reached its capacity
        return self.count == self.capacity