Implement Queue Using Stacks

📋

Problem

Imagine you have two stacks of plates and want to simulate a queue behavior - first in, first out - using only these stacks.

Implement a queue using two stacks. The queue should support the following operations: push(x) to add element x to the back of the queue, pop() to remove the element from the front of the queue, peek() to get the front element, and empty() to check if the queue is empty.

1 ≤ number of operations ≤ 10^5All operations are valid (e.g., pop or peek will not be called on an empty queue).

Edge cases: pop on queue with one element → queue becomes emptypeek on queue with one element → returns that elementempty on newly created queue → returns true

</>

IDE

class MyQueue: def __init__(self): pass def push(self, x: int) -> None: pass def pop(self) -> int: pass def peek(self) -> int: pass def empty(self) -> bool: passclass MyQueue { public MyQueue() { } public void push(int x) { } public int pop() { return 0; } public int peek() { return 0; } public boolean empty() { return false; } }class MyQueue { public: MyQueue() { } void push(int x) { } int pop() { return 0; } int peek() { return 0; } bool empty() { return false; } };class MyQueue { constructor() { } push(x) { } pop() { return 0; } peek() { return 0; } empty() { return false; } }

class MyQueue:
    def __init__(self):
        # Write your solution here
        pass
    def push(self, x: int) -> None:
        pass
    def pop(self) -> int:
        pass
    def peek(self) -> int:
        pass
    def empty(self) -> bool:
        pass

class MyQueue {
    public MyQueue() {
        // Write your solution here
    }
    public void push(int x) {
    }
    public int pop() {
        return 0;
    }
    public int peek() {
        return 0;
    }
    public boolean empty() {
        return false;
    }
}

#include <stack>
using namespace std;

class MyQueue {
public:
    MyQueue() {
        // Write your solution here
    }
    void push(int x) {
    }
    int pop() {
        return 0;
    }
    int peek() {
        return 0;
    }
    bool empty() {
        return false;
    }
};

class MyQueue {
    constructor() {
        // Write your solution here
    }
    push(x) {
    }
    pop() {
        return 0;
    }
    peek() {
        return 0;
    }
    empty() {
        return false;
    }
}

Common Bugs to Avoid

Wrong: pop or peek returns last pushed element instead of frontNot transferring elements from push stack to pop stack before pop/peek✅ Add condition to transfer all elements from push stack to pop stack when pop stack is empty before pop/peek

Wrong: empty() returns false on new queueChecking only one stack for emptiness✅ Check both push and pop stacks for emptiness to determine if queue is empty

Wrong: pop() does not remove last element, empty() returns false after popping allPop stack not updated correctly after last pop✅ Ensure pop removes element from pop stack and empty checks both stacks after pop

Wrong: TLE on large inputUsing recursive pop or transferring elements on every pop causing O(n) per operation✅ Implement amortized O(1) approach by transferring elements only when pop stack is empty

✓

Test Cases

Focus on handling empty and single-element queues correctly.

Test your implementation with interleaved push and pop operations to catch order bugs.

Optimize your solution to achieve amortized O(1) time per operation.

t1_01basic

Input["push(1)","push(2)","peek()","pop()","empty()"]

Expected[1,1,false]

⏱ Performance - must finish in 2000ms

After pushing 1 and 2, peek returns 1 (front). Pop removes 1. empty returns false because 2 is still in queue.

💡 Think about how two stacks can simulate queue operations.

💡 Use one stack for incoming elements and another for outgoing elements.

💡 Transfer elements from push stack to pop stack only when pop stack is empty.

Why it failed: Basic case failed - likely pop or peek does not correctly transfer elements from push stack to pop stack. Fix by checking if pop stack is empty before transferring.

✓ Core queue operations implemented correctly with two stacks.

t1_02basic

Input["push(10)","push(20)","push(30)","pop()","peek()","empty()"]

Expected[10,20,false]

⏱ Performance - must finish in 2000ms

Push 10,20,30; pop removes 10; peek returns 20; empty returns false as queue has elements.

💡 Remember to only transfer elements when pop stack is empty.

💡 Pop removes from the front, which is the bottom of the push stack.

💡 Maintain two stacks: push stack for new elements, pop stack for front elements.

Why it failed: Pop or peek returns wrong element - likely missing transfer or incorrect stack usage. Fix by transferring all elements from push stack to pop stack when pop stack is empty.

✓ Queue behavior correctly maintained with multiple elements.

t2_01edge

Input["empty()"]

Expected[true]

⏱ Performance - must finish in 2000ms

Empty called on newly created queue returns true.

💡 Check if both stacks are empty to determine if queue is empty.

💡 Empty queue means no elements in either push or pop stack.

💡 Return true only if both stacks have zero size.

