Implement Queue using Stacks

LeetCode 232: Implement Queue using Stacks Solution & Explanation

Problem Overview

TL;DR: To achieve FIFO behavior using LIFO stacks efficiently, maintain two stacks—one for incoming elements and one for outgoing elements—and transfer data between them only when the outgoing stack is empty.

The problem requires us to simulate a Queue (First-In-First-Out) data structure using only Stacks (Last-In-First-Out). We need to implement standard queue operations—push, pop, peek, and empty—while adhering to the constraint that we can only use standard stack operations (push, pop, peek, size, empty). This is a classic design problem often found in technical interviews, specifically denoted as LeetCode 232.

Brute Force Approach for Implement Queue using Stacks

A naive approach to solving Implement Queue using Stacks is to ensure the elements are always stored in FIFO order inside a single primary stack. To achieve this, every time we push a new element, we must reorder the entire data structure.

Naive Logic

1. Push:
   • Transfer all elements from the primary stack to a temporary helper stack.
   • Push the new element onto the empty primary stack (it is now at the bottom).
   • Transfer all elements back from the helper stack to the primary stack.
2. Pop/Peek: Simply perform the operation on the top of the primary stack.

Pseudo-code

function push(x):
    while primary_stack is not empty:
        helper_stack.push(primary_stack.pop())
    
    primary_stack.push(x)
    
    while helper_stack is not empty:
        primary_stack.push(helper_stack.pop())

Analysis

• Time Complexity: The push operation is $O(n)$ because every element currently in the queue must be moved twice for every insertion. pop is $O(1)$.
• Why it fails: While correct in terms of output, this approach is inefficient. If we perform $n$ push operations, the total time complexity becomes $O(n^2)$. The problem's follow-up explicitly asks for an amortized $O(1)$ time complexity for operations, which this brute force method fails to provide.

Algorithm Strategy: Design Patterns

We will implement the MyQueue class using two stacks: inputStack and outputStack.

1. State Maintenance:

   • inputStack: Used exclusively for push(x) operations.
   • outputStack: Used exclusively for pop() and peek() operations.

2. Push Operation:

   • Simply push the element onto inputStack. This is an $O(1)$ operation.

3. Pop and Peek Operations:

   • Check if outputStack is empty.
   • If outputStack is not empty, the top element is the correct front of the queue. Proceed to pop or peek.
   • If outputStack is empty, we must transfer elements. While inputStack is not empty, pop from inputStack and push onto outputStack.
   • After the transfer, the oldest element is now at the top of outputStack.

4. Empty Operation:

   • The queue is empty only if both inputStack and outputStack are empty.

This strategy ensures that the expensive transfer operation happens infrequently, averaging out to constant time over a sequence of operations.

Execution Flow

Consider the following sequence of operations: push(1), push(2), peek(), push(3), pop(), pop().

1. push(1):

   • inputStack: [1]
   • outputStack: []

2. push(2):

   • inputStack: [1, 2] (Top is 2)
   • outputStack: []

3. peek():

   • outputStack is empty. Transfer phase begins.
   • Pop 2 from input, push to output.
   • Pop 1 from input, push to output.
   • inputStack: []
   • outputStack: [2, 1] (Top is 1)
   • Return top of outputStack (1).

4. push(3):

   • inputStack: [3]
   • outputStack: [2, 1]

5. pop():

   • outputStack is not empty.
   • Pop from outputStack. Returns 1.
   • outputStack: [2] (Top is 2)

6. pop():

   • outputStack is not empty.
   • Pop from outputStack. Returns 2.
   • outputStack: []

Proof of Correctness

The correctness relies on the invariant that outputStack contains the oldest elements in FIFO order, while inputStack contains newer elements in LIFO order.

