Problem editorial

Implement Stack using Queues

EasyDesign PatternsStackDesignQueue

Editorial

Core insight

Implement Stack using Queues · Design Patterns

Core Insight for Implement Stack using Queues

The fundamental difference between a Stack and a Queue is where elements are removed.

Queue (FIFO): Removes from the front.
Stack (LIFO): Removes from the top (which corresponds to the back of the queue, i.e., the most recently added element).

To implement a Stack using a Queue, we need the "back" element to be accessible at the "front."

The core insight is Queue Rotation. When we push a new element $x$ into a queue of size $N$ , $x$ is placed at the back (position $N+1$ ). If we immediately remove the first $N$ elements from the front and add them back to the queue, the order cyclically shifts. The element $x$ (originally at the back) will "rotate" all the way to the front.

Visual Description: Imagine a queue containing elements [1, 2].

We push 3. The queue becomes [1, 2, 3].
To make 3 the top, we rotate.
Pop 1 and push it to back: [2, 3, 1].
Pop 2 and push it to back: [3, 1, 2].
Now 3 is at the front. A standard queue pop operation will correctly return 3, satisfying the Stack LIFO requirement.

Deep dive

Full breakdown

Full reasoning, pitfalls, and implementation flow

LeetCode 225: Implement Stack using Queues Solution & Explanation

Problem Overview

TL;DR: The optimal solution uses a single queue and rotates the elements after every insertion so that the most recently added element always sits at the front, allowing $O(1)$ access for stack operations.

The LeetCode 225 problem, "Implement Stack using Queues," challenges us to construct a Last-In-First-Out (LIFO) stack data structure using only First-In-First-Out (FIFO) queues. We must support the standard stack interface: push, pop, top, and empty, while strictly adhering to standard queue operations (enqueue, dequeue, size, and peek). This is a popular interview question used to test object-oriented design skills and data structure manipulation.

Brute Force Approach for Implement Stack using Queues

The most intuitive or "brute force" way to solve this is by using two separate queues, often referred to as q1 (source) and q2 (helper).

In this approach, to maintain the LIFO property, we ensure that the element to be popped is always at the front of q1.

Push Operation: When a new element arrives, we enqueue it into the empty q2. Then, we dequeue every element from q1 and enqueue them into q2. Finally, we swap the references of q1 and q2.
Pop Operation: Simply dequeue from q1.

Why this is suboptimal: While correct, this approach requires maintaining two distinct data structures. Although the time complexity is the same as the optimal approach ( $O(N)$ for push, $O(1)$ for pop), the management of two queues adds unnecessary overhead and code complexity. Furthermore, the problem statement includes a follow-up asking for a solution using only one queue, which the brute force method fails to address.

Algorithm Strategy: Design Patterns

We will implement the MyStack class using a single queue.

State: Maintain a single queue data structure.
Push Strategy:
- Add the new element to the queue.
- Immediately rotate the queue. If the queue size is $k$ after insertion, we perform $k-1$ dequeue-then-enqueue operations.
- This invariant ensures the newest element is always at the head of the queue.
Pop Strategy:
- Since the "stack top" is always maintained at the "queue front," we simply perform a standard queue dequeue operation.
Top Strategy:
- Return the front element of the queue.
Empty Strategy:
- Check if the underlying queue is empty.

Execution Flow

Let's trace the operations: push(1), push(2), pop().

Initialize: queue = []
push(1):
- Enqueue 1. queue = [1].
- Size is 1. Rotate 1-1 = 0 times.
- State: [1] (Top is 1).
push(2):
- Enqueue 2. queue = [1, 2].
- Size is 2. Rotate 2-1 = 1 time.
- Dequeue 1, Enqueue 1.
- State: [2, 1] (Top is 2).
pop():
- Dequeue front. Returns 2.
- State: [1] (Top is 1).

Proof of Correctness

The correctness relies on the invariant: The queue is always sorted in reverse chronological order of insertion.

Base Case: An empty queue represents an empty stack.
Inductive Step: Assume the queue contains elements ordered [Newest, ..., Oldest]. When we add a new element $E$ , it enters at the back: [Newest, ..., Oldest, E]. By rotating the previous $N$ elements behind $E$ , the new order becomes [E, Newest, ..., Oldest].
Conclusion: Since the newest element is always at the front, pop() (dequeue front) correctly removes the LIFO element, and top() (peek front) correctly views it.

