Cracking The Coding Interview Together – Problem 3.4: Queue via Stacks

In this edition of Cracking The Coding Interview — Together, we tackle a classic structural challenge: building a Queue using only Stacks. It sounds simple, but the efficiency of your data movement defines whether your solution is "interview-ready." We break down the intuition, the "lazy" transfer strategy, Java implementation, and time complexity.

As always, we’ll follow the same structure that you would use in a real interview.

1. Understand the problem statement together
2. Ask any questions, that you would like to ask the interviewer
3. I would urge you to take your time here and try to come up with your own solution before going forward
4. Think how you would go about solving the problem(you would be talking out loud in front of the actual interviewer)
5. Write code and understand how it works and explain it to your interviewer

Problem statement

Queue via Stacks: Implement a MyQueue class which implements a queue using two stacks.

As a reminder:

• Stack: LIFO (Last-In, First-Out) — like a stack of plates.
• Queue: FIFO (First-In, First-Out) — like a line at a coffee shop.

Your goal is to make two "Last-In" structures behave like a "First-In" structure.

Analyse the problem statement together

The core difference between a stack and a queue is the order of removal.

If we push 1, 2, 3 into a stack, we get 3, 2, 1 back. If we enqueue 1, 2, 3 into a queue, we get 1, 2, 3 back.

To get 1 out first from a stack where it sits at the bottom, we have to move everything on top of it somewhere else.

👉 The "Double Reversal" Trick If you take elements from Stack A and push them into Stack B, the order is reversed. If you then pop from Stack B, you are effectively popping in the original order.

Example:

1. Push 1, 2, 3 into stackNewest: [1, 2, 3] (top is 3)
2. Move all to stackOldest: [3, 2, 1] (top is 1)
3. Pop from stackOldest: Returns 1.

Success! We have FIFO behavior.

Questions for the interviewer

Before writing code, let's clarify the constraints:

1. What should peek() or pop() do if the queue is empty? (Throw an exception or return null?)
2. Is thread safety a concern? (Usually not in a standard algorithmic interview, but good to ask).
3. Should we optimize for push or pop? (In most cases, we want to avoid moving elements back and forth unnecessarily).

Let’s assume:

• Throw EmptyStackException if empty.
• Focus on Amortized time complexity (making the operations efficient over time).

Think about the Solution

To truly master this problem, you have to move past the "how" and into the "why." Let's pull back the curtain on the mental process of an engineer optimizing for performance.

Think about the Solution (Deep Dive)

When you first hear "Queue using Stacks," your brain likely creates a conflict. A Stack is a LIFO (Last-In, First-Out) structure, while a Queue is FIFO (First-In, First-Out). To bridge this gap, we need a way to "reverse the reversal."

1. The Strategy: Two Stacks, Two Roles

Instead of treating both stacks as equal, we assign them specific "zones" of responsibility:

• stackNewest (The Intake Zone): This stack handles all incoming data. Whenever someone calls add(), we push it here. The most recent elements are always at the top.
• stackOldest (The Service Zone): This stack handles all outgoing data. The oldest elements—the ones that need to be dequeued first—are at the top of this stack.

2. The Logic of the "Flip"

The magic happens when stackOldest is empty. Imagine we've added 1, 2, 3 to stackNewest.

• stackNewest looks like: [1, 2, 3] (where 3 is the top).
• To get 1 (the oldest), we must move 3, then 2, then 1 into stackOldest.
• After the move, stackOldest looks like: [3, 2, 1] (where 1 is now the top!).

3. Why This is "Lazy" (And Why That's Good)

A common mistake is moving elements back to stackNewest after every pop(). This is incredibly inefficient—like moving all the groceries out of your car, taking one bag inside, and then putting the rest back in the car.

Instead, we use Lazy Evaluation:

1. Keep elements in stackOldest as long as possible.
2. Only transfer from stackNewest when stackOldest is completely empty.
3. Once the transfer happens, stackOldest is perfectly ordered for FIFO until it's empty again.

4. The "Aha!" Moment: Amortized Analysis

If you have 1,000 elements in stackNewest and you call pop(), that specific call is "expensive" (O(N)) because it has to move all 1,000 elements.

However, notice that for those 1,000 elements, you will never have to move them again. They will be popped from stackOldest in O(1) time. When you average the cost of that one expensive move over the 1,000 cheap pops, the "amortized" cost is just O(1) per operation.

Write code and explain

Now let’s translate this idea into code.

Java code

import java.util.Stack;
import java.util.EmptyStackException;

public class MyQueue<T> {
    private Stack<T> stackNewest, stackOldest;

    public MyQueue() {
        stackNewest = new Stack<T>();
        stackOldest = new Stack<T>();
    }

    public int size() {
        return stackNewest.size() + stackOldest.size();
    }

    public void add(T value) {
        // Push onto stackNewest, which has the newest elements on top
        stackNewest.push(value);
    }

    private void shiftStacks() {
        if (stackOldest.isEmpty()) {
            while (!stackNewest.isEmpty()) {
                stackOldest.push(stackNewest.pop());
            }
        }
    }

    public T peek() {
        shiftStacks();
        if (stackOldest.isEmpty()) throw new EmptyStackException();
        return stackOldest.peek();
    }

    public T remove() {
        shiftStacks();
        if (stackOldest.isEmpty()) throw new EmptyStackException();
        return stackOldest.pop();
    }
}

Explain the Code in Plain English

• Two Stacks: We use stackNewest as our "inbox" and stackOldest as our "outbox."
• shiftStacks(): This is the heart of the class. It only moves data when necessary. If our "outbox" is empty, we flip the "inbox" into it. This puts the oldest elements at the top, ready to be served.
• Efficiency: We don't move elements back to stackNewest. They stay in stackOldest until they are popped. This is "lazy evaluation" in practice.

Time & Space Complexity

Time Complexity

• Push: O(1)
• Pop/Peek: O(1) Amortized.
  • Wait, why? Although a single pop might take O(N) if we have to move elements, any element is only moved from stackNewest to stackOldest once. Over N operations, the total work is O(N), making the average cost per operation constant.

Space Complexity

• O(N): We are storing N elements across two stacks. No extra overhead.

Final Thoughts

This problem tests if you can think beyond "brute force" movement. In a real system, moving data is expensive. By using the "Lazy Transfer" approach, we minimize movement and achieve high performance.

Interviewers love this problem because it forces you to manage the state of two different structures simultaneously.

Are you just reading, or are you coding? Try implementing this with a Deque instead of Stack for better performance in Java, or try handling the EmptyStackException more gracefully.

I’ll see you in the next one.

Happy Coding.

And that is what interviews are actually testing.At first glance, this problem feels simple.

“Just use multiple stacks.”

But the follow-up exposes whether you truly understand stack behavior and abstraction.

That is the beauty of these problems.

We are not memorizing solutions.

We are training our thinking.

If you followed along properly, paused, thought through edge cases, and mentally executed the code — you are improving.

If you simply read through it…

You know the answer already.

I’ll see you in the next one.

Happy Coding.