Log inSign up
easyLeetCodeNot Started

Implement Queue using Stacks

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

Queue
Solve on LeetCode
Lesson

Problem Statement

Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class: - void push(int x) Pushes 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. - boolean empty() Returns true if the queue is empty, false otherwise.

Notes: - You must use only standard operations of a stack — which means only push to top, peek/pop from top, size, and is empty operations are valid.

Example 1 · Standard Queue Operations:

Input: ["MyQueue", "push", "push", "peek", "pop", "empty"] [[], [1], [2], [], [], []]
Output: [null, null, null, 1, 1, false]
Explanation: MyQueue myQueue = new MyQueue(); myQueue.push(1); // queue is: [1] myQueue.push(2); // queue is: [1, 2] (leftmost is front) myQueue.peek(); // return 1 myQueue.pop(); // return 1, queue is [2] myQueue.empty(); // return false

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 (non-empty queue).

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Stack LIFO Property
  • Queue FIFO Property
  • Amortized Complexity Basics

What You'll Learn

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

  • Understand the mathematical difference between worst-case O(N) and amortized O(1) complexity.
  • Master the dual-stack inversion technique for FIFO simulation.
  • Implement lazy evaluation strategies to minimize redundant memory movement.

Pattern Recognition Trigger

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

Signals to Look For:

  • Restricted to LIFO primitives while requiring FIFO ordering.
  • Need O(1) average time for sequential stream buffering.

Algorithmic Decision Tree:

  • Keep push O(1) by always pushing onto inStack.
  • Shift all elements from inStack to outStack in reverse only when outStack is empty during pop/peek.

Connected Patterns:

Implement Stack using QueuesMin StackDesign Circular Queue

1. Brute Force — Push Costly (O(N) Push)

Intuition

Maintain the FIFO queue order inside s1 at all times by shifting existing elements to helper stack s2 before pushing.

Algorithm

  1. Step 1: Move all elements from stack s1 to helper stack s2.
  2. Step 2: Push the new element x onto stack s1.
  3. Step 3: Move all elements back from s2 onto s1.
  4. Step 4: Pop and peek directly return s1.top().
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <stack>
3
4using namespace std;
5
6class MyQueue {
7private:
8 stack<int> s1, s2;
9public:
10 MyQueue() {}
11
12 void push(int x) {
13 while (!s1.empty()) {
14 s2.push(s1.top());
15 s1.pop();
16 }
17 s1.push(x);
18 while (!s2.empty()) {
19 s1.push(s2.top());
20 s2.pop();
21 }
22 }
23
24 int pop() {
25 int val = s1.top();
26 s1.pop();
27 return val;
28 }
29
30 int peek() {
31 return s1.top();
32 }
33
34 bool empty() {
35 return s1.empty();
36 }
37};
38
39int main() {
40 MyQueue q;
41 q.push(1);
42 q.push(2);
43 cout << "Peek: " << q.peek() << endl; // 1
44 cout << "Pop: " << q.pop() << endl; // 1
45 cout << "Empty: " << (q.empty() ? "true" : "false") << endl; // false
46 return 0;
47}

Time & Space Complexity

  • Time complexity: Push: O(N), Pop: O(1) — Moving N elements between stacks on every push requires 2N operations.
  • Space complexity: O(N) — Stores N elements across two stacks.

Why Brute Force Doesn't Scale:

With 105 operations, an O(N) per pop approach requires 1010 operations (TLE).

Lazy transfer processes 105 operations in under 5ms because each item moves at most twice.

2. Better — Pop Costly with Reversal Dump

Intuition

Allow fast pushes by appending directly to s1. On pop/peek, transfer to s2 to access the bottom element, then restore.

Algorithm

  1. Step 1: On push(x), push directly onto s1 in O(1).
  2. Step 2: On pop(), transfer all elements from s1 to s2.
  3. Step 3: Save and pop top of s2.
  4. Step 4: Transfer all remaining elements back to s1 and return the saved value.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <stack>
3
4using namespace std;
5
6class MyQueue {
7private:
8 stack<int> s1, s2;
9public:
10 MyQueue() {}
11
12 void push(int x) {
13 s1.push(x);
14 }
15
16 int pop() {
17 while (!s1.empty()) {
18 s2.push(s1.top());
19 s1.pop();
20 }
21 int val = s2.top();
22 s2.pop();
23 while (!s2.empty()) {
24 s1.push(s2.top());
25 s2.pop();
26 }
27 return val;
28 }
29
30 int peek() {
31 while (!s1.empty()) {
32 s2.push(s1.top());
33 s1.pop();
34 }
35 int val = s2.top();
36 while (!s2.empty()) {
37 s1.push(s2.top());
38 s2.pop();
39 }
40 return val;
41 }
42
43 bool empty() {
44 return s1.empty();
45 }
46};
47
48int main() {
49 MyQueue q;
50 q.push(10);
51 q.push(20);
52 cout << "Peek: " << q.peek() << endl;
53 cout << "Pop: " << q.pop() << endl;
54 return 0;
55}

