Stacks and Queues

Queue from Two Stacks

Implement queue behavior with an input stack and an output stack.

Algorithm

Basic Implementation

Basic.java 
import java.util.*;

public class Basic {
    static String render(List<Integer> values) {
        StringBuilder out = new StringBuilder();
        for (int i = 0; i < values.size(); i++) {
            if (i > 0) out.append(" -> ");
            out.append(values.get(i));
        }
        return out.toString();
    }
    public static void main(String[] args) {
        Deque<Integer> inStack = new ArrayDeque<>();
        Deque<Integer> outStack = new ArrayDeque<>();
        for (int value : new int[] {10, 20, 30}) inStack.push(value);
        while (!inStack.isEmpty()) outStack.push(inStack.pop());
        List<Integer> removed = new ArrayList<>();
        while (!outStack.isEmpty()) removed.add(outStack.pop());
        System.out.println(render(removed));
    }
}

The two-stack queue keeps cheap enqueues in the input stack, then reverses that stack only when dequeue needs the output stack.

Step 1 - Enqueue pushes onto the input stack

After enqueueing 10, 20, 30, the newest input value is on top of the input stack.

After enqueues: input top is 30; output is empty.input stack top -> bottomoutput stack top -> bottomremoved30(empty)(empty)2010

Step 2 - Transfer reverses into output order

Moving every input value to the output stack turns 10 into the next pop.

After transfer: output top is 10, so dequeue returns the oldest value.input stackoutput stack top -> bottomremoved(empty)10(empty)2030

Step 3 - Dequeue pops from output

The output stack pops 10 first while 20 becomes the next front.

After one dequeue: removed is 10; output top is now 20.input stackoutput stack top -> bottomremoved(empty)201030

Complexity

  • Time: O(1) amortized per operation
  • Space: O(n)

Implementation notes

  • Java declares both stacks as Deque<Integer> and backs them with new ArrayDeque<>(), using deque operations as stack operations rather than the legacy Stack class. push and pop operate at the deque head.
  • The enhanced for loop reads primitive values from new int[] {10, 20, 30}; each inStack.push(value) autoboxes through Integer.valueOf, so these small fixture values may be cached Integer instances, and mutates the input stack.
  • Transfer is explicit: while inStack is not empty, outStack.push(inStack.pop()) pops the newest input-stack value and pushes it onto the output stack, reversing stack order so later outStack.pop() calls produce FIFO queue order.
  • The replay-visible states use logical stack notation, not ArrayDeque iteration order: in grows to [10, 20, 30], transfer leaves in empty and out as [30, 20, 10], then removed becomes [10, 20, 30]. The two ArrayDeque instances, ArrayList, any uncached boxed integers, and StringBuilder output are normal JVM heap objects managed by GC.
input stack Enqueue pushes new values onto the input stack.
output stack When the output stack is empty, transferring all input values reverses them into dequeue order.