114. Implement Stack using Queues

🔗 LeetCode Problem: 225. Implement Stack using Queues
📊 Difficulty: Easy
🏷️ Topics: Stack, Queue, Design

Problem Statement

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. - You can use two queues.

Example:

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

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

---

🌟 Understanding the Problem

The Behavior Difference

Stack (LIFO):

Plates stacked on table:
  push(1) → [1]
  push(2) → [2, 1]  (2 on top)
  push(3) → [3, 2, 1]  (3 on top)

  pop() → get 3 (last in, first out)

Queue (FIFO):

Line of people:
  add(1) → [1]
  add(2) → [1, 2]
  add(3) → [1, 2, 3]
          front → back

  remove() → get 1 (first in, first out)

The Challenge: Queue gives FIRST, we need LAST!

---

💡 Building Intuition - Two Different Ideas

Idea 1: What If We Had a Helper Queue?

Think about this scenario:

We have queue with: [1, 2, 3]
                    front → back

We want 3 (at the back).

What if we transfer all EXCEPT the last one to another queue?

Main queue:    [1, 2, 3]
Helper queue:  []

Transfer 1: 
  Main:   [2, 3]
  Helper: [1]

Transfer 2:
  Main:   [3]
  Helper: [1, 2]

Now main has only 3! Remove it!
  Main:   []
  Helper: [1, 2]

Then swap: Make helper become main
  Main:   [1, 2]
  Helper: []

We got 3 (the last element)!

The Pattern:

To pop:
  1. Transfer all except last to helper queue
  2. Pop the last element from main
  3. Swap the queues

This way we can get the LAST element!

Idea 2: What If We Rotate After Each Push?

Another way to think:

After adding element, what if we rotate the SAME queue?

Add 2 to [1]:
  Queue: [1, 2]

  Rotate:
    Remove 1, add back → [2, 1]

  Now 2 (newest) is at front!

For pop:
  Just remove from front → get 2 ✓

We only need ONE queue!

Let me teach you BOTH approaches properly!

---

🎯 Approach 1: Two Queues (Original Problem)

The Intuition

When do we need the second queue?

When we want to pop!

We need to get to the LAST element:
  → Transfer all elements EXCEPT last to helper
  → Pop the last one
  → Swap queues

The helper queue is like a "parking lot" for elements
while we get to the one we want.

The Strategy

push(x):
  Just add to queue1
  (No extra work needed!)

pop():
  Step 1: Transfer n-1 elements from queue1 to queue2
  Step 2: Pop the last element from queue1
  Step 3: Swap queue1 and queue2

top():
  Similar to pop, but don't remove the element
  (Transfer, peek, transfer back)

Visual Example

══════════════════════════════════════════════════════════
Setup: push(1), push(2), push(3)
══════════════════════════════════════════════════════════

After pushes:
  queue1: [1, 2, 3]
  queue2: []

══════════════════════════════════════════════════════════
Now: pop() - Want to get 3
══════════════════════════════════════════════════════════

Step 1: Transfer all except last from queue1 to queue2

  Transfer 1:
    queue1: [2, 3]
    queue2: [1]

  Transfer 2:
    queue1: [3]
    queue2: [1, 2]

Step 2: Pop from queue1
  result = 3
  queue1: []
  queue2: [1, 2]

Step 3: Swap queues
  queue1: [1, 2]  (was queue2)
  queue2: []      (was queue1)

Return: 3 ✓

Now queue1 has [1, 2] ready for next operation!

Implementation (Two Queues)

class MyStack {
    private Queue<Integer> queue1;
    private Queue<Integer> queue2;

    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    public void push(int x) {
        queue1.offer(x);
    }

    public int pop() {
        // Transfer all except last to queue2
        while (queue1.size() > 1) {
            queue2.offer(queue1.poll());
        }

        // Get the last element
        int result = queue1.poll();

        // Swap queues
        Queue<Integer> temp = queue1;
        queue1 = queue2;
        queue2 = temp;

        return result;
    }

