We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Design Circular Queue

Difficulty: Medium

Problem 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". The operations to implement include initializing the queue, retrieving the front and rear elements, inserting and deleting elements, and checking if the queue is empty or full.

Key Insights

  • A circular queue allows efficient use of space by connecting the end of the array back to the beginning.
  • The queue supports FIFO operations, meaning the first element added is the first one to be removed.
  • We need to manage the indices for the front and rear of the queue to handle wrap-around behavior correctly.
  • A counter can be used to track the number of elements currently in the queue.

Space and Time Complexity

Time Complexity:

  • enQueue: O(1)
  • deQueue: O(1)
  • Front: O(1)
  • Rear: O(1)
  • isEmpty: O(1)
  • isFull: O(1)

Space Complexity: O(k), where k is the size of the queue.

Solution

The circular queue can be implemented using a fixed-size array and two pointers (or indices) to track the front and rear of the queue. The array will hold the elements, and the indices will wrap around using modulo arithmetic to ensure they stay within the bounds of the array. The enQueue method will add an element to the rear, while the deQueue method will remove an element from the front. The isEmpty and isFull methods will check the state of the queue based on the indices and the total capacity.

Code Solutions

class MyCircularQueue:
    def __init__(self, k: int):
        self.size = k  # Maximum size of the queue
        self.queue = [0] * k  # Array to store the queue elements
        self.front = -1  # Pointer for the front of the queue
        self.rear = -1  # Pointer for the rear of the queue
    
    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False  # Queue is full
        if self.isEmpty():
            self.front = 0  # Set front to 0 if queue was empty
        self.rear = (self.rear + 1) % self.size  # Circular increment
        self.queue[self.rear] = value  # Insert value
        return True
    
    def deQueue(self) -> bool:
        if self.isEmpty():
            return False  # Queue is empty
        if self.front == self.rear:  # If there's only one element
            self.front = -1  # Reset the queue
            self.rear = -1
        else:
            self.front = (self.front + 1) % self.size  # Circular increment
        return True
    
    def Front(self) -> int:
        if self.isEmpty():
            return -1  # Queue is empty
        return self.queue[self.front]  # Return front element
    
    def Rear(self) -> int:
        if self.isEmpty():
            return -1  # Queue is empty
        return self.queue[self.rear]  # Return rear element
    
    def isEmpty(self) -> bool:
        return self.front == -1  # Queue is empty if front is -1
    
    def isFull(self) -> bool:
        return (self.rear + 1) % self.size == self.front  # Queue is full if next position of rear is front
← Back to All Questions