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

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:

// Java: Two stacks, cheap enqueue, lazy dequeue
Stack<Integer> in = new Stack<>();
Stack<Integer> out = new Stack<>();
 void push(int x) { in.push(x); }
 int pop() {
    if (out.isEmpty())
        while (!in.isEmpty()) out.push(in.pop());
    return out.pop();
}

🧠 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

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

  stackIn.push(x);

• 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.
• Peek (peek()): Like pop() but without evicting anyone.

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

• Empty check:

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

💻 The Code

import java.util.Stack;
 public class MyQueue {
    private Stack<Integer> stackIn = new Stack<>();
    private Stack<Integer> stackOut = new Stack<>();
     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() && 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.

🧠 Interviewer Brain-Tattoo

“To queue with stacks, be lazy. Move only when you must—like a true engineer.”