1. Elements are only added to inputStack.
2. Elements are only removed from inputStack to go immediately into outputStack.
3. Because a stack reverses order, moving from inputStack to outputStack reverses the order.
   • If inputStack has elements $[e_n, \dots, e_1]$ (where $e_1$ is oldest), popping them yields $e_n, e_{n-1}, \dots$.
   • Pushing them into outputStack results in outputStack having $[e_1, \dots, e_n]$ (where $e_1$ is at the top).
4. We only refill outputStack when it is strictly empty. This ensures we never place newer elements (from inputStack) on top of older elements still waiting in outputStack.
5. Therefore, the top of outputStack is always the oldest available element in the system.

Pattern Reuse Notes

The Design Patterns pattern used here is applicable to several other popular interview questions:

• LeetCode 146: LRU Cache: Requires combining a Hash Map and a Doubly Linked List to achieve $O(1)$ constraints, similar to how we combined two stacks here.
• LeetCode 155: Min Stack: Uses an auxiliary stack to track the minimum value state alongside the main data, maintaining synchronization between two data structures.
• LeetCode 225: Implement Stack using Queues: The inverse of this problem. It requires managing two queues to simulate LIFO behavior.
• LeetCode 251: Flatten 2D Vector: Involves maintaining pointers or iterators within a wrapper class to flatten a complex structure into a linear interface.

Reference Implementation

C++ Solution for LeetCode 232

1#include <stack>
2
3class MyQueue {
4private:
5    std::stack<int> inputStack;
6    std::stack<int> outputStack;
7
8    // Helper method to move elements if outputStack is empty
9    void moveInputToOutput() {
10        if (outputStack.empty()) {
11            while (!inputStack.empty()) {
12                outputStack.push(inputStack.top());
13                inputStack.pop();
14            }
15        }
16    }
17
18public:
19    MyQueue() {
20        // Constructors for stacks are called automatically
21    }
22    
23    void push(int x) {
24        inputStack.push(x);
25    }
26    
27    int pop() {
28        moveInputToOutput();
29        int topElement = outputStack.top();
30        outputStack.pop();
31        return topElement;
32    }
33    
34    int peek() {
35        moveInputToOutput();
36        return outputStack.top();
37    }
38    
39    bool empty() {
40        return inputStack.empty() && outputStack.empty();
41    }
42};

Java Solution for LeetCode 232

1import java.util.Stack;
2
3class MyQueue {
4    private Stack<Integer> inputStack;
5    private Stack<Integer> outputStack;
6
7    public MyQueue() {
8        inputStack = new Stack<>();
9        outputStack = new Stack<>();
10    }
11    
12    public void push(int x) {
13        inputStack.push(x);
14    }
15    
16    public int pop() {
17        moveInputToOutput();
18        return outputStack.pop();
19    }
20    
21    public int peek() {
22        moveInputToOutput();
23        return outputStack.peek();
24    }
25    
26    public boolean empty() {
27        return inputStack.isEmpty() && outputStack.isEmpty();
28    }
29
30    // Helper method to handle the lazy transfer
31    private void moveInputToOutput() {
32        if (outputStack.isEmpty()) {
33            while (!inputStack.isEmpty()) {
34                outputStack.push(inputStack.pop());
35            }
36        }
37    }
38}

Python Solution for LeetCode 232

1class MyQueue:
2
3    def __init__(self):
4        # Python lists can be used as stacks
5        # append() acts as push, pop() acts as pop from top
6        self.input_stack = []
7        self.output_stack = []
8
9    def push(self, x: int) -> None:
10        self.input_stack.append(x)
11
12    def pop(self) -> int:
13        self._move_input_to_output()
14        return self.output_stack.pop()
15
16    def peek(self) -> int:
17        self._move_input_to_output()
18        return self.output_stack[-1]
19
20    def empty(self) -> bool:
21        return not self.input_stack and not self.output_stack
22
23    def _move_input_to_output(self):
24        """
25        Moves elements from input_stack to output_stack only if
26        output_stack is empty.
27        """
28        if not self.output_stack:
29            while self.input_stack:
30                self.output_stack.append(self.input_stack.pop())