The O(n) Club: Implement Queue Using Stacks

The O(n) Club: Implement Queue Using Stacks — Stacking Your Odds

⚡ TL;DR

Turn two cranky stacks into a well-behaved queue. Only flip stacks when you absolutely must, so you won’t lose sleep over amortized time. Rough Java:

🧠 How Devs Usually Mess This Up

When faced with “queue using stacks,” many devs think:

🔍 What’s Actually Going On

Imagine a line at your favorite overhyped coffee shop: first in, first out. Every new customer hops onto stackIn like a true loyalist. Whenever the barista (stackOut) is empty, everyone in stackIn gets flipped over—now oldest is on top, ready for their single-origin espresso. stackOut only refills when it’s empty, so you won’t be shuffling all day. Only the coffee is overworked.

🛠️ PseudoCode

Empty check:

return stackIn.isEmpty() && stackOut.isEmpty();

Peek (peek()): Like pop() but without evicting anyone.

if (stackOut.isEmpty()) {
  while (!stackIn.isEmpty()) { stackOut.push(stackIn.pop()); }
}
return stackOut.peek();

Dequeue (pop()): Need the true front? Only transfer if stackOut is empty.

if (stackOut.isEmpty()) {
  while (!stackIn.isEmpty()) { stackOut.push(stackIn.pop()); }
}
return stackOut.pop();

Every element travels stack-to-stack only ONCE before leaving.

Enqueue (push(x)): Just slap it on stackIn. O(1). No drama.

stackIn.push(x);

💻 The Code

import java.util.Stack;
 public class MyQueue {
    private Stack&lt;Integer&gt; stackIn = new Stack&lt;&gt;();
    private Stack&lt;Integer&gt; stackOut = new Stack&lt;&gt;();
     public void push(int x) {
        stackIn.push(x);
    }
     public int pop() {
        if (stackOut.isEmpty()) {
            while (!stackIn.isEmpty()) {
                stackOut.push(stackIn.pop());
            }
        }
        return stackOut.pop();
    }
     public int peek() {
        if (stackOut.isEmpty()) {
            while (!stackIn.isEmpty()) {
                stackOut.push(stackIn.pop());
            }
        }
        return stackOut.peek();
    }
     public boolean empty() {
        return stackIn.isEmpty() &amp;&amp; stackOut.isEmpty();
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

Transferring on every pop: That’s a ticket to O(n²). Only transfer when stackOut is empty. Laziness wins.
Thinking it’s a circular queue: No modulo, no indices, just stack soap opera.
Pop/peek on empty: You’ll get a EmptyStackException. Interviewers love that segfault look. Handle with care.
Complexity check: Worst-case single op is O(n), but amortized across a series, it’s O(1). Go ahead, say “amortized” smugly in your interview.