Implement Queue Using Stacks

▶

Steps

setup

Initialize the Queue

Create an empty queue with two empty stacks: push_stack and pop_stack.

💡 Starting with empty stacks sets the foundation for all future operations.

Line:

def __init__(self):
    self.push_stack = []
    self.pop_stack = []

💡 The queue is represented internally by two stacks, both initially empty.

insert

Push 1 onto push_stack

Push the element 1 onto the push_stack to enqueue it.

💡 New elements are always added to push_stack to maintain insertion order.

Line:

def push(self, x: int) -> None:
    self.push_stack.append(x)

💡 The push_stack now holds the newest element at the top.

insert

Push 2 onto push_stack

Push the element 2 onto the push_stack, placing it above 1.

💡 Elements are stacked in order of arrival, newest on top.

Line:

def push(self, x: int) -> None:
    self.push_stack.append(x)

💡 push_stack now contains [1, 2] with 2 on top, preserving insertion order.

expand

Peek operation: pop_stack empty, transfer first element

pop_stack is empty, so pop the top element (2) from push_stack to transfer it.

💡 Transferring reverses order, so oldest element is on top of pop_stack for peek/pop.

Line:

def peek(self) -> int:
    if not self.pop_stack:
        while self.push_stack:
            self.pop_stack.append(self.push_stack.pop())

💡 This transfer is key to simulating queue order using stacks.

expand

Continue transferring second element to pop_stack

Push the popped element (2) onto pop_stack.

💡 Each popped element from push_stack is pushed onto pop_stack to reverse order.

Line:

while self.push_stack:
    self.pop_stack.append(self.push_stack.pop())

💡 pop_stack starts to build with elements in reversed order.

expand

Continue transferring elements to pop_stack

Pop 1 from push_stack and push it onto pop_stack, completing the transfer.

💡 All elements must be moved to pop_stack to maintain correct dequeue order.

Line:

while self.push_stack:
    self.pop_stack.append(self.push_stack.pop())

💡 pop_stack now has [2, 1] with 1 on top, the queue front.

compare

Peek returns front element from pop_stack

Return the top element of pop_stack (1) as the front of the queue.

💡 peek returns the oldest element, which is now on top of pop_stack.

Line:

return self.pop_stack[-1]

💡 The top of pop_stack represents the queue front after transfer.

delete

Pop removes front element from pop_stack

Pop the top element (1) from pop_stack, removing the front of the queue.

💡 Pop removes the oldest element, simulating dequeue.

Line:

return self.pop_stack.pop()

💡 pop_stack now holds [2], so next front is 2.

compare

Empty check: both stacks not empty

Check if both push_stack and pop_stack are empty to determine if queue is empty.

💡 Queue is empty only if both stacks are empty.

Line:

return not self.push_stack and not self.pop_stack

💡 Since pop_stack has [2], queue is not empty.

reconstruct

Final state: queue contains element 2

The queue now contains only element 2, represented by pop_stack holding [2].

💡 Final state shows the queue's internal stacks after all operations.

💡 The queue front is 2, confirming correct order preservation.

class MyQueue:
    def __init__(self):  # STEP 1
        self.push_stack = []
        self.pop_stack = []

    def push(self, x: int) -> None:  # STEP 2,3
        self.push_stack.append(x)

    def pop(self) -> int:  # STEP 4-8
        if not self.pop_stack:  # STEP 4
            while self.push_stack:  # STEP 4,5,6
                self.pop_stack.append(self.push_stack.pop())
        return self.pop_stack.pop()  # STEP 8

    def peek(self) -> int:  # STEP 4-7
        if not self.pop_stack:  # STEP 4
            while self.push_stack:  # STEP 4,5,6
                self.pop_stack.append(self.push_stack.pop())
        return self.pop_stack[-1]  # STEP 7

    def empty(self) -> bool:  # STEP 9
        return not self.push_stack and not self.pop_stack

