LeetCode 622 - Design Circular Queue

The problem asks us to implement a circular queue, a fixed-size queue where the end wraps back to the start to efficiently reuse empty space.

leetcodemediumarraylinked-listdesignqueue

LeetCode Problem 622

Difficulty: 🟡 Medium
Topics: Array, Linked List, Design, Queue

Solution

Problem Understanding

The problem asks us to implement a circular queue, a fixed-size queue where the end wraps back to the start to efficiently reuse empty space. In a normal queue implemented with an array, once the array fills, even if elements are dequeued from the front, new elements cannot be enqueued without shifting the array. A circular queue solves this by treating the array as circular, so the next insertion after the last index can occur at index 0 if space is available.

The input consists of method calls to the queue object: enQueue adds elements, deQueue removes elements, Front and Rear read elements from the front and back, and isEmpty / isFull check the queue state. The output is the return value of these calls. Constraints indicate the queue size k is at most 1000 and at most 3000 operations are performed. This makes an array-based solution feasible without worrying about performance limits.

Edge cases include trying to enqueue into a full queue, dequeue from an empty queue, and reading Front or Rear when the queue is empty. Handling the wrap-around correctly is crucial; naive implementations often get off-by-one errors with indices.

Approaches

A brute-force approach could use a dynamic array or list and shift elements on every dequeue to maintain the front at index 0. This is correct but inefficient, as shifting elements on every dequeue results in O(n) time for each dequeue operation, which is unnecessary.

The optimal approach uses a fixed-size array with two pointers, front and rear, and a count of elements. enQueue inserts at rear and moves it forward modulo k. deQueue moves front forward modulo k. isEmpty checks if count is zero, and isFull checks if count equals k. This approach maintains O(1) time for all operations, and no elements need to be shifted.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) per deQueue O(k) Shift elements on dequeue
Optimal O(1) per operation O(k) Use array with front, rear, count; wrap indices modulo k

Algorithm Walkthrough

  1. Initialize the queue with a fixed-size array of size k. Set front and rear to 0 and count to 0.
  2. To enQueue(value), first check if the queue is full (count == k). If full, return False. Otherwise, insert value at rear, increment rear modulo k, and increment count. Return True.
  3. To deQueue(), first check if the queue is empty (count == 0). If empty, return False. Otherwise, increment front modulo k and decrement count. Return True.
  4. Front() returns -1 if the queue is empty. Otherwise, return the value at front.
  5. Rear() returns -1 if the queue is empty. Otherwise, return the value at (rear - 1 + k) % k because rear points to the next insertion index.
  6. isEmpty() returns True if count == 0, else False.
  7. isFull() returns True if count == k, else False.

The algorithm works because the combination of front, rear, and count always maintains the correct number of elements and ensures that all operations respect FIFO order. Using modulo arithmetic guarantees the circular behavior.

Python Solution

class MyCircularQueue:

    def __init__(self, k: int):
        self.queue = [0] * k
        self.k = k
        self.front = 0
        self.rear = 0
        self.count = 0

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False
        self.queue[self.rear] = value
        self.rear = (self.rear + 1) % self.k
        self.count += 1
        return True

    def deQueue(self) -> bool:
        if self.isEmpty():
            return False
        self.front = (self.front + 1) % self.k
        self.count -= 1
        return True

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

    def Rear(self) -> int:
        if self.isEmpty():
            return -1
        return self.queue[(self.rear - 1 + self.k) % self.k]

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

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

The Python implementation uses a fixed array queue to store elements and maintains front, rear, and count. All operations use modulo arithmetic to handle the circular behavior. This guarantees O(1) for each operation and correct wrap-around.

Go Solution

type MyCircularQueue struct {
	queue       []int
	front, rear int
	count, k    int
}

func Constructor(k int) MyCircularQueue {
	return MyCircularQueue{
		queue: make([]int, k),
		k:     k,
	}
}

func (this *MyCircularQueue) EnQueue(value int) bool {
	if this.IsFull() {
		return false
	}
	this.queue[this.rear] = value
	this.rear = (this.rear + 1) % this.k
	this.count++
	return true
}

func (this *MyCircularQueue) DeQueue() bool {
	if this.IsEmpty() {
		return false
	}
	this.front = (this.front + 1) % this.k
	this.count--
	return true
}

func (this *MyCircularQueue) Front() int {
	if this.IsEmpty() {
		return -1
	}
	return this.queue[this.front]
}

func (this *MyCircularQueue) Rear() int {
	if this.IsEmpty() {
		return -1
	}
	return this.queue[(this.rear-1+this.k)%this.k]
}

func (this *MyCircularQueue) IsEmpty() bool {
	return this.count == 0
}

func (this *MyCircularQueue) IsFull() bool {
	return this.count == this.k
}

The Go solution is similar to Python but uses slices with fixed length and integer fields to track state. Wrap-around is handled identically using modulo arithmetic.

Worked Examples

Example operations on a queue of size 3:

Operation queue front rear count Output
enQueue(1) [1,0,0] 0 1 1 True
enQueue(2) [1,2,0] 0 2 2 True
enQueue(3) [1,2,3] 0 0 3 True
enQueue(4) [1,2,3] 0 0 3 False
Rear() [1,2,3] 0 0 3 3
isFull() [1,2,3] 0 0 3 True
deQueue() [1,2,3] 1 0 2 True
enQueue(4) [4,2,3] 1 1 3 True
Rear() [4,2,3] 1 1 3 4

Complexity Analysis

Measure Complexity Explanation
Time O(1) per operation All operations involve simple pointer updates or checks
Space O(k) Fixed-size array stores up to k elements

Since we never shift elements and only update indices modulo k, the algorithm achieves constant time per operation.

Test Cases

# Basic functionality
q = MyCircularQueue(3)
assert q.enQueue(1) == True  # insert 1
assert q.enQueue(2) == True  # insert 2
assert q.enQueue(3) == True  # insert 3
assert q.enQueue(4) == False # queue is full
assert q.Rear() == 3         # last element
assert q.isFull() == True    # check full
assert q.deQueue() == True   # remove front
assert q.enQueue(4) == True  # insert 4
assert q.Rear() == 4         # new last element

# Edge cases
empty_q = MyCircularQueue(1)
assert empty_q.deQueue() == False  # cannot dequeue empty queue
assert empty_q.Front() == -1       # front is -1 when empty
assert empty_q.Rear() == -1        # rear is -1 when empty
assert empty_q.enQueue(5) == True
assert empty_q.Front() == 5
assert empty_q.Rear() == 5
assert empty_q.isFull() == True
assert empty_q.deQueue() == True
assert empty_q.isEmpty() == True
Test Why
enQueue into full queue Validates isFull logic