Design Circular Queue

▶

Steps

setup

Initialize Circular Queue

We create a circular queue of capacity 3. The internal array is initialized with zeros, and head, tail, and size pointers are set to 0.

💡 Initialization sets the stage for all operations by defining the fixed size and starting pointers.

Line:

self.queue = [0] * k
self.head = 0
self.tail = 0
self.size = 0
self.capacity = k

💡 The queue is empty initially, with head and tail at the same position and size zero.

compare

Enqueue 1 - Check if Full

Before inserting 1, we check if the queue is full by comparing size (0) with capacity (3). It is not full, so we proceed.

💡 Checking fullness prevents overwriting existing elements.

Line:

if self.isFull():
    return False

💡 The queue can accept new elements as size is less than capacity.

insert

Enqueue 1 - Insert Element

We insert the value 1 at the tail index 0, then move tail to 1 (mod 3) and increment size to 1.

💡 Insertion updates the array and advances the tail pointer circularly.

Line:

self.queue[self.tail] = value
self.tail = (self.tail + 1) % self.capacity
self.size += 1

💡 Tail pointer moves forward, size increases, and element 1 is stored at index 0.

compare

Enqueue 2 - Check if Full

Check if the queue is full before inserting 2. Size is 1, capacity 3, so not full.

💡 Each enqueue must verify space availability.

Line:

if self.isFull():
    return False

💡 Queue still has space for new elements.

insert

Enqueue 2 - Insert Element

Insert 2 at tail index 1, advance tail to 2, increment size to 2.

💡 Tail moves forward circularly, size tracks number of elements.

Line:

self.queue[self.tail] = value
self.tail = (self.tail + 1) % self.capacity
self.size += 1

💡 Element 2 stored at index 1, tail now points to index 2.

compare

Enqueue 3 - Check if Full

Check if queue is full before inserting 3. Size is 2, capacity 3, so not full.

💡 Fullness check prevents overflow.

Line:

if self.isFull():
    return False

💡 Queue can still accept one more element.

insert

Enqueue 3 - Insert Element

Insert 3 at tail index 2, advance tail to 0 (wrap around), increment size to 3.

💡 Tail wraps around to start of array, demonstrating circular behavior.

Line:

self.queue[self.tail] = value
self.tail = (self.tail + 1) % self.capacity
self.size += 1

💡 Element 3 stored at index 2, tail wraps to 0, queue is now full.

compare

Enqueue 4 - Check if Full

Check if queue is full before inserting 4. Size is 3, capacity 3, so queue is full and enqueue fails.

💡 Full queue prevents further insertions.

Line:

if self.isFull():
    return False

💡 Queue is full; cannot enqueue 4.

traverse

Rear - Retrieve Last Element

Retrieve the rear element at index (tail - 1 + capacity) % capacity = (0 - 1 + 3) % 3 = 2, which is 3.

💡 Rear returns the last inserted element in the queue.

Line:

return self.queue[(self.tail - 1 + self.capacity) % self.capacity]

💡 Tail points to next insertion index; rear is one behind tail circularly.

compare

isFull - Check if Queue is Full

Check if size equals capacity (3 == 3), which is true, so queue is full.

💡 isFull returns true when queue cannot accept more elements.

Line:

return self.size == self.capacity

💡 Size variable tracks fullness accurately.

compare

Dequeue - Check if Empty

Check if queue is empty before dequeuing. Size is 3, so not empty, proceed to dequeue.

💡 Dequeue only allowed if queue has elements.

Line:

if self.isEmpty():
    return False

💡 Queue has elements to remove.

delete

Dequeue - Remove Element

Advance head pointer from 0 to 1 (mod 3), decrement size from 3 to 2, effectively removing element 1.

💡 Moving head pointer removes front element logically without shifting array.

Line:

self.head = (self.head + 1) % self.capacity
self.size -= 1

💡 Head moves forward, size decreases, queue now has elements [2,3].

compare

Enqueue 4 - Check if Full

Check if queue is full before inserting 4. Size is 2, capacity 3, so not full.

💡 Enqueue allowed as queue has space after dequeue.

Line:

if self.isFull():
    return False

💡 Queue has space due to previous dequeue.

insert

Enqueue 4 - Insert Element with Wrap Around

Insert 4 at tail index 0 (wrap around), advance tail to 1, increment size to 3.

💡 Tail wraps to start of array, showing circular indexing in action.

Line:

self.queue[self.tail] = value
self.tail = (self.tail + 1) % self.capacity
self.size += 1

💡 Element 4 replaces old value at index 0, tail moves forward, queue full again.

