Stacks and Queues

Stack Push/Pop

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

Algorithm

The replay uses the same three values in every language, so this Java DSA implementation can be compared directly with the rest of the DSA track.

top The top is the most recently pushed value.
LIFO A stack removes values in last-in, first-out order.

Visual walkthrough

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

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));
    }
}

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.