Stacks and Queues

Stack Push/Pop

Push values onto a stack and pop them back in last-in, first-out order.

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> stack = new ArrayDeque<>();
        for (int value : new int[] {10, 20, 30}) stack.push(value);
        List<Integer> popped = new ArrayList<>();
        while (!stack.isEmpty()) popped.add(stack.pop());
        System.out.println(render(popped));
    }
}

The same three values from the trace are shown as stack states. The top cell is the next value a pop removes.

Step 1 - Start empty

There is no top value yet.

Empty stack before any push.top of stack(empty)

Step 2 - Push 10, then 20, then 30

Each push places the new value above the previous top.

After push 10, push 20, push 30: 30 is on top.top -> bottom302010

Step 3 - Pop removes 30 first

The top cell leaves first, so the remaining stack starts with 20.

After one pop: popped is 30; 20 is now on top.top -> bottompopped203010

Complexity

  • Time: O(1) per push/pop
  • Space: O(n)

Implementation notes

  • Java declares the stack as Deque<Integer> and backs it with new ArrayDeque<>(), using deque methods as stack operations instead of 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 stack.push(value) autoboxes through Integer.valueOf, so these small fixture values may be cached Integer instances, and mutates the stack.
  • Pop uses while (!stack.isEmpty()) popped.add(stack.pop()). pop() removes the current top and would throw on an empty deque, so the isEmpty guard is the checked empty behavior here.
  • The replay-visible stack uses logical stack notation, not ArrayDeque iteration order: it shows [10, 20, 30] after pushes and pops 30 first, then 20 and 10, producing popped = [30, 20, 10]. The ArrayDeque, ArrayList, any uncached boxed integers, and StringBuilder output are normal JVM heap objects managed by GC.
top The top is the most recently pushed value.
LIFO A stack removes values in last-in, first-out order.