LeetCode 622: Design Circular Queue Solution in Python – A Step-by-Step Guide

What Is LeetCode 622: Design Circular Queue?

In LeetCode 622: Design Circular Queue, you’re tasked with implementing a MyCircularQueue class with a fixed capacity k and these methods:

• enQueue(value): Add an element if space exists.
• deQueue(): Remove the front element if not empty.
• Front(): Return the front element, or -1 if empty.
• Rear(): Return the rear element, or -1 if empty.
• isEmpty(): Check if queue is empty.
• isFull(): Check if queue is full.

Unlike a regular queue, this one is circular—when the end is reached, it wraps around to the start. For example, with k=3, you can add 1, 2, 3, dequeue 1, and add 4 at the start. This problem tests your ability to design a data structure with wrap-around logic.

Problem Statement

• Input:
• k: Integer capacity (1 ≤ k ≤ 1000).
• Method calls with values (0 ≤ value ≤ 1000).
• Output: A class implementing the circular queue methods.
• Rules:
• Fixed size k.
• Circular: Rear wraps to front when full and space opens.

Constraints

• 1 ≤ k ≤ 1000.
• 0 ≤ value ≤ 1000.
• Up to 3000 method calls.

Examples

• Input:
• ["MyCircularQueue", "enQueue", "enQueue", "enQueue", "enQueue", "Rear", "isFull", "deQueue", "enQueue"]
• [[3], [1], [2], [3], [4], [], [], [], [4]]
• Output: [null, true, true, true, false, 3, true, true, true]
• Init k=3, add 1,2,3 (full), 4 fails, rear=3, dequeue 1, add 4.
• Input:
• ["MyCircularQueue", "enQueue", "deQueue", "Front"]
• [[1], [1], [], []]
• Output: [null, true, true, -1]
• Init k=1, add 1, remove 1, front empty.

These examples show the flow—let’s solve it!

Understanding the Problem: Designing a Circular Queue

To solve LeetCode 622: Design Circular Queue in Python, we need to create a class that manages a fixed-size queue where the rear loops back to the front when space is available. A naive approach might use a regular list and shift elements, but that’s slow. We’ll use:

• Best Solution (Array-Based with Pointers): O(1) time per operation, O(k) space—fast and space-efficient.
• Alternative Solution (Linked List-Based): O(1) time per operation, O(k) space—flexible but uses more memory.

Let’s start with the array-based solution, breaking it down for beginners.

Best Solution: Array-Based Circular Queue with Pointers

Why This Is the Best Solution

The array-based circular queue with pointers is the top choice for LeetCode 622 because it’s efficient—O(1) time for all operations—and uses a fixed array with two pointers (front and rear) to track the queue’s state, minimizing space to O(k). It’s the classic circular queue implementation, ideal for fixed-size constraints (k ≤ 1000). It’s like a ring of slots where you track the start and end!

How It Works

Think of this as a circular ticket line:

• Step 1: Initialize:
• Array of size k, front/rear pointers, size counter.
• Step 2: Enqueue:
• If not full, add at rear, increment rear (mod k), update size.
• Step 3: Dequeue:
• If not empty, move front (mod k), decrease size.
• Step 4: Front/Rear:
• Return values at pointers, or -1 if empty.
• Step 5: Check Empty/Full:
• Empty: size = 0.
• Full: size = k.

It’s like a ring manager—track and loop!

Step-by-Step Example

Example: k=3, Operations: enQueue(1), enQueue(2), enQueue(3), deQueue(), enQueue(4)

• Init: queue = [None, None, None], front = 0, rear = 0, size = 0.
• enQueue(1):
• Not full, queue[0] = 1, rear = 1, size = 1.
• [1, None, None].
• enQueue(2):
• queue[1] = 2, rear = 2, size = 2.
• [1, 2, None].
• enQueue(3):
• queue[2] = 3, rear = 0 (wrap), size = 3.
• [1, 2, 3].
• enQueue(4):
• Full (size = k), return False.
• Rear(): queue[2] = 3, return 3.
• isFull(): size = 3 = k, return True.
• deQueue():
• Not empty, front = 1, size = 2, return True.
• [1, 2, 3] (1 logically removed).
• enQueue(4):
• queue[0] = 4, rear = 1, size = 3.
• [4, 2, 3].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

