Implement Queue using Stacks

Description

Implement a first-in, first-out (FIFO) queue using only two stacks. The implemented queue should support all the standard queue operations:

push(x): Push element x to the back of the queue.
pop(): Remove the element from the front of the queue and return it.
peek(): Return the element at the front of the queue without removing it.
empty(): Return true if the queue is empty, false otherwise.

You must use only standard stack operations: push to top, peek/pop from top, size, and is-empty. You may not use any other data structure operations.

A stack is last-in, first-out (LIFO), while a queue is first-in, first-out (FIFO). The challenge is bridging this fundamental ordering difference using only stacks.

Examples

Example 1

Input:

["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]

Output:

[null, null, null, 1, 1, false]

Explanation:

MyQueue myQueue = new MyQueue(); — Create an empty queue.
myQueue.push(1); — Queue becomes [1]. The element 1 is at the front.
myQueue.push(2); — Queue becomes [1, 2]. Element 1 is still at the front, 2 is at the back.
myQueue.peek(); — Returns 1, the front element. Queue remains [1, 2].
myQueue.pop(); — Returns 1 and removes it. Queue becomes [2].
myQueue.empty(); — Returns false because the queue still has element 2.

Example 2

Input:

["MyQueue", "push", "push", "push", "pop", "push", "pop", "pop", "empty"]
[[], [10], [20], [30], [], [40], [], [], []]

Output:

[null, null, null, null, 10, null, 20, 30, false]

Explanation:

Push 10, 20, 30 → queue is [10, 20, 30].
Pop → returns 10 (the first element pushed). Queue is [20, 30].
Push 40 → queue is [20, 30, 40].
Pop → returns 20. Queue is [30, 40].
Pop → returns 30. Queue is [40].
Empty → returns false because 40 is still in the queue.

Constraints

1 ≤ x ≤ 9
At most 100 calls will be made to push, pop, peek, and empty.
All calls to pop and peek are valid (the queue is non-empty when called).

Editorial

Brute Force

Intuition

The core challenge is that a stack gives us elements in LIFO order (last in, first out), but a queue needs FIFO order (first in, first out). Elements come out of a stack in reverse order compared to what a queue needs.

The most direct idea is: every time we push a new element, rearrange all existing elements so the oldest element is always on top of the main stack. This way, pop and peek are simple — just look at the top.

Here's the process for push(x):

Move all elements from stack s1 to a helper stack s2 (this reverses their order).
Push the new element x onto the now-empty s1.
Move everything back from s2 to s1 (reverses again, placing x at the bottom).

Think of it like a stack of plates. To add a new plate at the very bottom (so it's served last), you move all plates to a side table, put the new plate down, then stack all the plates back on top. Expensive for adding, but now grabbing the next plate to serve (pop) is instant.

Step-by-Step Explanation

Let's trace through: push(1), push(2), push(3), peek(), pop().

Step 1: push(1). s1 is empty, so just push 1 onto s1. s1 = [1] (top is 1). s2 = [].

Step 2: push(2). Move all from s1 to s2: pop 1 from s1, push 1 onto s2. s1 = [], s2 = [1].

Step 3: Push 2 onto empty s1. s1 = [2], s2 = [1].

Step 4: Move all from s2 back to s1: pop 1 from s2, push 1 onto s1. s1 = [2, 1] (top is 1), s2 = []. Element 1 is on top (front of queue), 2 is at bottom (back of queue).

Step 5: push(3). Move all from s1 to s2: pop 1, push to s2. Pop 2, push to s2. s1 = [], s2 = [1, 2] (top is 2).

Step 6: Push 3 onto empty s1. s1 = [3], s2 = [1, 2].

Step 7: Move all from s2 back: pop 2, push to s1. Pop 1, push to s1. s1 = [3, 2, 1] (top is 1), s2 = []. Now s1 has elements in queue order from top: 1, 2, 3.

Step 8: peek() → return top of s1 = 1. The first element pushed is at the top. Correct!

Step 9: pop() → pop top of s1 = 1. s1 = [3, 2] (top is 2). Returns 1.

Brute Force — Costly Push with Two Stacks — Watch how every push operation transfers all elements between two stacks to keep the oldest element on top, making pop and peek instant.

Algorithm

push(x):

While s1 is not empty, pop from s1 and push onto s2
Push x onto s1
While s2 is not empty, pop from s2 and push onto s1

pop():

Pop and return the top element of s1

peek():

Return the top element of s1 without removing

empty():

Return whether s1 is empty

Code

class MyQueue {
    stack<int> s1, s2;
public:
    MyQueue() {}
    
    void push(int x) {
        // Move all elements from s1 to s2
        while (!s1.empty()) {
            s2.push(s1.top());
            s1.pop();
        }
        // Push new element onto s1
        s1.push(x);
        // Move everything back from s2 to s1
        while (!s2.empty()) {
            s1.push(s2.top());
            s2.pop();
        }
    }
    
    int pop() {
        int front = s1.top();
        s1.pop();
        return front;
    }
    
    int peek() {
        return s1.top();
    }
    
    bool empty() {
        return s1.empty();
    }
};

class MyQueue:
    def __init__(self):
        self.s1 = []
        self.s2 = []
    
    def push(self, x: int) -> None:
        # Move all from s1 to s2
        while self.s1:
            self.s2.append(self.s1.pop())
        # Push new element
        self.s1.append(x)
        # Move all back from s2 to s1
        while self.s2:
            self.s1.append(self.s2.pop())
    
    def pop(self) -> int:
        return self.s1.pop()
    
    def peek(self) -> int:
        return self.s1[-1]
    
    def empty(self) -> bool:
        return len(self.s1) == 0

class MyQueue {
    private Stack<Integer> s1;
    private Stack<Integer> s2;
    
    public MyQueue() {
        s1 = new Stack<>();
        s2 = new Stack<>();
    }
    
    public void push(int x) {
        while (!s1.isEmpty()) {
            s2.push(s1.pop());
        }
        s1.push(x);
        while (!s2.isEmpty()) {
            s1.push(s2.pop());
        }
    }
    
    public int pop() {
        return s1.pop();
    }
    
    public int peek() {
        return s1.peek();
    }
    
    public boolean empty() {
        return s1.isEmpty();
    }
}

Complexity Analysis

Time Complexity:

push(x): O(n) — We move all n existing elements from s1 to s2, then back. That's 2n pops and 2n pushes plus the new element push, so O(n) total.
pop(): O(1) — Just pop the top of s1.
peek(): O(1) — Just read the top of s1.
empty(): O(1) — Just check if s1 is empty.

Space Complexity: O(n)

Both stacks together hold exactly n elements at any time. During push, we temporarily use s2, but the total element count stays at n+1 (including the new element).

Why This Approach Is Not Efficient

The brute force makes every push O(n) by transferring all elements back and forth between the two stacks. If we perform n pushes, the total work is 1 + 2 + 3 + ... + n = O(n²). This is wasteful because we're repeatedly moving the same elements for every single new insertion.

The fundamental problem is that we're maintaining the queue order in s1 at all times — eagerly rearranging after every push. But do we really need the queue order until someone asks for the front element?

Key insight: What if we lazily delay the reordering? Instead of rearranging on every push, we can push onto one stack (O(1)) and only transfer to the other stack when a pop or peek is needed. If the output stack still has elements from a previous transfer, we don't even need to transfer at all. This lazy strategy gives us amortized O(1) per operation.

Optimal Approach - Lazy Transfer (Amortized O(1))

Intuition

Instead of rearranging on every push, we use the two stacks with different roles:

Input stack (s1): Where new elements are pushed. Push is always O(1).
Output stack (s2): Where elements are popped/peeked from. Elements here are in correct FIFO order.

The clever trick: we only transfer elements from s1 to s2 when s2 is empty and we need to pop or peek. When we dump s1 into s2, the reversal that happens naturally (because stacks reverse order) puts elements in exactly the right FIFO sequence!

Think of two buckets connected by a pipe. New items go into the 'input bucket' (s1). When you need to take items out but the 'output bucket' (s2) is empty, you flip the input bucket upside down — all items pour into the output bucket in reversed order, which is exactly queue order. You keep taking from the output bucket until it's empty, then flip again.

Each element moves from s1 to s2 exactly once in its lifetime. So over n operations, the total transfer work is at most n — giving amortized O(1) per operation.

Step-by-Step Explanation

Let's trace: push(1), push(2), push(3), pop(), push(4), pop(), pop().

Step 1: push(1). Push 1 onto s1. s1 = [1], s2 = []. Simple O(1) push.

Step 2: push(2). Push 2 onto s1. s1 = [1, 2] (top=2), s2 = []. Still O(1).

Step 3: push(3). Push 3 onto s1. s1 = [1, 2, 3] (top=3), s2 = []. All pushes O(1).

Step 4: pop(). Need front element. s2 is empty, so transfer all from s1 to s2: pop 3→s2, pop 2→s2, pop 1→s2. Now s1 = [], s2 = [3, 2, 1] (top=1). The reversal gives us queue order!

Step 5: Pop from s2: returns 1. s2 = [3, 2] (top=2). Correct — 1 was pushed first.

Step 6: push(4). Push 4 onto s1. s1 = [4], s2 = [3, 2]. Note: we do NOT transfer. Both stacks hold elements simultaneously.

Step 7: pop(). Need front. s2 is NOT empty (has [3, 2]), so just pop from s2: returns 2. s2 = [3]. No transfer needed — s2 still has elements in correct order.

Step 8: pop(). s2 is NOT empty (has [3]), pop from s2: returns 3. s2 = []. Correct order: 1, 2, 3 were popped.

Note: Element 4 is still in s1 = [4]. The next pop would trigger a transfer of s1 to s2.

Lazy Transfer — Amortized O(1) Queue Using Two Stacks — Watch how pushes go to the input stack (s1) in O(1), and elements only transfer to the output stack (s2) when s2 is empty and a pop/peek is needed. Each element transfers exactly once.

Algorithm

push(x):

Push x onto s1 (input stack)

pop():

If s2 is empty:
- While s1 is not empty, pop from s1 and push onto s2
Pop and return the top of s2

peek():

If s2 is empty:
- While s1 is not empty, pop from s1 and push onto s2
Return the top of s2 (without removing)

empty():

Return true if both s1 and s2 are empty

Code

class MyQueue {
    stack<int> s1, s2;
public:
    MyQueue() {}
    
    void push(int x) {
        s1.push(x);
    }
    
    int pop() {
        if (s2.empty()) {
            while (!s1.empty()) {
                s2.push(s1.top());
                s1.pop();
            }
        }
        int front = s2.top();
        s2.pop();
        return front;
    }
    
    int peek() {
        if (s2.empty()) {
            while (!s1.empty()) {
                s2.push(s1.top());
                s1.pop();
            }
        }
        return s2.top();
    }
    
    bool empty() {
        return s1.empty() && s2.empty();
    }
};

class MyQueue:
    def __init__(self):
        self.s1 = []  # input stack
        self.s2 = []  # output stack
    
    def push(self, x: int) -> None:
        self.s1.append(x)
    
    def pop(self) -> int:
        if not self.s2:
            while self.s1:
                self.s2.append(self.s1.pop())
        return self.s2.pop()
    
    def peek(self) -> int:
        if not self.s2:
            while self.s1:
                self.s2.append(self.s1.pop())
        return self.s2[-1]
    
    def empty(self) -> bool:
        return not self.s1 and not self.s2

class MyQueue {
    private Stack<Integer> s1;
    private Stack<Integer> s2;
    
    public MyQueue() {
        s1 = new Stack<>();
        s2 = new Stack<>();
    }
    
    public void push(int x) {
        s1.push(x);
    }
    
    public int pop() {
        if (s2.isEmpty()) {
            while (!s1.isEmpty()) {
                s2.push(s1.pop());
            }
        }
        return s2.pop();
    }
    
    public int peek() {
        if (s2.isEmpty()) {
            while (!s1.isEmpty()) {
                s2.push(s1.pop());
            }
        }
        return s2.peek();
    }
    
    public boolean empty() {
        return s1.isEmpty() && s2.isEmpty();
    }
}

Complexity Analysis

Time Complexity:

push(x): O(1) — Always a single stack push.
pop(): Amortized O(1), worst-case O(n) — In the worst case, we transfer all n elements from s1 to s2. But each element is transferred at most once in its entire lifetime (it enters s1 once and leaves to s2 once). So across n operations, total transfer work is O(n), meaning each operation costs O(1) amortized.
peek(): Amortized O(1), worst-case O(n) — Same reasoning as pop.
empty(): O(1) — Two isEmpty checks.

Why amortized O(1)? Consider any sequence of n push and n pop operations. Each element is pushed onto s1 once (cost 1), popped from s1 once (cost 1), pushed onto s2 once (cost 1), and popped from s2 once (cost 1). Total cost across all operations: 4n. Cost per operation: 4n / 2n = O(1).

Space Complexity: O(n)

Both stacks together hold at most n elements at any time.

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

Implement Queue using Stacks

Description

Examples

Example 1

Example 2

Constraints

Editorial

Brute Force

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Optimal Approach - Lazy Transfer (Amortized O(1))

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis