Log inSign up
easyLeetCodeNot Started

Implement Stack using Queues

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Queue
Solve on LeetCode
Lesson

Problem Statement

Implement a last-in-first-out (LIFO) stack using only two queues (or a single queue). 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.

Example 1 · Standard Stack Operations:

Input: ["MyStack", "push", "push", "top", "pop", "empty"] [[], [1], [2], [], [], []]
Output: [null, null, null, 2, 2, false]
Explanation: MyStack myStack = new MyStack(); myStack.push(1); myStack.push(2); myStack.top(); // return 2 myStack.pop(); // return 2 myStack.empty(); // return False

Constraints:

  • 1 <= x <= 9
  • At most 100 calls will be made to push, pop, top, and empty.
  • All calls to pop and top are valid.

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Queue FIFO Property
  • Stack LIFO Definition

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master cyclic buffer rotation to reverse element priority in a FIFO queue.
  • Compare 2-queue vs 1-queue space efficiency.
  • Implement clean LIFO interfaces using minimal queue primitives.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Simulate LIFO behavior strictly using FIFO queues.
  • Frequent top/pop operations requiring O(1) retrieval.

Algorithmic Decision Tree:

  • Use 1 Queue with Self-Rotation: Enqueue new element, rotate previous elements behind it.
  • Alternatively use 2 Queues: Swap references after transfer.

Connected Patterns:

Implement Queue using StacksDesign Circular QueueMin Stack

1. Brute Force — Two Queues with Pop Costly

Intuition

Push easily to the end of q1. When popping, move all elements except the last one to q2, leaving the top element isolated.

Algorithm

  1. Step 1: push(x) enqueues x directly to q1.
  2. Step 2: pop() moves size - 1 elements from q1 to q2.
  3. Step 3: Pop the remaining single element in q1.
  4. Step 4: Swap queue references q1 and q2.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <queue>
3
4using namespace std;
5
6class MyStack {
7private:
8 queue<int> q1, q2;
9public:
10 MyStack() {}
11
12 void push(int x) {
13 q1.push(x);
14 }
15
16 int pop() {
17 while (q1.size() > 1) {
18 q2.push(q1.front());
19 q1.pop();
20 }
21 int topVal = q1.front();
22 q1.pop();
23 swap(q1, q2);
24 return topVal;
25 }
26
27 int top() {
28 while (q1.size() > 1) {
29 q2.push(q1.front());
30 q1.pop();
31 }
32 int topVal = q1.front();
33 q2.push(topVal);
34 q1.pop();
35 swap(q1, q2);
36 return topVal;
37 }
38
39 bool empty() {
40 return q1.empty();
41 }
42};
43
44int main() {
45 MyStack st;
46 st.push(1);
47 st.push(2);
48 cout << "Top: " << st.top() << endl; // 2
49 cout << "Pop: " << st.pop() << endl; // 2
50 cout << "Empty: " << (st.empty() ? "true" : "false") << endl; // false
51 return 0;
52}

Time & Space Complexity

  • Time complexity: Push: O(1), Pop: O(N), Top: O(N) — Moving N-1 elements from q1 to q2 takes O(N) on every pop/top.
  • Space complexity: O(N) — Allocates two queues storing N elements.

Why Brute Force Doesn't Scale:

Two-queue pop-costly takes O(N) on every read, slowing down read-heavy workloads.

Single queue push-costly provides O(1) reads with zero extra object allocation overhead.

2. Better — Two Queues with Push Costly

Intuition

Keep q1 always in stack order by inserting new element into q2 first, dumping q1 behind it, and swapping.

Algorithm

  1. Step 1: Enqueue new element x into helper queue q2.
  2. Step 2: Transfer all existing elements from q1 into q2.
  3. Step 3: Swap queue references q1 and q2 so q1 holds all elements with newest at front.
  4. Step 4: pop() and top() read directly from q1 front in O(1).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <queue>
3
4using namespace std;
5
6class MyStack {
7private:
8 queue<int> q1, q2;
9public:
10 MyStack() {}
11
12 void push(int x) {
13 q2.push(x);
14 while (!q1.empty()) {
15 q2.push(q1.front());
16 q1.pop();
17 }
18 swap(q1, q2);
19 }
20
21 int pop() {
22 int val = q1.front();
23 q1.pop();
24 return val;
25 }
26
27 int top() {
28 return q1.front();
29 }
30
31 bool empty() {
32 return q1.empty();
33 }
34};
35
36int main() {
37 MyStack st;
38 st.push(10);
39 st.push(20);
40 cout << "Top: " << st.top() << endl; // 20
41 cout << "Pop: " << st.pop() << endl; // 20
42 return 0;
43}