    public int top() {
        // Transfer all except last to queue2
        while (queue1.size() > 1) {
            queue2.offer(queue1.poll());
        }

        // Peek at the last element
        int result = queue1.peek();

        // Transfer this element too
        queue2.offer(queue1.poll());

        // Swap queues
        Queue<Integer> temp = queue1;
        queue1 = queue2;
        queue2 = temp;

        return result;
    }

    public boolean empty() {
        return queue1.isEmpty();
    }
}

⏰ Time Complexity: - push(): O(1) - Just add to queue - pop(): O(n) - Transfer n-1 elements - top(): O(n) - Transfer n elements - empty(): O(1)

---

🎯 Approach 2: One Queue (Optimization)

The Realization

Do we really need TWO queues?

In Approach 1, we transfer elements from queue1 to queue2.

But what if... we transfer back to THE SAME queue?

Original: [1, 2, 3]
          front → back

Remove 1, add to back: [2, 3, 1]
Remove 2, add to back: [3, 1, 2]

Now 3 is at front!

We rotated within the SAME queue!
We don't need a second queue!

The Strategy

push(x):
  Step 1: Add x to queue
  Step 2: Rotate (size - 1) times
          (brings x to front)

pop():
  Just remove from front

top():
  Just peek at front

Visual Example

══════════════════════════════════════════════════════════
push(1):
══════════════════════════════════════════════════════════

Add 1: [1]
Rotate 0 times (size-1 = 0)

Queue: [1]

══════════════════════════════════════════════════════════
push(2):
══════════════════════════════════════════════════════════

Add 2: [1, 2]

Rotate 1 time (size-1 = 1):
  Remove 1, add back: [2, 1]

Queue: [2, 1]
       ↑
    newest at front!

══════════════════════════════════════════════════════════
push(3):
══════════════════════════════════════════════════════════

Add 3: [2, 1, 3]

Rotate 2 times (size-1 = 2):
  Remove 2, add back: [1, 3, 2]
  Remove 1, add back: [3, 2, 1]

Queue: [3, 2, 1]
       ↑
    newest at front!

══════════════════════════════════════════════════════════
pop():
══════════════════════════════════════════════════════════

Just remove from front: get 3 ✓

Queue: [2, 1]

Implementation (One Queue)

class MyStack {
    private Queue<Integer> queue;

    public MyStack() {
        queue = new LinkedList<>();
    }

    public void push(int x) {
        // Add new element
        queue.offer(x);

        // Rotate to bring x to front
        int size = queue.size();
        for (int i = 0; i < size - 1; i++) {
            queue.offer(queue.poll());
        }
    }

    public int pop() {
        return queue.poll();
    }

    public int top() {
        return queue.peek();
    }

    public boolean empty() {
        return queue.isEmpty();
    }
}

⏰ Time Complexity: - push(): O(n) - Rotate n-1 elements - pop(): O(1) - Just remove from front - top(): O(1) - Just peek at front - empty(): O(1)

---

🔍 Detailed Dry Run - Two Queue Approach

Operations: push(1), push(2), push(3), pop(), top()

═══════════════════════════════════════════════════════════
Operation: push(1)
═══════════════════════════════════════════════════════════

queue1.offer(1)

State:
  queue1: [1]
  queue2: []

═══════════════════════════════════════════════════════════
Operation: push(2)
═══════════════════════════════════════════════════════════

queue1.offer(2)

State:
  queue1: [1, 2]
  queue2: []

═══════════════════════════════════════════════════════════
Operation: push(3)
═══════════════════════════════════════════════════════════

queue1.offer(3)

State:
  queue1: [1, 2, 3]
  queue2: []

Stack view:
  3 ← top
  2
  1

═══════════════════════════════════════════════════════════
Operation: pop() - Want 3
═══════════════════════════════════════════════════════════

