Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Implement Queue using Stacks

EASYProblemSolveExternal Links

Description

Design a data structure that behaves like a queue — where the first element added is the first one removed (First-In-First-Out) — but you may only use stacks internally. A stack is the opposite: the last element added is the first one removed (Last-In-First-Out).

Your task is to implement the MyQueue class with these four operations:

  • void push(int x) — Adds element x to the back of the queue.
  • int pop() — Removes the element from the front of the queue and returns it.
  • int peek() — Returns the element at the front of the queue without removing it.
  • boolean empty() — Returns true if the queue has no elements, false otherwise.

You must use only standard stack operations: push to top, pop from top, peek at top, check size, and check if empty. You may use at most two 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].
  • myQueue.push(2); — Queue becomes [1, 2]. The leftmost element (1) is the front.
  • myQueue.peek(); — Returns 1 because 1 is at the front of the queue.
  • myQueue.pop(); — Returns 1 and removes it. Queue becomes [2].
  • myQueue.empty(); — Returns false because the queue still contains one element.

Example 2

Input:
["MyQueue", "push", "push", "push", "pop", "push", "peek", "pop", "pop"]
[[], [5], [3], [7], [], [9], [], [], []]

Output: [null, null, null, null, 5, null, 3, 3, 7]

Explanation:

  • push(5), push(3), push(7) — Queue becomes [5, 3, 7].
  • pop() — Returns 5 (front of queue). Queue becomes [3, 7].
  • push(9) — Queue becomes [3, 7, 9].
  • peek() — Returns 3 (current front) without removing it.
  • pop() — Returns 3. Queue becomes [7, 9].
  • pop() — Returns 7. Queue becomes [9].

Notice elements always come out in the order they were pushed — first in, first out.

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 never empty when these are called).

Editorial

Brute Force

Intuition

Imagine you have two buckets (stacks) and a line of people (queue) to manage. The simplest idea is to make sure one bucket always holds everyone in perfect queue order — the person who arrived first is sitting right on top, ready to leave.

To achieve this, every time a new person arrives (push), you temporarily move everyone from the main bucket into the helper bucket, place the newcomer at the bottom of the main bucket, then move everyone back on top. This way the main bucket always has the oldest person on top.

Popping and peeking become trivial — just look at or remove the top of the main bucket. The downside is that every single push requires moving all existing elements twice: once into the helper and once back. This makes push expensive.

Step-by-Step Explanation

Let us trace through the operations push(1), push(2), pop() using the costly push approach. We maintain two stacks: s1 (the main stack that keeps queue order with front on top) and s2 (a temporary helper).

Step 1: Initialize two empty stacks.

  • s1 = [], s2 = []

Step 2: push(1). s1 is empty, so there is nothing to transfer. Push 1 onto s1.

  • s1 = [1], s2 = []

Step 3: push(2) begins. s1 has one element. Transfer all from s1 to s2: pop 1 from s1, push onto s2.

  • s1 = [], s2 = [1]

Step 4: Push 2 onto the now-empty s1. The new element goes to the bottom position.

  • s1 = [2], s2 = [1]

Step 5: Transfer everything back from s2 to s1: pop 1 from s2, push onto s1.

  • s1 = [2, 1], s2 = []
  • Notice: s1 now has 1 on top (the queue front) and 2 at the bottom (the queue back). Queue order is preserved.

Step 6: pop(). Simply pop from the top of s1. The top element is 1, which is the oldest element — exactly the queue front.

  • Returns 1. s1 = [2], s2 = []

Step 7: After the pop, queue contains only [2]. Element 1 was pushed first and popped first — FIFO order achieved using LIFO stacks.

Brute Force — Costly Push with Eager Transfer — Watch how every push operation transfers all existing elements to a helper stack and back, ensuring the main stack always maintains queue order with the front element on top.

Algorithm

  1. Maintain two stacks: s1 (main) and s2 (helper).
  2. push(x):
    a. While s1 is not empty, pop each element from s1 and push it onto s2.
    b. Push x onto s1 (it now sits at the bottom position).
    c. While s2 is not empty, pop each element from s2 and push it back onto s1.
    d. After this, s1 has x at the bottom and all previous elements on top in their original queue order.
  3. pop(): Pop and return the top element of s1. It is the queue front.
  4. peek(): Return the top element of s1 without removing it.
  5. empty(): Return true if s1 is empty.

Code

class MyQueue {
    stack<int> s1, s2;

public:
    MyQueue() {}

    // Push element to back of queue - O(n)
    void push(int x) {
        // Transfer all elements from s1 to s2
        while (!s1.empty()) {
            s2.push(s1.top());
            s1.pop();
        }
        // Push new element onto empty s1
        s1.push(x);
        // Transfer everything back from s2 to s1
        while (!s2.empty()) {
            s1.push(s2.top());
            s2.pop();
        }
    }

    // Remove and return front element - O(1)
    int pop() {
        int front = s1.top();
        s1.pop();
        return front;
    }