Why it failed: Empty returns false on new queue - likely only checking one stack. Fix by checking both push and pop stacks for emptiness.

✓ Empty correctly returns true for new queue.

t2_02edge

Input["push(42)","pop()","empty()"]

Expected[42,true]

⏱ Performance - must finish in 2000ms

Push one element, pop removes it, empty returns true as queue is now empty.

💡 Pop on single element should remove it and leave queue empty.

💡 Ensure pop stack is used correctly to remove front element.

💡 After pop, both stacks should be empty for empty() to return true.

Why it failed: Pop does not remove last element or empty returns false after pop. Fix by correctly popping from pop stack and updating empty check.

✓ Single element pop empties queue correctly.

t2_03edge

Input["push(5)","push(5)","push(5)","pop()","pop()","pop()","empty()"]

Expected[5,5,5,true]

⏱ Performance - must finish in 2000ms

All elements identical; popping all returns them in order; empty returns true after all removed.

💡 Identical elements should not affect order or correctness.

💡 Ensure pop stack transfers all elements correctly regardless of duplicates.

💡 Empty check must confirm both stacks are empty after all pops.

Why it failed: Pop returns wrong element or empty returns false after all pops. Fix by proper transfer and pop logic handling duplicates.

✓ Queue handles identical elements correctly.

t3_01corner

Input["push(1)","push(2)","pop()","push(3)","peek()","pop()","peek()"]

Expected[1,2,3]

⏱ Performance - must finish in 2000ms

Tests correct order after interleaved push and pop operations.

💡 Check that pop stack is only refilled when empty.

💡 After popping, pushing new elements should not disrupt order.

💡 Peek should always return front element from pop stack or transfer if empty.

Why it failed: Peek or pop returns wrong element after interleaved operations. Fix by transferring only when pop stack empty and maintaining order.

✓ Interleaved push/pop operations maintain correct queue order.

t3_02corner

Input["push(1)","push(2)","push(3)","pop()","pop()","pop()","empty()"]

Expected[1,2,3,true]

⏱ Performance - must finish in 2000ms

Tests full dequeue of all elements and empty returns true.

💡 Ensure pop stack empties correctly after all pops.

💡 Empty must check both stacks after all pops.

💡 No elements should remain after all pops.

Why it failed: Empty returns false after all pops or pop returns wrong element. Fix by clearing pop stack and checking both stacks for empty.

✓ Full dequeue empties queue correctly.

t3_03corner

Input["push(1)","push(2)","push(3)","peek()","pop()","peek()","pop()","peek()","pop()","empty()"]

Expected[1,1,2,2,3,3,true]

⏱ Performance - must finish in 2000ms

Tests repeated peek and pop calls to verify front element consistency.

💡 Peek should not remove elements, pop should.

💡 Pop stack must maintain correct front element after each pop.

💡 Peek after pop should update front correctly.

Why it failed: Peek returns wrong element after pop or pop removes wrong element. Fix by correctly managing pop stack and transferring only when empty.

✓ Peek and pop maintain consistent front element.

t4_01performance

Input["push(1)","push(2)","push(3)","push(4)","push(5)","push(6)","push(7)","push(8)","push(9)","push(10)","pop()","pop()","pop()","pop()","pop()","pop()","pop()","pop()","pop()","pop()"]

Expectednull

⏱ Performance - must finish in 2000ms

n=100000 operations (push and pop) must complete in 2s using amortized O(1) approach.

💡 Use two stacks to achieve amortized O(1) per operation.

💡 Avoid recursive or costly pop implementations.

💡 Transfer elements only when pop stack is empty.

Why it failed: TLE due to O(n) per pop or peek operation. Fix by using amortized O(1) two-stack approach with lazy transfer.

✓ Amortized O(1) complexity confirmed for large input.

Practice

1. Given the following Python code for the Basic Calculator, what is the value of result immediately after processing the character ')' at index 6 in the input string "(1+(2-3))"?

def calculate(s: str) -> int:
    stack = []
    result = 0
    sign = 1
    num = 0
    for i, c in enumerate(s):
        if c.isdigit():
            num = num * 10 + int(c)
        elif c in '+-':
            result += sign * num
            num = 0
            sign = 1 if c == '+' else -1
        elif c == '(':  # Push current result and sign
            stack.append(result)
            stack.append(sign)
            result = 0
            sign = 1
        elif c == ')':  # Add last number and combine
            result += sign * num
            num = 0
            result *= stack.pop()
            result += stack.pop()
    result += sign * num
    return result

easy

A. 0

B. 0

C. 0

D. 0

Solution