Step 1: Transfer all except last to queue2

  queue1.size() = 3
  Transfer while size > 1:

  Transfer 1:
    queue2.offer(queue1.poll())
    queue1: [2, 3]
    queue2: [1]

  Transfer 2:
    queue2.offer(queue1.poll())
    queue1: [3]
    queue2: [1, 2]

Step 2: Pop from queue1
  result = queue1.poll() = 3
  queue1: []
  queue2: [1, 2]

Step 3: Swap queues
  temp = queue1
  queue1 = queue2  → queue1: [1, 2]
  queue2 = temp    → queue2: []

Return: 3 ✓

State after pop:
  queue1: [1, 2]
  queue2: []

Stack view:
  2 ← top
  1

═══════════════════════════════════════════════════════════
Operation: top() - Want 2 (don't remove)
═══════════════════════════════════════════════════════════

Step 1: Transfer all except last to queue2

  Transfer 1:
    queue1: [2]
    queue2: [1]

Step 2: Peek at last element
  result = queue1.peek() = 2

Step 3: Transfer this element too (don't remove it!)
  queue2.offer(queue1.poll())
  queue1: []
  queue2: [1, 2]

Step 4: Swap queues
  queue1: [1, 2]
  queue2: []

Return: 2 ✓

State:
  queue1: [1, 2]  (unchanged from before)
  queue2: []

---

🎯 Comparing Both Approaches

Which One to Use?

                  Two Queues        One Queue
                  (Original)        (Optimized)
─────────────────────────────────────────────────
push()            O(1)              O(n)
pop()             O(n)              O(1)
top()             O(n)              O(1)
Space             2 queues          1 queue
Code              More complex      Simpler
Best for          Frequent push     Frequent pop

Problem asks:     Two queues ✓      Works too

When to Use Each?

Use Two Queues when:

- Problem specifically asks for two queues
- You push frequently, pop rarely
- Example: Building a stack for later processing

push(1), push(2), push(3), ... push(100)  ← All O(1)
pop() once ← One O(n) operation

Total: 100 × O(1) + 1 × O(n) = O(n)

Use One Queue when:

- You want simpler code
- You pop/top frequently
- Example: Undo functionality

push(action1)  ← O(n)
pop() (undo)   ← O(1)
push(action2)  ← O(n)
pop() (undo)   ← O(1)

Simpler to understand and implement

---

⚠️ Common Mistakes

Mistake 1: Not swapping queues (Two-queue approach)

// ❌ WRONG
public int pop() {
    while (queue1.size() > 1) {
        queue2.offer(queue1.poll());
    }
    return queue1.poll();
    // Forgot to swap! Next operation will fail
}

// ✓ CORRECT - Always swap
Queue<Integer> temp = queue1;
queue1 = queue2;
queue2 = temp;

Mistake 2: Wrong number of rotations (One-queue approach)

// ❌ WRONG - Rotating size times
for (int i = 0; i < queue.size(); i++) {
    queue.offer(queue.poll());
}
// Brings element back to same position!

// ✓ CORRECT - Rotate (size - 1) times
int size = queue.size();  // Store first!
for (int i = 0; i < size - 1; i++) {
    queue.offer(queue.poll());
}

Mistake 3: Using queue.size() in loop condition

// ❌ WRONG - Size changes during loop
for (int i = 0; i < queue.size() - 1; i++) {
    queue.offer(queue.poll());
}

// ✓ CORRECT - Store size before loop
int size = queue.size();
for (int i = 0; i < size - 1; i++) {
    queue.offer(queue.poll());
}

---

🎯 The Core Insights

For Two Queues:

"Use helper queue as temporary storage.
 Transfer all except target element.
 Then swap queues."

When you pop:
  Main → Helper (transfer all except last)
  Pop last from Main
  Swap (Helper becomes Main)

For One Queue:

"Rotate within the same queue.
 Keep newest always at front."

When you push:
  Add new element
  Rotate to bring it to front

---

🧠 Interview Strategy

If asked for TWO queues:

"I'll use two queues. One is main, one is helper.

For push: Just add to main queue - O(1)

For pop: 
  Transfer all except last to helper - O(n)
  Pop the last element
  Swap queues

This way push is fast, pop is slower.
Good when we push frequently."

If asked for optimal:

"I can optimize to one queue.

After each push, rotate the queue
to bring the new element to front.

Then pop/top are just O(1) operations.

Trade-off: Push becomes O(n), but pop is O(1).
Better when we pop frequently."

---

📝 Quick Revision

Two-Queue Approach: - push: O(1) - just add - pop: O(n) - transfer, pop, swap - Best when: frequent push, rare pop

One-Queue Approach: - push: O(n) - add, then rotate (size-1) times - pop: O(1) - just remove from front - Best when: frequent pop, rare push

import java.util.LinkedList;
import java.util.Queue;

// // Approach 1 - using single queue.
// class MyStack {
//   Queue<Integer> queue;

//   public MyStack() {
//     queue = new LinkedList<>();    
//   }

//   public void push(int x) {
//     // push(1) => [1]
//     // push(2) => [1, 2] => make it [2, 1]
//     // push(3) => [2, 1, 3] => make it [1, 3, 2] => again make it [3, 2, 1]
//     // We can actually do at pop side also. It depends on use case.
//     // If pop or top operations are heavy, do it at push side all this.
//     // If pop operations are less, do it at pop side.
//     queue.add(x);

//     int size = queue.size();
//     for(int i = 0; i < size - 1; i++) {
//       queue.add(queue.poll());
//     }
//   }

//   public int pop() {
//     return queue.poll();
//   }

//   public int top() {
//     return queue.peek();
//   }

//   public boolean empty() {
//     return queue.isEmpty();
//   }
// }

// Approach 2 - using 2 queues as asked in question - little tricky
class MyStack {
  Queue<Integer> queue1;
  Queue<Integer> queue2;

  public MyStack() {
    queue1 = new LinkedList<>();
    queue2 = new LinkedList<>();
  }

  public void push(int x) {
    // simply push
    queue1.add(x);    
  }

  public int pop() {
    // make use of 2nd queue here.
    // Step 1: transfer all elements from Q1 to Q2 except the last one.
    int size = queue1.size();
    for(int i = 0; i < size - 1; i++) {
      queue2.add(queue1.poll());
    }

    // Step 2: remove the required element from Q1.
    int top = queue1.poll();

    // Step 3: change the references (SWAP) for next push or pop.
    Queue<Integer> temp = queue1;
    queue1 = queue2;
    queue2 = temp;

    return top;
  }

  public int top() {
    // same logic as of pop except that we do not remove the element from Q1.
    // we save that and push to Q2.
    int size = queue1.size();
    for(int i = 0; i < size - 1; i++) {
      queue2.add(queue1.poll());
    }

    // Step 2: save the required element from Q1.
    int top = queue1.poll();

    // Step 3: push the saved element to Q2.
    queue2.add(top);

    // Step 3: change the references (SWAP) for next push or pop.
    Queue<Integer> temp = queue1;
    queue1 = queue2;
    queue2 = temp;

    return top;
  }

  public boolean empty() {
    return queue1.isEmpty();
  }
}

class Solution {
  public static void main(String[] args) {
    Solution s = new Solution();
    MyStack myStack = new MyStack();
    myStack.push(1);
    myStack.push(2);
    myStack.push(3);
    System.out.println(myStack.top());
    // System.out.println(myStack.pop());
    // System.out.println(myStack.empty());
  }
}

Both work! Choose based on usage pattern.

---

🎉 Summary

The Problem: Stack (LIFO) using Queue (FIFO)

Two Solutions: 1. Two Queues: Transfer to helper, swap 2. One Queue: Rotate to maintain order

Key Insight: - Two queues: Helper for temporary storage - One queue: Rotation transforms FIFO → LIFO

Choose based on: What operation is more frequent?

---

Happy practicing! 🎯

Note: Problem originally asks for TWO queues, so that's the expected solution. But knowing the one-queue optimization shows deeper understanding! 💪✨