    // Return front element without removing - O(1)
    int peek() {
        return s1.top();
    }

    // Check if queue is empty - O(1)
    bool empty() {
        return s1.empty();
    }
};
class MyQueue:
    def __init__(self):
        self.s1 = []  # Main stack (keeps queue order)
        self.s2 = []  # Temporary helper stack

    # Push element to back of queue - O(n)
    def push(self, x: int) -> None:
        # Transfer all elements from s1 to s2
        while self.s1:
            self.s2.append(self.s1.pop())
        # Push new element onto empty s1
        self.s1.append(x)
        # Transfer everything back from s2 to s1
        while self.s2:
            self.s1.append(self.s2.pop())

    # Remove and return front element - O(1)
    def pop(self) -> int:
        return self.s1.pop()

    # Return front element without removing - O(1)
    def peek(self) -> int:
        return self.s1[-1]

    # Check if queue is empty - O(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<>();
    }

    // Push element to back of queue - O(n)
    public void push(int x) {
        // Transfer all elements from s1 to s2
        while (!s1.isEmpty()) {
            s2.push(s1.pop());
        }
        // Push new element onto empty s1
        s1.push(x);
        // Transfer everything back from s2 to s1
        while (!s2.isEmpty()) {
            s1.push(s2.pop());
        }
    }

    // Remove and return front element - O(1)
    public int pop() {
        return s1.pop();
    }

    // Return front element without removing - O(1)
    public int peek() {
        return s1.peek();
    }

    // Check if queue is empty - O(1)
    public boolean empty() {
        return s1.isEmpty();
    }
}

Complexity Analysis

Time Complexity:

  • push(x): O(n) — where n is the number of elements currently in the queue. We move all n elements from s1 to s2 (n pops and n pushes), place the new element, then move all n elements back (n pops and n pushes). Total: 4n + 1 operations per push, which is O(n).
  • pop(): O(1) — the front element is always on top of s1, so we simply pop.
  • peek(): O(1) — same reasoning as pop, just read the top without removing.
  • empty(): O(1) — check if s1 is empty.

Space Complexity: O(n)

Both stacks together hold all n elements in the queue. During a push operation, s2 temporarily holds all n existing elements while s1 gets the new one, but the total element count is still n + 1. No additional memory beyond the two stacks is used.

Why This Approach Is Not Efficient

The brute force makes every push operation O(n) because it eagerly transfers all existing elements twice — once to the helper stack and once back. If we perform n push operations in sequence, the total work is:

1 + 2 + 3 + ... + (n-1) = n×(n-1)/2 = O(n²)

With the constraint of up to 100 operations, this gives roughly 100² = 10,000 operations — which is fine for this small input. But the design is fundamentally wasteful.

The core problem: we rearrange the entire collection on every push, even though we might not need to access the front element until much later. We are doing work eagerly that may not be needed right away.

Key insight: what if we delayed the rearrangement until someone actually asks for the front element (pop or peek)? Instead of keeping s1 in perfect queue order at all times, we could let pushes accumulate cheaply in one stack, and only reorganize when a pop or peek forces us to. This "lazy" strategy avoids redundant transfers and yields amortized O(1) per operation.

Optimal Approach - Lazy Transfer with Two Stacks

Intuition

Think of two buckets labeled "In" and "Out". New arrivals always go into the In bucket (just toss them on top — no rearranging). When someone asks "who is next in line?" (pop or peek), you check the Out bucket first. If Out is empty, you flip the entire In bucket upside-down into Out. This one flip reverses the LIFO order into FIFO order — the oldest arrival is now on top of Out.

Here is the beautiful part: once elements are in Out, they stay there in perfect queue order. Subsequent pops just take from the top of Out — no more flipping needed until Out runs dry again. Each element moves at most twice in its lifetime: once into In (during push) and once from In to Out (during a transfer). This means the total cost of n operations is O(n), giving each operation an amortized cost of O(1).

Compare this to the brute force, which transfers elements on every push. The lazy approach only transfers when absolutely necessary — when the Out bucket is empty and someone needs the front element.

Step-by-Step Explanation

Let us trace through the operations push(1), push(2), push(3), pop(), push(4), pop() using lazy transfer. We maintain s1 (input stack) and s2 (output stack).

Step 1: Initialize two empty stacks.

  • s1 = [], s2 = []

Step 2: push(1). Push directly onto s1. No transfer.

  • s1 = [1], s2 = []

Step 3: push(2). Push directly onto s1. No transfer.

  • s1 = [1, 2], s2 = []

Step 4: push(3). Push directly onto s1. No transfer. Three pushes, zero transfers so far.

  • s1 = [1, 2, 3], s2 = []

Step 5: pop() called. We need the front element but s2 is empty. Transfer begins: pop 3 from s1, push to s2.

  • s1 = [1, 2], s2 = [3]

Step 6: Continue transfer. Pop 2 from s1, push to s2.

  • s1 = [1], s2 = [3, 2]