Pattern Reuse Notes

The logic of wrapping or adapting one data structure to serve another purpose is found in several LeetCode problems:

LeetCode 146: LRU Cache - Combines a Hash Map and Doubly Linked List to enforce eviction policies.
LeetCode 155: Min Stack - Adapts a stack to track the minimum element in constant time.
LeetCode 232: Implement Queue using Stacks - The inverse of this problem; uses two stacks to simulate FIFO behavior.
LeetCode 251: Flatten 2D Vector - Adapts a 2D array structure to behave like a linear iterator.

Understanding how to manipulate data structure invariants is key to solving these design problems efficiently.

Feynman coach · Before you peek at the code

Can you explain the core insight in your own words?

If you can explain it before reading code, you’re far more likely to recall it under interview pressure.

Loading your attempt…

Reference Implementation

C++ Solution for LeetCode 225

cpp

1#include <queue>
2
3class MyStack {
4private:
5    std::queue<int> q;
6
7public:
8    MyStack() {
9        // Constructor does not need to do anything specifically
10    }
11    
12    void push(int x) {
13        q.push(x);
14        // Rotate the queue so the new element (at back) moves to front
15        int sz = q.size();
16        for (int i = 0; i < sz - 1; ++i) {
17            q.push(q.front());
18            q.pop();
19        }
20    }
21    
22    int pop() {
23        int topElement = q.front();
24        q.pop();
25        return topElement;
26    }
27    
28    int top() {
29        return q.front();
30    }
31    
32    bool empty() {
33        return q.empty();
34    }
35};

Java Solution for LeetCode 225

java

1import java.util.LinkedList;
2import java.util.Queue;
3
4class MyStack {
5    private Queue<Integer> queue;
6
7    public MyStack() {
8        // LinkedList implements Queue interface in Java
9        queue = new LinkedList<>();
10    }
11    
12    public void push(int x) {
13        queue.add(x);
14        // Rotate size-1 elements to the back
15        int sz = queue.size();
16        for (int i = 0; i < sz - 1; i++) {
17            queue.add(queue.remove());
18        }
19    }
20    
21    public int pop() {
22        // The front of the queue is the top of the stack
23        return queue.remove();
24    }
25    
26    public int top() {
27        return queue.peek();
28    }
29    
30    public boolean empty() {
31        return queue.isEmpty();
32    }
33}

Python Solution for LeetCode 225

python

1from collections import deque
2
3class MyStack:
4
5    def __init__(self):
6        # deque serves as our queue implementation
7        self.q = deque()
8
9    def push(self, x: int) -> None:
10        self.q.append(x)
11        # Rotate the queue: pop from left and append to right
12        # We do this size-1 times to bring the new element to the front
13        for _ in range(len(self.q) - 1):
14            self.q.append(self.q.popleft())
15
16    def pop(self) -> int:
17        # Front of queue (left) is the top of stack
18        return self.q.popleft()
19
20    def top(self) -> int:
21        return self.q[0]
22
23    def empty(self) -> bool:
24        return len(self.q) == 0

AI Coach Insight

For Implement Stack using Queues, focus on explaining why the structure works, not just naming Design Patterns.

Complexity Analysis

Time Complexity:
- push(x): $O(N)$ . We add one element and then move $N$ elements, resulting in $N+1$ operations.
- pop(): $O(1)$ . We simply remove from the front.
- top(): $O(1)$ . We simply peek at the front.
- empty(): $O(1)$ .
Space Complexity: $O(N)$ . We use a single queue to store the $N$ elements of the stack. No auxiliary data structures are used.

Related Patterns

Pattern: Design Patterns
Subpattern: Design (General/Specific)

This problem falls under the Design Pattern category because it requires implementing a specific interface (Stack) by composing an underlying data structure (Queue) in a way that modifies its natural behavior. We are essentially building an adapter that enforces LIFO constraints on a FIFO container.

Common Mistakes & FAQ