Time & Space Complexity

  • Time complexity: Push: O(1), Pop: O(N) — Push is instant O(1). Pop transfers all elements to s2, pops, and returns them to s1 in O(N).
  • Space complexity: O(N) — Uses O(N) storage for stack elements.

3. Optimal — Lazy Dual-Stack Amortized O(1)

Intuition

Do not move elements back from outStack to inStack. Keep elements in outStack until it is completely drained, preserving reverse order.

Algorithm

  1. Step 1: Push operations always push directly onto inStack in O(1).
  2. Step 2: On pop() or peek(), check if outStack is empty.
  3. Step 3: If outStack is empty, pop all elements from inStack and push them into outStack.
  4. Step 4: Return/pop top of outStack in O(1).
  5. Step 5: Queue is empty only when both inStack and outStack are empty.

Lazy Dual-Stack FIFO Trace

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

inStack: [1, 2], outStack: []

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <stack>
3
4using namespace std;
5
6class MyQueue {
7private:
8 stack<int> inStack;
9 stack<int> outStack;
10
11 void transfer() {
12 if (outStack.empty()) {
13 while (!inStack.empty()) {
14 outStack.push(inStack.top());
15 inStack.pop();
16 }
17 }
18 }
19
20public:
21 MyQueue() {}
22
23 void push(int x) {
24 inStack.push(x);
25 }
26
27 int pop() {
28 transfer();
29 int val = outStack.top();
30 outStack.pop();
31 return val;
32 }
33
34 int peek() {
35 transfer();
36 return outStack.top();
37 }
38
39 bool empty() {
40 return inStack.empty() && outStack.empty();
41 }
42};
43
44int main() {
45 MyQueue q;
46 q.push(1);
47 q.push(2);
48 cout << "Peek: " << q.peek() << endl; // 1
49 cout << "Pop: " << q.pop() << endl; // 1
50 q.push(3);
51 cout << "Pop: " << q.pop() << endl; // 2
52 cout << "Empty: " << (q.empty() ? "true" : "false") << endl; // false
53 return 0;
54}

Time & Space Complexity

  • Time complexity: Push: O(1), Pop/Peek: Amortized O(1) — Each element is pushed to inStack once, moved to outStack once, and popped once. Across N elements, total time is O(2N) = O(N), averaging O(1) per operation.
  • Space complexity: O(N) — O(N) total auxiliary memory distributed across inStack and outStack.

Approach Comparison Matrix

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

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Rebuild on Every PushPush: O(N), Pop: O(1)O(N)Transfer all elements from s1 to s2, push new element to s1, then transfer everything back from s2 to s1 on every single push.Eager reordering during every push.
2.Better — Rebuild on Every Pop/PeekPush: O(1), Pop/Peek: O(N)O(N)Always push into s1 in O(1). When popping, dump s1 into s2, pop top, and immediately dump s2 back into s1.Dumping elements back and forth on every query.
3.Optimal — Lazy Transfer Two Stacks (Amortized O(1))OptimalPush: O(1), Pop/Peek: Amortized O(1)O(N)Push to inStack. For pop/peek, read from outStack. Only transfer inStack -> outStack if outStack is empty. Never transfer back!None. Total work across N operations is O(N).

Common Pitfalls & Crucial Edge Cases

Dumping back to inStack

Moving elements back and forth after every pop destroys the amortized O(1) guarantee, worsening complexity to O(N).

Transferring when outStack is not empty

Overwriting outStack before it drains will invert the ordering of newer elements.

Checking only one stack for empty()

Queue is only empty when *both* inStack.empty() and outStack.empty() evaluate to true.

Crucial Edge Cases to Validate:

  • Repeated peek/pop without pushes — Does not trigger redundant transfers; reads continuously from outStack in O(1).
  • Alternating push and pop operations — inStack and outStack maintain elements simultaneously without collision.
  • Single element operations — Push 1 element, pop immediately; handles boundary correctly.

Interview Tips & Best Practices

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

  1. Explain the amortization aggregate method: 'Every item is pushed twice and popped twice throughout its lifecycle.'
  2. Highlight memory locality: Dual-stack buffers keep memory contiguous and cache-friendly.
  3. Discuss thread safety as a follow-up: inStack and outStack can have separate mutex locks for concurrent push/pop.

Quick Comprehension Check

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

1.What is the amortized time complexity of the pop() operation in the optimal two-stack approach?

2.When should elements be transferred from inStack to outStack?

3.What is the condition for MyQueue.empty() to return true?

Back to DSA Sheet