# Driver code
if __name__ == '__main__':
    q = MyQueue()  # STEP 1
    q.push(1)     # STEP 2
    q.push(2)     # STEP 3
    print(q.peek())  # STEP 7
    print(q.pop())   # STEP 8
    print(q.empty()) # STEP 9

📊

Implement Queue Using Stacks - Watch the Algorithm Execute, Step by Step

Watching each stack operation and transfer step reveals how the queue order is preserved using stacks, which is not obvious from code alone.

no_op

Stack (top→bottom)

empty

pushElement[0]: 1

Stack (top→bottom)

1

↑ pushed: 1

pushElement[1]: 2

Stack (top→bottom)

2

1

↑ pushed: 2

pop

Stack (top→bottom)

1

↓ popped: [2]

push

Stack (top→bottom)

2

↑ pushed: 2

pop

Stack (top→bottom)

1

2

↓ popped: [1]

peekElement[2]: 1

Stack (top→bottom)

1

2

Contributes: 1

popElement[3]: 1

Stack (top→bottom)

2

↓ popped: [1]

Contributes: 1

no_op

Stack (top→bottom)

2

Contributes: false

no_op

Stack (top→bottom)

2

Key Takeaways

✓ Two stacks can simulate a queue by using one stack for pushing and another for popping, with a transfer step reversing order.

This reversal step is not obvious from code but is critical to preserving queue order.

✓ The transfer from push_stack to pop_stack happens only when pop_stack is empty, making pop and peek operations amortized O(1).

Seeing the transfer visually clarifies why the costly operation is infrequent.

✓ Empty check requires both stacks to be empty, reflecting the queue's true emptiness state.

This condition is subtle and easy to miss without seeing both stacks' states.

Practice

1. Consider the following Python code implementing the Remove K Digits algorithm. What is the final returned value when calling removeKdigits("10200", 1)?

easy

A. "0"

B. "100"

C. "200"

D. "2000"

Solution

1. Step 1: Trace builder and k during iteration

   Digits: '1', '0', '2', '0', '0' - '1': builder = ['1'], k=1 - '0': '1' > '0', pop '1', k=0, builder = [] - Append '0': builder = ['0'] - '2': builder = ['0', '2'] - '0': '2' > '0', but k=0, no pop - Append '0': builder = ['0', '2', '0'] - '0': builder = ['0', '2', '0', '0']

2. Step 2: Remove leading zeros and finalize

   k=0, so no slice. Join builder: '0200'. Strip leading zeros: '200'. Return '200'.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches expected minimal number after removing one digit [OK]

Hint: Pop digits while next digit is smaller and k>0 [OK]

Common Mistakes:

• Forgetting to strip leading zeros
• Removing wrong digits due to off-by-one in loop

2. Consider the following buggy code for asteroid collision. Which line contains the subtle bug that causes incorrect behavior on equal size asteroids?

def asteroidCollision(asteroids):
    stack = []
    for a in asteroids:
        alive = True
        while alive and stack and stack[-1] > 0 and a < 0:
            if stack[-1] < -a:
                stack.pop()
            elif stack[-1] == -a:
                alive = False
            else:
                alive = False
        if alive:
            stack.append(a)
    return stack

medium

A. Line with 'stack.pop()' inside 'if stack[-1] < -a:'

B. Line with 'while alive and stack and stack[-1] > 0 and a < 0:' condition

C. Line with 'alive = False' inside 'elif stack[-1] == -a:'

D. Line with 'stack.append(a)' after the while loop

Solution

1. Step 1: Identify behavior on equal size asteroids

   When sizes are equal, both asteroids should explode (pop from stack and not append current).

2. Step 2: Check code for equal size case

   In the buggy code, stack.pop() is missing when sizes are equal, so the top asteroid remains incorrectly.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Missing stack.pop() causes incorrect survival of equal asteroid [OK]

Hint: Equal size asteroids both must be removed [OK]

Common Mistakes:

