Implement Stack Using Queues

▶

Steps

setup

Initialize empty queue

Create an empty queue to simulate the stack. No elements are present yet.

💡 Starting with an empty queue is essential to build the stack from scratch.

Line:

self.q = deque()

💡 The queue will hold all stack elements, with the front representing the top.

insert

Push 1: enqueue element

Enqueue 1 into the queue. The queue now contains [1].

💡 Pushing means adding the element to the queue's end before rotation.

Line:

self.q.append(x)  # enqueue

💡 The new element is added at the back of the queue initially.

insert

Push 1: rotate queue (no rotation needed)

Rotate the queue by dequeuing and enqueuing all elements except the newly added one. Since only one element, no rotation occurs.

💡 Rotation ensures the new element moves to the front, but here it's already at front.

Line:

for _ in range(len(self.q) - 1):
    self.q.append(self.q.popleft())  # rotate queue

💡 With one element, the queue front is already the top.

insert

Push 2: enqueue element

Enqueue 2 into the queue. The queue now contains [1, 2].

💡 New elements are always added to the back before rotation.

Line:

self.q.append(x)  # enqueue

💡 The queue temporarily holds elements in insertion order before rotation.

insert

Push 2: rotate queue first rotation

Dequeue front element 1 and enqueue it to the back. Queue changes from [1, 2] to [2, 1].

💡 Rotation moves the newly added element to the front by cycling older elements to the back.

Line:

self.q.append(self.q.popleft())  # rotate queue

💡 After one rotation, the last pushed element moves closer to the front.

compare

Top operation: peek front element

Peek the front element of the queue, which is 2, representing the stack top.

💡 Top returns the front of the queue without removing it.

Line:

return self.q[0]  # peek front

💡 The front of the queue is always the current top of the stack.

delete

Pop operation: dequeue front element

Dequeue the front element 2 from the queue, removing the stack top.

💡 Pop removes the top element by dequeuing the front of the queue.

Line:

return self.q.popleft()  # dequeue front

💡 Removing the front element simulates popping the stack top.

compare

Empty operation: check if queue is empty

Check if the queue is empty. It contains [1], so it is not empty.

💡 Empty returns true if no elements remain, false otherwise.

Line:

return not self.q

💡 The queue's emptiness directly reflects the stack's emptiness.

reconstruct

Final state: stack after all operations

The queue currently holds [1], representing the stack with top element 1.

💡 The final queue state shows the remaining stack elements after all operations.

💡 The queue order reflects the stack order with front as top.

from collections import deque

class MyStack:
    def __init__(self):
        self.q = deque()  # STEP 1

    def push(self, x: int) -> None:
        self.q.append(x)  # STEP 2,4 enqueue
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())  # STEP 3,5 rotate queue

    def pop(self) -> int:
        return self.q.popleft()  # STEP 7 dequeue front

    def top(self) -> int:
        return self.q[0]  # STEP 6 peek front

    def empty(self) -> bool:
        return not self.q  # STEP 8 check empty

if __name__ == '__main__':
    stack = MyStack()  # STEP 1
    stack.push(1)     # STEP 2,3
    stack.push(2)     # STEP 4,5
    print(stack.top())  # STEP 6 output 2
    print(stack.pop())  # STEP 7 output 2
    print(stack.empty())  # STEP 8 output False

📊

Implement Stack Using Queues - Watch the Algorithm Execute, Step by Step

Watching each queue operation and rotation step reveals how the stack's LIFO behavior is maintained using a FIFO queue.

no_op

Stack (top→bottom)

empty

pushElement[0]: 1

Stack (top→bottom)

1

↑ pushed: 1

no_opElement[0]: 1

Stack (top→bottom)

1

pushElement[1]: 2

Stack (top→bottom)

2

1

↑ pushed: 2

no_opElement[0]: 2

Stack (top→bottom)

1

2

peekElement[0]: 2

Stack (top→bottom)

1

2

Contributes: 2

popElement[0]: 2

Stack (top→bottom)

1

↓ popped: [2]

Contributes: 2

no_op

Stack (top→bottom)

1

Contributes: false

no_op

Stack (top→bottom)

1

Key Takeaways

✓ The queue front always represents the stack top after rotations.

This is hard to see from code alone because the queue is FIFO but simulates LIFO by rotation.

✓ Push operation is costly because it rotates the queue to maintain stack order.

Visualizing each rotation step clarifies why push is O(n) and how the order changes.

✓ Pop and top operations are simple and efficient, directly accessing the queue front.

Seeing the queue front accessed for pop/top helps understand the efficiency difference.

Practice

1. Consider the following Python code implementing the optimal 132 pattern detection algorithm. What is the return value when the input is [3, 1, 4, 2]?

easy

A. None

B. False

C. Raises an error

D. True

Solution