Q: Why can't I just use a list or array? A: The problem explicitly requires using only standard queue operations (push to back, peek/pop from front, size, is empty). Using random access (like arr[i]) or removing from the end of a list violates the constraints of the "Design" pattern challenge.

Q: Can I make push $O(1)$ and pop $O(N)$ instead? A: Yes, this is a valid alternative. You would keep the queue in FIFO order (normal queue behavior). For pop(), you would have to rotate $N-1$ elements to the back to expose the last element, remove it, and then leave the queue in a potentially rotated state. However, the $O(N)$ push approach (presented above) is generally preferred because top() becomes $O(1)$ , whereas the alternative makes top() $O(N)$ as well.

Q: Why does my solution get Time Limit Exceeded (TLE)? A: This is rare given the small constraint ( $N=100$ ), but logically, if you are creating a new queue instance inside every push or pop operation instead of reusing one (or two) persistent queues, the allocation overhead can be significant. Additionally, ensure you are not entering an infinite loop during the rotation phase.

Practise Implement Stack using Queues and the problems around it

Implement Stack using Queues is a Design Patterns problem, in the Design (General/Specific) subpattern. Once the approach above makes sense, write it yourself and then work through the neighbouring problems that reuse it.

Core insight

Implement Stack using Queues · Design Patterns

Core Insight for Implement Stack using Queues

The fundamental difference between a Stack and a Queue is where elements are removed.

Queue (FIFO): Removes from the front.
Stack (LIFO): Removes from the top (which corresponds to the back of the queue, i.e., the most recently added element).

To implement a Stack using a Queue, we need the "back" element to be accessible at the "front."

Visual Description: Imagine a queue containing elements [1, 2].

We push 3. The queue becomes [1, 2, 3].
To make 3 the top, we rotate.
Pop 1 and push it to back: [2, 3, 1].
Pop 2 and push it to back: [3, 1, 2].
Now 3 is at the front. A standard queue pop operation will correctly return 3, satisfying the Stack LIFO requirement.

Deep dive

Full breakdown

Full reasoning, pitfalls, and implementation flow

LeetCode 225: Implement Stack using Queues Solution & Explanation

Problem Overview

Brute Force Approach for Implement Stack using Queues

The most intuitive or "brute force" way to solve this is by using two separate queues, often referred to as q1 (source) and q2 (helper).

In this approach, to maintain the LIFO property, we ensure that the element to be popped is always at the front of q1.

Push Operation: When a new element arrives, we enqueue it into the empty q2. Then, we dequeue every element from q1 and enqueue them into q2. Finally, we swap the references of q1 and q2.
Pop Operation: Simply dequeue from q1.

Algorithm Strategy: Design Patterns

We will implement the MyStack class using a single queue.

State: Maintain a single queue data structure.
Push Strategy:
- Add the new element to the queue.
- Immediately rotate the queue. If the queue size is $k$ after insertion, we perform $k-1$ dequeue-then-enqueue operations.
- This invariant ensures the newest element is always at the head of the queue.
Pop Strategy:
- Since the "stack top" is always maintained at the "queue front," we simply perform a standard queue dequeue operation.
Top Strategy:
- Return the front element of the queue.
Empty Strategy:
- Check if the underlying queue is empty.

Execution Flow

Let's trace the operations: push(1), push(2), pop().

Initialize: queue = []
push(1):
- Enqueue 1. queue = [1].
- Size is 1. Rotate 1-1 = 0 times.
- State: [1] (Top is 1).
push(2):
- Enqueue 2. queue = [1, 2].
- Size is 2. Rotate 2-1 = 1 time.
- Dequeue 1, Enqueue 1.
- State: [2, 1] (Top is 2).
pop():
- Dequeue front. Returns 2.
- State: [1] (Top is 1).

Proof of Correctness

The correctness relies on the invariant: The queue is always sorted in reverse chronological order of insertion.

Base Case: An empty queue represents an empty stack.
Inductive Step: Assume the queue contains elements ordered [Newest, ..., Oldest]. When we add a new element $E$ , it enters at the back: [Newest, ..., Oldest, E]. By rotating the previous $N$ elements behind $E$ , the new order becomes [E, Newest, ..., Oldest].
Conclusion: Since the newest element is always at the front, pop() (dequeue front) correctly removes the LIFO element, and top() (peek front) correctly views it.