Time & Space Complexity

  • Time complexity: Push: O(N), Pop: O(1), Top: O(1) — On push, moves all elements to q2 and back to q1 in O(N). Pop/Top are O(1).
  • Space complexity: O(N) — Allocates two queues.

3. Optimal — Single Queue with Self-Rotation

Intuition

Instead of using a second queue, re-enqueue previous elements into the same queue. The latest element immediately becomes the front.

Algorithm

  1. Step 1: Record existing queue size s = q.size().
  2. Step 2: Enqueue new element x.
  3. Step 3: Loop s times: dequeue front element and immediately re-enqueue it to the back.
  4. Step 4: Now x is at the front of the queue.
  5. Step 5: pop() and top() simply read from front in O(1).

Single Queue Self-Rotation Trace

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Queue: [1]
Visual state
Values and pointers at this exact step
queue
FRONT → REAR
1
Enqueue adds at the rear · Dequeue removes from the front
Decision / next transition
push(1)
Why this step matters

Queue: [1]. Size was 0.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <queue>
3
4using namespace std;
5
6class MyStack {
7private:
8 queue<int> q;
9public:
10 MyStack() {}
11
12 void push(int x) {
13 int sz = q.size();
14 q.push(x);
15 for (int i = 0; i < sz; ++i) {
16 q.push(q.front());
17 q.pop();
18 }
19 }
20
21 int pop() {
22 int val = q.front();
23 q.pop();
24 return val;
25 }
26
27 int top() {
28 return q.front();
29 }
30
31 bool empty() {
32 return q.empty();
33 }
34};
35
36int main() {
37 MyStack st;
38 st.push(1);
39 st.push(2);
40 st.push(3);
41 cout << "Top: " << st.top() << endl; // 3
42 cout << "Pop: " << st.pop() << endl; // 3
43 cout << "Top: " << st.top() << endl; // 2
44 cout << "Empty: " << (st.empty() ? "true" : "false") << endl; // false
45 return 0;
46}

Time & Space Complexity

  • Time complexity: Push: O(N), Pop: O(1), Top: O(1) — On push, rotates the previous N-1 elements to the back in N-1 operations. Pop and top are instant O(1).
  • Space complexity: O(N) (1 Single Queue) — Requires only a single queue data structure.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Two Queues (Pop Costly O(N))Push: O(1), Pop/Top: O(N)O(N)Push to q1. On pop/top, transfer N-1 elements from q1 to q2, pop the last element, and swap q1 and q2 references.Iterating through all elements during retrieval.
2.Better — Two Queues (Push Costly O(N))Push: O(N), Pop/Top: O(1)O(N)Enqueue new element into q2, transfer all q1 elements into q2, then swap q1 and q2 so q1 always maintains LIFO order at front.Dual queue memory overhead.
3.Optimal — Single Queue Self-Rotation (O(N) Push, O(1) Pop)OptimalPush: O(N), Pop/Top: O(1)O(N) (Single Queue Only)Enqueue x, then rotate the existing size - 1 elements in-place by popping from front and pushing to back.Self-rotation loop during push.

Common Pitfalls & Crucial Edge Cases

Rotating `q.size()` after pushing instead of previous size

Will rotate the new element too, ending back in original FIFO order.

Using two queues when one is sufficient

Demonstrating the single-queue approach shows deeper understanding of data structure mechanics.

Crucial Edge Cases to Validate:

  • Single element stack — Size is 0 before push, rotation loop does not run, element stays at front.
  • Repeated top() without pop() — Accesses front repeatedly in O(1) without modifying queue state.
  • Popping down to empty — Fully empties queue; subsequent empty() evaluates correctly.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention both 2-queue and 1-queue variations to the interviewer before jumping to the 1-queue optimal code.
  2. Highlight that Queue -> Stack cannot be amortized to O(1) both ways like Stack -> Queue (one operation must be O(N)).
  3. Explain the rotation invariant clearly: 'We maintain the invariant that the queue front always equals the stack top.'

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.How many elements are rotated when pushing into a single queue of existing size N?

2.What is the time complexity of top() and pop() in the optimal single-queue implementation?

3.Why is the single queue implementation preferred over two queues?

Back to DSA Sheet