• Forgetting to pop stack on equal size
• Appending asteroid after it exploded
• Incorrect while loop condition

3. The following code attempts to compute the largest rectangle area in a histogram using a monotonic stack. Identify the line containing the subtle bug that causes incorrect area calculation in some cases.

def largestRectangleArea(heights):
    n = len(heights)
    left = [-1] * n
    right = [n] * n
    stack = []

    for i in range(n):
        while stack and heights[stack[-1]] >= heights[i]:
            stack.pop()
        left[i] = stack[-1] if stack else -1
        stack.append(i)

    stack.clear()

    for i in range(n - 1, -1, -1):
        while stack and heights[stack[-1]] >= heights[i]:
            stack.pop()
        right[i] = stack[-1] if stack else n
        stack.append(i)

    max_area = 0
    for i in range(n):
        width = right[i] - left[i] - 1
        area = heights[i] * width
        max_area = max(max_area, area)
    return max_area

medium

A. Line with 'while stack and heights[stack[-1]] >= heights[i]:' in right boundary computation

B. Line with 'stack.clear()' before computing right boundaries

C. Line with 'width = right[i] - left[i] - 1' in area calculation

D. Line with 'while stack and heights[stack[-1]] > heights[i]:' in left boundary computation

Solution

1. Step 1: Compare left boundary condition with right boundary

   Left boundary uses '>=' but right boundary also uses '>='; originally left boundary used '>' causing inconsistency.

2. Step 2: Identify impact of using '>' instead of '>='

   Using '>' misses popping bars equal in height, leading to wrong left boundaries and smaller area.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Changing '>' to '>=' in left boundary fixes the bug [OK]

Hint: Use consistent '>=' in both boundary computations [OK]

Common Mistakes:

• Mixing '>' and '>=' causing inconsistent boundaries
• Forgetting to clear stack before right boundary pass

4. Consider this buggy code for the stock span problem. Which line contains the subtle bug that causes incorrect spans when prices are equal?

medium

A. Line 9: span calculation does not add 1 when stack is not empty

B. Line 11: appending price after appending index to stack

C. Line 6: while condition uses '<' instead of '<='

D. Line 7: popping from stack without checking if empty

Solution

1. Step 1: Identify the bug in while condition

   The condition uses '<' instead of '<=', so equal prices are not popped, causing incorrect spans.

2. Step 2: Confirm other lines are correct

   Span calculation correctly handles empty stack. Appending order is correct. Stack emptiness is checked before popping.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Using '<=' ensures equal prices are popped for correct spans [OK]

Hint: Use '<=' in while to pop equal or smaller prices [OK]

Common Mistakes:

• Using '<' causes incorrect spans for equal prices
• Misplaced span calculation

5. Suppose the problem is modified so that digits can be removed multiple times (i.e., you can remove the same digit repeatedly if it appears multiple times), or the input string can contain non-digit characters. Which modification to the original algorithm is necessary to handle these changes correctly?

hard

A. Use a frequency map to track digit counts and remove digits greedily based on frequency

B. Switch to a brute force approach generating all subsequences since greedy no longer applies

C. Preprocess input to filter out non-digit characters and apply the same monotonic stack algorithm without changes

D. Modify the stack to allow re-insertion of digits and skip non-digit characters during iteration

Solution

1. Step 1: Analyze impact of repeated removals and non-digit chars

   Allowing multiple removals of the same digit requires the stack to handle re-insertion or multiple passes. Non-digit chars must be skipped to avoid errors.

2. Step 2: Identify necessary algorithm modification

   The stack must be adapted to allow re-insertion or multiple removals, and iteration must skip non-digit characters to maintain correctness.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Handling input sanitization and stack flexibility is key for this variant [OK]

Hint: Stack must handle re-insertions and skip invalid chars [OK]

Common Mistakes:

• Assuming original algorithm works unchanged
• Ignoring input sanitization
• Switching to brute force unnecessarily