Step 7: Continue transfer. Pop 1 from s1, push to s2. Transfer complete.

  • s1 = [], s2 = [3, 2, 1]
  • The order reversed: element 1 (pushed first) is now on top of s2.

Step 8: Pop from s2. Returns 1 — the queue front. Correct FIFO order.

  • s1 = [], s2 = [3, 2]

Step 9: push(4). Push directly onto s1. We do NOT touch s2 — its remaining elements stay in place.

  • s1 = [4], s2 = [3, 2]

Step 10: pop() called. s2 is NOT empty — it still has elements from the earlier transfer. No new transfer needed. Pop from s2. Returns 2.

  • s1 = [4], s2 = [3]

Result: Elements came out as 1, then 2 — correct FIFO order. The key: one transfer served two pop operations. The three elements moved from s1 to s2 just once, and then two pops consumed two of them without any additional transfers.

Lazy Transfer — Amortized O(1) Queue Operations — Watch how pushes accumulate cheaply in the input stack, and elements transfer to the output stack only when a pop or peek finds it empty. Once transferred, elements serve multiple pops without re-transferring.

Algorithm

  1. Maintain two stacks: s1 (input) and s2 (output).
  2. push(x): Push x onto s1. Nothing else. Cost: O(1).
  3. Helper — transfer(): If s2 is empty, pop every element from s1 and push it onto s2. This reverses the order so the oldest element is on top of s2. If s2 is not empty, do nothing.
  4. pop(): Call transfer(). Pop and return the top element of s2.
  5. peek(): Call transfer(). Return the top element of s2 without removing it.
  6. empty(): Return true if both s1 and s2 are empty.

Code

class MyQueue {
    stack<int> s1, s2;

    // Transfer all elements from s1 to s2 only when s2 is empty
    void transfer() {
        if (s2.empty()) {
            while (!s1.empty()) {
                s2.push(s1.top());
                s1.pop();
            }
        }
    }

public:
    MyQueue() {}

    // Push element to back of queue - O(1)
    void push(int x) {
        s1.push(x);
    }

    // Remove and return front element - Amortized O(1)
    int pop() {
        transfer();
        int front = s2.top();
        s2.pop();
        return front;
    }

    // Return front element without removing - Amortized O(1)
    int peek() {
        transfer();
        return s2.top();
    }

    // Check if queue is empty - O(1)
    bool empty() {
        return s1.empty() && s2.empty();
    }
};
class MyQueue:
    def __init__(self):
        self.s1 = []  # Input stack (pushes go here)
        self.s2 = []  # Output stack (pops come from here)

    def _transfer(self) -> None:
        # Transfer only when output stack is empty
        if not self.s2:
            while self.s1:
                self.s2.append(self.s1.pop())

    # Push element to back of queue - O(1)
    def push(self, x: int) -> None:
        self.s1.append(x)

    # Remove and return front element - Amortized O(1)
    def pop(self) -> int:
        self._transfer()
        return self.s2.pop()

    # Return front element without removing - Amortized O(1)
    def peek(self) -> int:
        self._transfer()
        return self.s2[-1]

    # Check if queue is empty - O(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<>();
    }

    // Transfer all elements from s1 to s2 only when s2 is empty
    private void transfer() {
        if (s2.isEmpty()) {
            while (!s1.isEmpty()) {
                s2.push(s1.pop());
            }
        }
    }

    // Push element to back of queue - O(1)
    public void push(int x) {
        s1.push(x);
    }

    // Remove and return front element - Amortized O(1)
    public int pop() {
        transfer();
        return s2.pop();
    }

    // Return front element without removing - Amortized O(1)
    public int peek() {
        transfer();
        return s2.peek();
    }

    // Check if queue is empty - O(1)
    public boolean empty() {
        return s1.isEmpty() && s2.isEmpty();
    }
}

Complexity Analysis

Time Complexity:

  • push(x): O(1) — simply push onto s1. No transfers, no rearranging.
  • pop(): Amortized O(1) — a single pop might trigger a transfer costing O(k) where k is the number of elements in s1. However, each element is transferred at most once from s1 to s2 over its entire lifetime. If we perform n operations total, the cumulative transfer cost across all operations is at most O(n). Spread over n operations, each operation costs O(1) on average (amortized).
  • peek(): Amortized O(1) — same reasoning as pop. The transfer function has amortized O(1) cost, and reading the top of s2 is O(1).
  • empty(): O(1) — checking if two stacks are empty is constant time.

Why amortized O(1) and not just O(1)? Because a single pop can cost O(n) in the worst case (when all elements need to transfer). But that expensive operation "pays for" the next several cheap pops. Over any sequence of n operations, total element moves never exceed 2n (each element enters s1 once and leaves to s2 once).

Space Complexity: O(n)

Both stacks together hold all n elements currently in the queue. At any point, an element is in exactly one of the two stacks. No additional memory beyond the two stacks is used.