1. Step 1: Trace characters up to index 6

   Input: "(1+(2-3))" - i=0:'(' push 0 and 1, result=0, sign=1 - i=1:'1' num=1 - i=2:'+' result=0+1*1=1, num=0, sign=1 - i=3:'(' push 1 and 1, result=0, sign=1 - i=4:'2' num=2 - i=5:'-' result=0+1*2=2, num=0, sign=-1 - i=6:'3' num=3

2. Step 2: Process character at index 6 (')')

   At ')': result += sign*num = 2 + (-1)*3 = -1 num=0 result *= stack.pop() -> result *= 1 -> -1 result += stack.pop() -> -1 + 1 = 0

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Result after popping stack is 0 [OK]

Hint: Remember to apply sign*num before popping stack [OK]

Common Mistakes:

• Forgetting to add last number before popping stack

2. Consider the following buggy code snippet for the optimal calculator. Which line contains the subtle bug that causes incorrect results for expressions with negative division?

medium

A. Line with 'current_op = c' updating the operator

B. Line with 'last_num = last_num // current_num' (integer division without handling negatives)

C. Line with 'current_num = current_num * 10 + int(c)' parsing digits

D. Line with 'total += last_num' inside '+' case

Solution

1. Step 1: Identify division handling

   Integer division of negative numbers must truncate toward zero, not floor.

2. Step 2: Locate bug line

   The line 'last_num = last_num // current_num' does not handle negative last_num correctly, causing wrong results.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Correct negative division requires special handling, missing here [OK]

Hint: Negative division truncation requires special code [OK]

Common Mistakes:

• Ignoring negative division truncation
• Forgetting to add last_num at end
• Misparsing digits

3. Identify the bug in the following MinStack implementation using a single stack with encoded minimums:

medium

A. Line 'if diff < 0:' in pop should be 'if diff <= 0:' to handle zero differences correctly.

B. Line 'self.stack.append(diff)' should append x instead of diff to store actual values.

C. Line with 'if diff <= 0:' should be 'if diff < 0:' to avoid incorrect min updates on duplicates.

D. Line 'self.minVal = self.minVal - diff' in pop should add diff instead of subtracting.

Solution

1. Step 1: Analyze push condition

   The condition 'if diff <= 0:' updates minVal even when diff == 0, i.e., when new element equals current min.

2. Step 2: Understand impact

   Updating minVal on equal values causes minVal to be overwritten incorrectly, breaking min tracking when duplicates are popped.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Correct condition is 'diff < 0' to update minVal only on strictly smaller values [OK]

Hint: Only update minVal when new value is strictly less than current min [OK]

Common Mistakes:

• Using <= instead of < causes minVal errors with duplicates
• Incorrect pop minVal update
• Appending wrong values to stack

4. Consider the following buggy code for validating parentheses. Which line contains the subtle bug that can cause a runtime error or incorrect result?

def isValid(s: str) -> bool:
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}
    for char in s:
        if char in pairs.values():
            stack.append(char)
        elif char in pairs:
            if stack[-1] != pairs[char]:
                return False
            stack.pop()
        else:
            return False
    return not stack

medium

A. Line checking if stack[-1] != pairs[char]

B. Line popping from stack: stack.pop()

C. Line appending opening bracket: stack.append(char)

D. Line iterating over characters: for char in s

Solution

1. Step 1: Identify potential runtime errors

   Accessing stack[-1] without checking if stack is empty can cause IndexError if stack is empty.

2. Step 2: Check code logic

   Before comparing stack[-1], code must verify stack is not empty. Missing this check causes runtime error or incorrect acceptance.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing empty stack check before stack[-1] access [OK]

Hint: Always check stack emptiness before accessing top [OK]

Common Mistakes:

• Forgetting to check if stack is empty before popping or peeking

5. Suppose the problem is modified so that the 132 pattern subsequence can reuse elements multiple times (i.e., indices need not be strictly increasing). Which modification to the optimal algorithm correctly handles this variant?

hard

A. The monotonic stack approach cannot be adapted; a new approach using segment trees is needed

B. Use a brute force triple nested loop to check all triplets allowing repeated indices

C. Keep the same monotonic stack approach but iterate forwards instead of backwards

D. Modify the condition to allow non-strict inequalities and keep the same algorithm

Solution

1. Step 1: Understand the reuse variant

   Allowing reuse of elements means indices are not strictly increasing, breaking the subsequence definition and invalidating monotonic stack assumptions.

2. Step 2: Evaluate algorithm adaptability

   The monotonic stack relies on strict index ordering and cannot track repeated elements correctly; segment trees or other data structures are needed.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Monotonic stack fails on reuse variant; advanced data structures required [OK]

Hint: Monotonic stack requires strict index order [OK]

Common Mistakes:

• Trying to reuse monotonic stack unchanged
• Relaxing inequalities incorrectly
• Assuming brute force is only solution