1. Step 1: Trace the loop with input [3,1,4,2]

   Iterate reversed: 2,4,1,3. Initially, stack=[], third=-inf. - num=2: stack empty, append 2. - num=4: stack top 2 < 4, pop 2, third=2, append 4. - num=1: 1 < third(2), return True.

2. Step 2: Confirm early return

   At num=1, condition triggers return True, so output is True.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Early return on detecting 132 pattern confirmed [OK]

Hint: Early return when num < third triggers True [OK]

Common Mistakes:

• Confusing iteration order
• Misunderstanding when third updates
• Off-by-one in stack operations

2. You are given a circular array of integers and need to find, for each element, the next greater element when traversing the array circularly. Which algorithmic approach guarantees an optimal O(n) time solution for this problem?

easy

A. Brute force nested loops checking each element's next greater by scanning forward twice

B. Greedy approach selecting next greater element by local comparisons only

C. Dynamic programming with memoization of next greater elements

D. Monotonic stack with explicit circular array copy to simulate circular traversal

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the next greater element for each item in a circular array, which means elements after the end wrap around to the start.

2. Step 2: Identify algorithmic pattern

   Brute force is O(n²), greedy/local comparisons fail on circular wrap, and DP is not naturally suited. Monotonic stack with explicit circular array copy simulates circular traversal efficiently in O(n) time.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Monotonic stack with doubled array -> O(n) time [OK]

Hint: Circular array + next greater -> monotonic stack with doubling [OK]

Common Mistakes:

• Assuming greedy local comparisons suffice for circular arrays
• Thinking DP applies directly without circular simulation
• Believing brute force is optimal for large inputs

3. Given the following code for sliding window maximum, what is the returned list when nums = [2, 1, 3] and k = 2?

easy

A. [3, 3]

B. [2, 1]

C. [1, 3]

D. [2, 3]

Solution

1. Step 1: Trace iteration i=0

   dq empty, append index 0 (value 2). No output yet since i < k-1.

2. Step 2: Trace iteration i=1

   nums[1]=1 < nums[0]=2, so append index 1. Window size reached, max is nums[dq[0]]=2.

3. Step 3: Trace iteration i=2

   nums[2]=3 > nums[1]=1 pop index 1, nums[2]=3 > nums[0]=2 pop index 0, append index 2. Max is nums[2]=3.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Output matches expected sliding window max [OK]

Hint: Pop smaller elements before appending new index [OK]

Common Mistakes:

• Forgetting to remove out-of-window indices
• Appending max too early or late

4. Consider this buggy implementation of the pop method in the two-stack queue. What is the bug?

def pop(self) -> int:
    while self.push_stack:
        self.pop_stack.append(self.push_stack.pop())
    return self.pop_stack.pop()

medium

A. The push_stack should be cleared after transfer to avoid duplicates.

B. The pop_stack.pop() call should be replaced with pop_stack[-1] to peek instead of pop.

C. The transfer loop should only run if pop_stack is empty, otherwise elements are transferred every pop causing inefficiency.

D. The method should check if both stacks are empty before popping to avoid runtime errors.

Solution

1. Step 1: Identify transfer condition

   The code transfers elements from push_stack to pop_stack on every pop, regardless of pop_stack state.

2. Step 2: Understand impact

   This causes O(n) time on every pop, losing amortized O(1) efficiency.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Transfer only when pop_stack empty -> amortized O(1) [OK]

Hint: Transfer only if pop_stack empty to keep amortized O(1) [OK]

Common Mistakes:

• Transferring every pop causes O(n) pop time
• Not checking empty queue before pop

5. Suppose you want to implement a queue using two stacks, but now the queue must support a 'reuse' operation that re-enqueues the last dequeued element. Which modification ensures correctness and efficiency?

hard

A. Use a third stack to hold reused elements and merge it with push_stack during transfers.

B. After every pop, immediately push the popped element back onto pop_stack to allow reuse, effectively making pop a peek operation.

C. Clear both stacks and re-insert all elements including the reused element to maintain order.

D. Store the last dequeued element separately and push it back onto the push_stack when reuse is called, without changing pop_stack.

Solution

1. Step 1: Understand reuse operation

   Reuse means re-enqueueing the last dequeued element, so it should be treated as a new push.

2. Step 2: Choose efficient modification

   Storing the last popped element separately and pushing it onto push_stack on reuse preserves order and amortized efficiency.

3. Step 3: Analyze other options

   After every pop, immediately push the popped element back onto pop_stack to allow reuse, effectively making pop a peek operation, breaks queue semantics by not removing element. Clearing both stacks and re-inserting all elements including the reused element is inefficient. Using a third stack to hold reused elements and merging it with push_stack during transfers adds unnecessary complexity.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Reuse as push to push_stack keeps order and efficiency [OK]

Hint: Reuse = push last popped element onto push_stack [OK]

Common Mistakes:

• Trying to reuse by pushing onto pop_stack
• Rebuilding stacks on reuse causing inefficiency