traverse

Rear - Retrieve Last Element After Wrap

Retrieve rear element at index (tail - 1 + capacity) % capacity = (1 - 1 + 3) % 3 = 0, which is 4.

💡 Rear reflects the most recently enqueued element, even after wrap-around.

Line:

return self.queue[(self.tail - 1 + self.capacity) % self.capacity]

💡 Tail points to index 1, rear is at index 0 with value 4.

class MyCircularQueue:
    def __init__(self, k: int):
        self.queue = [0] * k  # STEP 1
        self.head = 0         # STEP 1
        self.tail = 0         # STEP 1
        self.size = 0         # STEP 1
        self.capacity = k     # STEP 1

    def enQueue(self, value: int) -> bool:
        if self.isFull():     # STEP 2,4,6,8,13
            return False     # STEP 8
        self.queue[self.tail] = value  # STEP 3,5,7,14
        self.tail = (self.tail + 1) % self.capacity  # STEP 3,5,7,14
        self.size += 1       # STEP 3,5,7,14
        return True          # STEP 3,5,7,14

    def deQueue(self) -> bool:
        if self.isEmpty():    # STEP 11
            return False
        self.head = (self.head + 1) % self.capacity  # STEP 12
        self.size -= 1       # STEP 12
        return True          # STEP 12

    def Front(self) -> int:
        if self.isEmpty():    # Not used in this trace
            return -1
        return self.queue[self.head]

    def Rear(self) -> int:
        if self.isEmpty():    # STEP 9,15
            return -1
        return self.queue[(self.tail - 1 + self.capacity) % self.capacity]  # STEP 9,15

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

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

if __name__ == '__main__':
    cq = MyCircularQueue(3)  # STEP 1
    print(cq.enQueue(1))     # STEP 2,3
    print(cq.enQueue(2))     # STEP 4,5
    print(cq.enQueue(3))     # STEP 6,7
    print(cq.enQueue(4))     # STEP 8
    print(cq.Rear())         # STEP 9
    print(cq.isFull())       # STEP 10
    print(cq.deQueue())      # STEP 11,12
    print(cq.enQueue(4))     # STEP 13,14
    print(cq.Rear())         # STEP 15

📊

Design Circular Queue - Watch the Algorithm Execute, Step by Step

Watching each pointer move and each element insertion or removal helps you understand how the circular queue efficiently uses a fixed-size array without shifting elements.

no_op

Stack (top→bottom)

0

0

0

no_op

Stack (top→bottom)

0

0

0

pushElement[0]: 1

Stack (top→bottom)

0

0

1

↑ pushed: 1

Contributes: true

no_op

Stack (top→bottom)

0

0

1

pushElement[1]: 2

Stack (top→bottom)

0

2

1

↑ pushed: 2

Contributes: true

no_op

Stack (top→bottom)

0

2

1

pushElement[2]: 3

Stack (top→bottom)

3

2

1

↑ pushed: 3

Contributes: true

no_op

Stack (top→bottom)

3

2

1

Contributes: false

peekElement[2]: 3

Stack (top→bottom)

3

2

1

Contributes: 3

no_op

Stack (top→bottom)

3

2

1

Contributes: true

no_op

Stack (top→bottom)

3

2

1

popElement[0]: 1

Stack (top→bottom)

3

2

1

↓ popped: [1]

Contributes: true

no_op

Stack (top→bottom)

3

2

1

pushElement[0]: 4

Stack (top→bottom)

3

2

4

↑ pushed: 4

Contributes: true

peekElement[0]: 4

Stack (top→bottom)

3

2

4

Contributes: 4

Key Takeaways

✓ The circular queue uses modular arithmetic to wrap the tail and head pointers, efficiently reusing array space without shifting elements.

This wrap-around behavior is hard to visualize from code alone but becomes clear when watching pointers move step-by-step.

✓ The size variable is crucial to distinguish between full and empty states, since head == tail can mean either.

Understanding this subtlety is easier when you see the size increment and decrement alongside pointer movements.

✓ Enqueue and dequeue operations each advance one pointer and update size by exactly one, maintaining FIFO order without data movement.

Seeing each pointer move individually clarifies how the queue maintains order and capacity constraints.

Practice

1. Given the following code for largestRectangleArea, what is the returned max_area for input heights = [2,1,2]?

easy

A. 3

B. 4

C. 2

D. 1

Solution

