Leetcode - Implement Queue Using Stacks Solution

Implementing a queue using only two stacks sounds impossible at first. Queues are FIFO (First In, First Out) and stacks are LIFO (Last In, First Out). They're opposites! But there's a clever trick: if you reverse a stack twice, you get the original order back. That's the key insight that makes this problem solvable.

The solution uses one stack as an "inbox" for incoming elements and another as an "outbox" for outgoing elements. When we need to pop or peek, we transfer elements from inbox to outbox only when needed, which reverses their order and makes the front of the queue accessible.

The Problem

I needed to implement a queue with these operations:

• push(x): Add element to the end
• pop(): Remove element from the front
• peek(): Look at front element without removing
• empty(): Check if queue is empty

But I could only use stack operations: push, pop, peek, and checking if empty.

My Initial Confusion

I was confused at first. "How can I get the first element out when stacks only let me access the top?" Then I realized: if I reverse a stack, I get the elements in reverse order. And if I reverse it twice, I'm back to the original order!

The Insight

The key idea: use one stack as an "inbox" and another as an "outbox":

• When pushing, just push to inbox
• When popping or peeking, if outbox is empty, transfer all elements from inbox to outbox (this reverses them!)
• Now the front of the queue is at the top of outbox

My Solution

class MyQueue {
  constructor() {
    this.inbox = []; // Stack for incoming elements
    this.outbox = []; // Stack for outgoing elements
  }

  push(x) {
    // Just push to inbox - simple!
    this.inbox.push(x);
  }

  pop() {
    // Make sure outbox has elements
    this.moveInboxToOutbox();
    // Pop from outbox (this is the front of the queue)
    return this.outbox.pop();
  }

  peek() {
    // Make sure outbox has elements
    this.moveInboxToOutbox();
    // Look at top of outbox without removing
    return this.outbox[this.outbox.length - 1];
  }

  empty() {
    // Queue is empty if both stacks are empty
    return this.inbox.length === 0 && this.outbox.length === 0;
  }

  // Helper: transfer inbox to outbox when outbox is empty
  moveInboxToOutbox() {
    if (this.outbox.length === 0) {
      // Transfer all elements from inbox to outbox
      // This reverses the order, so first-in becomes first-out!
      while (this.inbox.length > 0) {
        this.outbox.push(this.inbox.pop());
      }
    }
  }
}

How It Works

Let me trace through an example:

1. push(1): inbox = [1], outbox = []
2. push(2): inbox = [1, 2], outbox = []
3. push(3): inbox = [1, 2, 3], outbox = []
4. pop(): Transfer inbox to outbox → outbox = [3, 2, 1], inbox = []
   • Pop from outbox → returns 1 (correct! first in, first out)
5. push(4): inbox = [4], outbox = [3, 2]
6. pop(): outbox not empty, so pop → returns 2 (correct!)

Why This Is Efficient

The key insight: we only transfer when outbox is empty. So:

• Push is always O(1)
• Pop is amortized O(1). Each element is transferred at most once.
• The transfer cost is "spread out" over multiple operations

What I Learned

This problem taught me:

• Data structures can simulate other data structures
• Amortized analysis helps understand "average" performance
• Sometimes the solution is simpler than you think
• Reversing a stack twice gives you the original order

Key Takeaways

• Two stacks can simulate a queue by using one as inbox and one as outbox
• Transfer only when needed (lazy evaluation)
• Amortized O(1) operations even though individual operations might be O(n)
• This pattern appears in other problems too

I found this problem really satisfying because it showed how creative thinking can solve seemingly impossible constraints. The two-stack approach is elegant and efficient!