Command Palette

Search for a command to run...

Hectal

Lesson 9.1 · Stack and Monotonic Stack

How a Stack Works

Push onto the top, pop from the top, peek at the top. All O(1). Use ArrayDeque, not the old Stack class.

10 min

Think of it like this

A stack of plates in a canteen: you add a clean plate on top and take the top plate when you need one. You never pull a plate from the middle. The last plate put down is the first one picked up.

1.The three operations

push(x) puts x on top, pop() removes and returns the top, peek() returns the top without removing it. Each is O(1). Checking isEmpty() before popping avoids exceptions.

In Java, use Deque<Integer> stack = new ArrayDeque<>(). The legacy Stack class is synchronised (slower) and extends Vector, so it also allows non-stack operations.

StackDemo.java
import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    public static void main(String[] args) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(4);
        stack.push(7);
        System.out.println(stack.pop());     // 7
        stack.push(9);
        System.out.println(stack.peek());    // 9
        System.out.println(stack.size());    // 2
        System.out.println(stack);           // top first
    }
}

Output

7
9
2
[9, 4]
▶ Dry run: Push, push, pop, push, peekpush 4, push 7, pop, push 9, peek

stack(stack)

4

Step 1/5push 4: the stack holds 4.

2.Where stacks hide

The call stack: every method call pushes a frame and every return pops one, which is why recursion can be rewritten with an explicit stack. Undo history, browser back buttons, and depth-first search all use stacks.

Remember

  • LIFO: last in, first out.
  • push, pop, peek are O(1).
  • Use ArrayDeque as a stack in Java.
  • Check isEmpty() before pop() or peek().

Common mistakes

  • Using Stack or LinkedList out of habit.
  • Popping from an empty stack (NoSuchElementException with ArrayDeque).

Words used in this lesson

LIFO
Last in, first out.
Top
The end of the stack where items are added and removed.
Call stack
The stack of active method calls in a running program.