Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Implement Stack using Queues

EASYProblemSolveExternal Links

Description

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack: push, top, pop, and empty.

Implement the MyStack class:

  • void push(int x) — Pushes element x to the top of the stack.
  • int pop() — Removes the element on the top of the stack and returns it.
  • int top() — Returns the element on the top of the stack.
  • boolean empty() — Returns true if the stack is empty, false otherwise.

Notes:

  • You must use only standard operations of a queue, which means only push to back, peek/pop from front, size, and is empty operations are valid.
  • Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue's standard operations.

Follow-up: Can you implement the stack using only one queue?

Examples

Example 1

Input:
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]

Output: [null, null, null, 2, 2, false]

Explanation:

  • MyStack myStack = new MyStack();
  • myStack.push(1); // stack is [1]
  • myStack.push(2); // stack is [1, 2] (2 is on top)
  • myStack.top(); // returns 2
  • myStack.pop(); // returns 2, stack becomes [1]
  • myStack.empty(); // returns false, stack still has element 1

Constraints

  • 1 ≤ x ≤ 9
  • At most 100 calls will be made to push, pop, top, and empty
  • All the calls to pop and top are valid (stack won't be empty when these are called)

Editorial

Brute Force

Intuition

A stack is LIFO (Last-In, First-Out), but a queue is FIFO (First-In, First-Out). These are opposite ordering behaviors. The challenge is to make a FIFO data structure behave like a LIFO one.

The core insight is: when we push a new element, it should become the element that comes out first (since it's the "top" of the stack). But a queue places new elements at the back, not the front. So we need to rearrange the queue so the newest element ends up at the front.

The brute force approach uses two queues: q1 (the main queue) and q2 (a helper). Every time we push, we:

  1. Put the new element into the empty q2
  2. Move everything from q1 into q2 (one by one, from front to back)
  3. Swap q1 and q2

After this, q1 always has the newest element at the front. So pop() and top() just interact with the front of q1 — which is O(1).

Think of it like a line of people. When a new person arrives and needs to be at the front (stack behavior), you move the new person into an empty second line, then have everyone from the first line join behind them in the second line, then relabel the second line as the main line.

Step-by-Step Explanation

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

Step 1 — push(1): q2 is empty. Enqueue 1 into q2. q1 is also empty, so nothing to move. Swap: q1 = [1], q2 = [].

Step 2 — push(2): Enqueue 2 into q2: q2 = [2]. Move all of q1 into q2: dequeue 1 from q1, enqueue into q2. Now q2 = [2, 1]. Swap: q1 = [2, 1], q2 = [].

Step 3 — top(): Return front of q1 = 2. This is correct — 2 was pushed last, so it should be on top.

Step 4 — pop(): Dequeue front of q1: returns 2. q1 = [1]. Correct — 2 is removed from the top.

Step 5 — push(3): Enqueue 3 into q2: q2 = [3]. Move all of q1 into q2: dequeue 1, enqueue into q2. q2 = [3, 1]. Swap: q1 = [3, 1], q2 = [].

Step 6 — pop(): Dequeue front of q1: returns 3. q1 = [1]. Correct — 3 was the most recently pushed element.

Two Queues — Push-Costly Approach — Watch how two queues work together to simulate a stack. On each push, the new element goes into q2, all elements from q1 are moved behind it, then the queues are swapped so q1 always has the stack's top at its front.

Algorithm

Use two queues, q1 (main) and q2 (helper).

push(x):

  1. Enqueue x into q2
  2. While q1 is not empty: dequeue from q1 and enqueue into q2
  3. Swap q1 and q2

pop():

  1. Dequeue and return the front element of q1

top():

  1. Return the front element of q1 (without removing it)

empty():

  1. Return whether q1 is empty

Code

class MyStack {
private:
    queue<int> q1, q2;
    
public:
    MyStack() {}
    
    void push(int x) {
        q2.push(x);
        while (!q1.empty()) {
            q2.push(q1.front());
            q1.pop();
        }
        swap(q1, q2);
    }
    
    int pop() {
        int top = q1.front();
        q1.pop();
        return top;
    }
    
    int top() {
        return q1.front();
    }
    
    bool empty() {
        return q1.empty();
    }
};
from collections import deque

class MyStack:
    def __init__(self):
        self.q1 = deque()
        self.q2 = deque()
    
    def push(self, x: int) -> None:
        self.q2.append(x)
        while self.q1:
            self.q2.append(self.q1.popleft())
        self.q1, self.q2 = self.q2, self.q1
    
    def pop(self) -> int:
        return self.q1.popleft()
    
    def top(self) -> int:
        return self.q1[0]
    
    def empty(self) -> bool:
        return len(self.q1) == 0
class MyStack {
    private Queue<Integer> q1;
    private Queue<Integer> q2;
    
    public MyStack() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }
    
    public void push(int x) {
        q2.add(x);
        while (!q1.isEmpty()) {
            q2.add(q1.poll());
        }
        Queue<Integer> temp = q1;
        q1 = q2;
        q2 = temp;
    }
    
    public int pop() {
        return q1.poll();
    }
    
    public int top() {
        return q1.peek();
    }
    
    public boolean empty() {
        return q1.isEmpty();
    }
}

Complexity Analysis

Time Complexity:

  • push(x): O(n) — We move all n existing elements from q1 to q2 one at a time, then swap. Each move involves a dequeue and enqueue, both O(1), done n times.
  • pop(): O(1) — Simply dequeue from the front of q1.
  • top(): O(1) — Peek at the front of q1.
  • empty(): O(1) — Check if q1 is empty.

Space Complexity: O(n)

We store all n elements across the two queues. At any point, q2 is empty and q1 holds all elements, so total space is O(n). The second queue q2 is only temporarily used during push.

Why This Approach Is Not Efficient

The two-queue push-costly approach works correctly, but it uses two separate queues and requires moving all elements during every push operation. While the time complexity cannot be improved beyond O(n) for at least one of push or pop (you must pay the cost of reordering somewhere), we can ask: do we really need two queues?

The answer is no. The helper queue q2 is only used temporarily during push — we enqueue the new element into it, transfer everything from q1, and then swap. But if we think carefully, we can achieve the exact same effect with a single queue: push the new element to the back, then rotate the existing elements behind it by repeatedly dequeuing from the front and enqueuing to the back.

This eliminates the second queue entirely, halving memory overhead (though the asymptotic space remains O(n)) and simplifying the code. It also directly answers the problem's follow-up question: "Can you implement the stack using only one queue?"

The key realization is that a queue's circular nature (front to back) lets us rotate elements into the correct order without needing a separate container.

Optimal Approach - Single Queue

Intuition

Instead of using two queues, we can achieve the same stack behavior with just one queue. The trick is to use the queue's own circular rotation to rearrange elements.

When we push a new element:

  1. Enqueue it at the back of the queue (normal queue operation)
  2. Then rotate all the elements that were already in the queue: dequeue from the front and re-enqueue to the back, repeating (size - 1) times

After this rotation, the newly pushed element is at the front of the queue. Every element behind it is in reverse insertion order — exactly the LIFO order we need.

Imagine a circular conveyor belt. When a new item is placed at the end, we spin the belt until that item reaches the front. All the older items naturally line up behind it in the correct stack order.

Pop and top simply interact with the front of the queue, which is always the stack's top element. This is O(1).

Step-by-Step Explanation

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

Step 1 — push(1): Enqueue 1. Queue: [1]. Size is 1, so rotate 0 times (nothing to rotate). Queue stays [1]. The front is 1, which is the stack top.

Step 2 — push(2): Enqueue 2. Queue: [1, 2]. Now rotate (size - 1) = 1 time: dequeue 1, enqueue 1 back. Queue: [2, 1]. The front is 2 (newest element), which is the stack top.

Step 3 — push(3): Enqueue 3. Queue: [2, 1, 3]. Rotate 2 times:

  • Dequeue 2, enqueue 2: Queue: [1, 3, 2]
  • Dequeue 1, enqueue 1: Queue: [3, 2, 1]
    The front is 3 (newest), followed by 2, then 1. Perfect LIFO order!

Step 4 — top(): Peek front = 3. Correct.

Step 5 — pop(): Dequeue front = 3, return 3. Queue: [2, 1]. Correct — 3 was the most recent.

Step 6 — pop(): Dequeue front = 2, return 2. Queue: [1]. Correct — 2 was next.

Single Queue — Rotation-Based Stack Simulation — Watch how a single queue simulates a stack using rotation. After pushing a new element to the back, we rotate all previous elements behind it so the newest is always at the front.

Algorithm

Use a single queue.

push(x):

  1. Record the current size of the queue as n
  2. Enqueue x at the back of the queue
  3. Rotate n times: dequeue from the front and enqueue back to the rear
  4. After rotation, x is at the front of the queue

pop():

  1. Dequeue and return the front element

top():

  1. Peek and return the front element without removing it

empty():

  1. Return whether the queue is empty

Code

class MyStack {
private:
    queue<int> q;
    
public:
    MyStack() {}
    
    void push(int x) {
        int n = q.size();
        q.push(x);
        for (int i = 0; i < n; i++) {
            q.push(q.front());
            q.pop();
        }
    }
    
    int pop() {
        int top = q.front();
        q.pop();
        return top;
    }
    
    int top() {
        return q.front();
    }
    
    bool empty() {
        return q.empty();
    }
};
from collections import deque

class MyStack:
    def __init__(self):
        self.q = deque()
    
    def push(self, x: int) -> None:
        n = len(self.q)
        self.q.append(x)
        for _ in range(n):
            self.q.append(self.q.popleft())
    
    def pop(self) -> int:
        return self.q.popleft()
    
    def top(self) -> int:
        return self.q[0]
    
    def empty(self) -> bool:
        return len(self.q) == 0
class MyStack {
    private Queue<Integer> q;
    
    public MyStack() {
        q = new LinkedList<>();
    }
    
    public void push(int x) {
        int n = q.size();
        q.add(x);
        for (int i = 0; i < n; i++) {
            q.add(q.poll());
        }
    }
    
    public int pop() {
        return q.poll();
    }
    
    public int top() {
        return q.peek();
    }
    
    public boolean empty() {
        return q.isEmpty();
    }
}

Complexity Analysis

Time Complexity:

  • push(x): O(n) — We enqueue the new element (O(1)), then perform n rotations. Each rotation involves one dequeue and one enqueue, both O(1). Total: O(n).
  • pop(): O(1) — Dequeue from the front.
  • top(): O(1) — Peek at the front.
  • empty(): O(1) — Check queue size.

Space Complexity: O(n)

We use a single queue storing all n elements. This is optimal — we must store n elements somewhere, so O(n) space is unavoidable.

Compared to the two-queue approach, this uses half the queue objects (1 vs 2), resulting in lower constant-factor memory overhead. The asymptotic complexities are identical, but the single-queue approach is cleaner, simpler, and answers the problem's follow-up challenge.