Pattern Reuse Notes

The logic of wrapping or adapting one data structure to serve another purpose is found in several LeetCode problems:

LeetCode 146: LRU Cache - Combines a Hash Map and Doubly Linked List to enforce eviction policies.
LeetCode 155: Min Stack - Adapts a stack to track the minimum element in constant time.
LeetCode 232: Implement Queue using Stacks - The inverse of this problem; uses two stacks to simulate FIFO behavior.
LeetCode 251: Flatten 2D Vector - Adapts a 2D array structure to behave like a linear iterator.

Understanding how to manipulate data structure invariants is key to solving these design problems efficiently.

Feynman coach · Before you peek at the code

Can you explain the core insight in your own words?

If you can explain it before reading code, you’re far more likely to recall it under interview pressure.

Loading your attempt…

Reference Implementation

C++ Solution for LeetCode 225

cpp

1#include <queue>
2
3class MyStack {
4private:
5    std::queue<int> q;
6
7public:
8    MyStack() {
9        // Constructor does not need to do anything specifically
10    }
11    
12    void push(int x) {
13        q.push(x);
14        // Rotate the queue so the new element (at back) moves to front
15        int sz = q.size();
16        for (int i = 0; i < sz - 1; ++i) {
17            q.push(q.front());
18            q.pop();
19        }
20    }
21    
22    int pop() {
23        int topElement = q.front();
24        q.pop();
25        return topElement;
26    }
27    
28    int top() {
29        return q.front();
30    }
31    
32    bool empty() {
33        return q.empty();
34    }
35};

Java Solution for LeetCode 225

java

1import java.util.LinkedList;
2import java.util.Queue;
3
4class MyStack {
5    private Queue<Integer> queue;
6
7    public MyStack() {
8        // LinkedList implements Queue interface in Java
9        queue = new LinkedList<>();
10    }
11    
12    public void push(int x) {
13        queue.add(x);
14        // Rotate size-1 elements to the back
15        int sz = queue.size();
16        for (int i = 0; i < sz - 1; i++) {
17            queue.add(queue.remove());
18        }
19    }
20    
21    public int pop() {
22        // The front of the queue is the top of the stack
23        return queue.remove();
24    }
25    
26    public int top() {
27        return queue.peek();
28    }
29    
30    public boolean empty() {
31        return queue.isEmpty();
32    }
33}

Python Solution for LeetCode 225

python

1from collections import deque
2
3class MyStack:
4
5    def __init__(self):
6        # deque serves as our queue implementation
7        self.q = deque()
8
9    def push(self, x: int) -> None:
10        self.q.append(x)
11        # Rotate the queue: pop from left and append to right
12        # We do this size-1 times to bring the new element to the front
13        for _ in range(len(self.q) - 1):
14            self.q.append(self.q.popleft())
15
16    def pop(self) -> int:
17        # Front of queue (left) is the top of stack
18        return self.q.popleft()
19
20    def top(self) -> int:
21        return self.q[0]
22
23    def empty(self) -> bool:
24        return len(self.q) == 0

Implement Stack using Queues

Core insight

Core Insight for Implement Stack using Queues

Full breakdown

LeetCode 225: Implement Stack using Queues Solution & Explanation

Problem Overview

Brute Force Approach for Implement Stack using Queues

Algorithm Strategy: Design Patterns

Execution Flow

Proof of Correctness

Pattern Reuse Notes

Can you explain the core insight in your own words?

Reference Implementation

C++ Solution for LeetCode 225

Java Solution for LeetCode 225

Python Solution for LeetCode 225

Practise Implement Stack using Queues and the problems around it

Related problems

Implement Stack using Queues

Core insight

Core Insight for Implement Stack using Queues

Full breakdown

LeetCode 225: Implement Stack using Queues Solution & Explanation

Problem Overview

Brute Force Approach for Implement Stack using Queues

Algorithm Strategy: Design Patterns

Execution Flow

Proof of Correctness

Pattern Reuse Notes

Can you explain the core insight in your own words?

Reference Implementation

C++ Solution for LeetCode 225

Java Solution for LeetCode 225

Python Solution for LeetCode 225

Practise Implement Stack using Queues and the problems around it

Related problems