1. Step 1: Trace stack operations for heights=[2,1,2]

   i=0,h=2: stack=[0]; i=1,h=1: pop 0 (height=2,width=1), max_area=2; stack=[]; append 1; i=2,h=2: append 2; i=3,h=0: pop 2 (height=2,width=1), max_area=2; pop 1 (height=1,width=3), max_area=3

2. Step 2: Final max_area after processing all elements

   max_area=3

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Max rectangle area is 3 for input [2,1,2] [OK]

Hint: Remember to add sentinel zero to flush stack [OK]

Common Mistakes:

• Forgetting sentinel zero causes missed areas
• Incorrect width calculation
• Off-by-one in stack indices

2. Given an integer array, you need to find the sum of the minimum values of all possible contiguous subarrays. Which algorithmic approach guarantees an optimal O(n) time complexity solution?

easy

A. Monotonic stack to find previous less and next less elements for each array element

B. Greedy approach selecting minimum elements from left to right

C. Dynamic programming with memoization of subarray minimums

D. Brute force nested loops checking all subarrays and their minimums

Solution

1. Step 1: Understand problem constraints

   The problem requires summing minimums of all subarrays efficiently, which brute force cannot do in O(n).

2. Step 2: Identify the pattern

   Monotonic stack helps find previous less and next less elements in O(n), enabling counting subarrays where each element is minimum.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Monotonic stack approach is known optimal for this problem [OK]

Hint: Monotonic stack finds boundaries for minimums in O(n) [OK]

Common Mistakes:

• Assuming greedy or DP solves this in O(n)
• Confusing with maximum subarray problems

3. Consider this buggy version of the decodeString function. Which line contains the subtle bug that causes incorrect decoding for inputs with multiple bracketed substrings?

medium

A. Line appending current_string to string_stack

B. Line popping count from count_stack

C. Line resetting k after '[' is missing

D. Line appending characters to current_string

Solution

1. Step 1: Identify where repeat count is reset

   After pushing k to count_stack on '[', k must be reset to 0 to avoid carryover to next substring.

2. Step 2: Locate missing reset

   The code comment indicates missing reset of k after pushing it, causing subsequent repeats to accumulate incorrectly.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Resetting k prevents repeat count carryover bugs [OK]

Hint: Repeat count must reset after pushing to stack [OK]

Common Mistakes:

• Forgetting to reset repeat count after '['
• Mismanaging stack push/pop order

4. Suppose the calculator expression can contain multiplication '*' and division '/' operators in addition to plus, minus, and parentheses. Which modification to the stack-based approach correctly handles operator precedence and parentheses?

hard

A. Use two stacks: one for numbers and one for operators, applying operators with higher precedence immediately before pushing lower precedence operators

B. Continue using a single stack and apply all operators in the order they appear, ignoring precedence

C. Convert the expression to postfix notation first, then evaluate using a stack

D. Evaluate recursively without any stack, relying on Python's eval() function

Solution

1. Step 1: Understand operator precedence

   Multiplication and division have higher precedence than addition and subtraction, so evaluation order matters.

2. Step 2: Modify stack approach

   Using two stacks (numbers and operators) allows applying higher precedence operators immediately, preserving correct order.

3. Step 3: Why other options fail

   Single stack ignoring precedence leads to wrong results; postfix conversion is valid but more complex; relying on eval() is unsafe and not interview-appropriate.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Two-stack approach is standard for precedence and parentheses [OK]

Hint: Two stacks handle precedence and parentheses correctly [OK]

Common Mistakes:

• Ignoring precedence or relying on single stack only

5. Suppose the stock prices can be negative and you want to compute the span as before. Which modification to the monotonic stack approach correctly handles negative prices without breaking the algorithm?

hard

A. Store pairs of (price, span) in the stack and accumulate spans when popping

B. Change the while condition to pop only when top price is strictly less than current price

C. Use a balanced binary search tree instead of a stack to handle negative values

D. No change needed; the existing monotonic stack approach works for negative prices

Solution

1. Step 1: Understand impact of negative prices

   Negative prices do not affect the monotonic stack logic, but to handle spans correctly, storing spans with prices helps accumulate consecutive spans efficiently.

2. Step 2: Why storing (price, span) pairs works

   When popping smaller or equal prices, their spans can be added to the current span, allowing correct span calculation even with negative or mixed values.

3. Step 3: Why other options fail

   Changing while condition to strict less breaks equal price handling. Balanced BST is unnecessary overhead. No change ignores span accumulation needed for correctness.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Storing spans with prices is a known robust solution [OK]

Hint: Store (price, span) pairs to accumulate spans correctly [OK]

Common Mistakes:

• Assuming no change needed
• Using strict less instead of less or equal