class MyCircularQueue:
    def __init__(self, k: int):
        # Step 1: Initialize array and pointers
        self.k = k
        self.queue = [None] * k
        self.front = 0  # Index of front element
        self.rear = 0   # Index where next element goes
        self.size = 0   # Current number of elements

    def enQueue(self, value: int) -> bool:
        # Step 2: Add element if not full
        if self.isFull():
            return False
        self.queue[self.rear] = value
        self.rear = (self.rear + 1) % self.k  # Wrap around
        self.size += 1
        return True

    def deQueue(self) -> bool:
        # Step 3: Remove element if not empty
        if self.isEmpty():
            return False
        self.front = (self.front + 1) % self.k  # Wrap around
        self.size -= 1
        return True

    def Front(self) -> int:
        # Step 4: Return front element
        if self.isEmpty():
            return -1
        return self.queue[self.front]

    def Rear(self) -> int:
        # Step 5: Return rear element
        if self.isEmpty():
            return -1
        return self.queue[(self.rear - 1) % self.k]

    def isEmpty(self) -> bool:
        # Step 6: Check if empty
        return self.size == 0

    def isFull(self) -> bool:
        # Step 7: Check if full
        return self.size == self.k

• Lines 3-8: Init:
• Array of size k, pointers at 0, size tracker.
• Lines 11-16: enQueue:
• Add at rear, wrap with modulo, increment size.
• Lines 19-23: deQueue:
• Move front, wrap, decrease size.
• Lines 26-29: Front: Return queue[front] or -1.
• Lines 32-35: Rear: Return queue[rear-1] or -1.
• Lines 38-40: isEmpty: Size = 0.
• Lines 43-45: isFull: Size = k.
• Time Complexity: O(1) per operation.
• Space Complexity: O(k)—fixed array.

This is like a ring queue—fast and tight!

Alternative Solution: Linked List-Based Circular Queue

Why an Alternative Approach?

The linked list-based approach uses nodes with pointers—O(1) time per operation, O(k) space. It’s more flexible, dynamically linking elements, but uses extra memory for pointers and isn’t as cache-friendly as an array. It’s like a chain of tickets looping around!

How It Works

Picture this as a linked chain:

• Step 1: Init with head/tail pointers and size.
• Step 2: Enqueue: Add node at tail, link to head if full.
• Step 3: Dequeue: Move head, adjust tail if empty.
• Step 4: Front/Rear: Access head/tail values.
• Step 5: Empty/Full: Check size vs capacity.

It’s like a flexible queue loop!

Step-by-Step Example

Example: k=2, enQueue(1), enQueue(2), deQueue(), enQueue(3)

• Init: head = None, tail = None, size = 0, k = 2.
• enQueue(1):
• head = tail = Node(1), size = 1.
• enQueue(2):
• tail.next = Node(2), tail = tail.next, size = 2.
• tail.next = head (circular).
• deQueue():
• head = head.next, size = 1, return True.
• [2], tail.next = head.
• enQueue(3):
• tail.next = Node(3), tail = tail.next, size = 2.
• [2, 3], tail.next = head.

Code for Linked List Approach

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class MyCircularQueue:
    def __init__(self, k: int):
        self.k = k
        self.head = None
        self.tail = None
        self.size = 0

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False
        new_node = Node(value)
        if self.isEmpty():
            self.head = self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node
        self.tail.next = self.head  # Circular link
        self.size += 1
        return True

    def deQueue(self) -> bool:
        if self.isEmpty():
            return False
        self.head = self.head.next
        self.tail.next = self.head
        self.size -= 1
        if self.isEmpty():
            self.head = self.tail = None
        return True

    def Front(self) -> int:
        return -1 if self.isEmpty() else self.head.value

    def Rear(self) -> int:
        return -1 if self.isEmpty() else self.tail.value

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

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

• Lines 7-12: Init with pointers.
• Lines 14-22: enQueue: Add node, link circularly.
• Lines 25-32: deQueue: Move head, adjust links.
• Time Complexity: O(1) per operation.
• Space Complexity: O(k)—nodes.

It’s a chain queue—flexible but heavier!

Comparing the Two Solutions

• Array-Based (Best):
• Pros: O(1) time, O(k) space, cache-friendly.
• Cons: Fixed structure.
• Linked List (Alternative):
• Pros: O(1) time, O(k) space, dynamic.
• Cons: More memory, less efficient.

Array-based wins for efficiency.

Additional Examples and Edge Cases

• Input: k=1, enQueue(1), enQueue(2)
• Output: [true, false].
• Input: k=1, deQueue()
• Output: [false].

Both handle these well.

Complexity Breakdown

• Array-Based: Time O(1), Space O(k).
• Linked List: Time O(1), Space O(k).

Array-based is optimal.

Key Takeaways

• Array-Based: Pointer magic—smart!
• Linked List: Node flexibility—clear!
• Queues: Circular is fun.
• Python Tip: Arrays rock—see Python Basics.

Final Thoughts: Design That Queue

LeetCode 622: Design Circular Queue in Python is a cool data structure challenge. The array-based approach offers speed and simplicity, while linked lists add flexibility. Want more? Try LeetCode 641: Design Circular Deque or LeetCode 232: Implement Queue using Stacks. Ready to queue up? Head to Solve LeetCode 622 on LeetCode and design that circular queue today!