PK

PKBytes

Explore tracks
Chapter 12: Stacks and Stack-Based Algorithms
12.01Beginner / Intermediate8 topics12 min5 interactive animations

Stack model

The stack abstract data type: last-in first-out order, the operations push, pop, peek and isEmpty, what overflow and underflow mean, and the difference between fixed and resizable stacks.

Learning goals

  • State the LIFO rule and the stack operations
  • Explain underflow and overflow
  • Distinguish fixed-capacity from resizable stacks

Prerequisites

Arrays and dynamic arrays
12.01.1

LIFO

A stack is a collection with one open end, the top. The element added most recently is the first to be removed: last in, first out (LIFO). Think of a stack of plates. This order matches many natural problems: undoing the latest action, matching the most recent open bracket, returning from the innermost function call.

Only the top element is ever accessible, which is what makes every operation O(1).

Sequence of operationsStack after (bottom to top)Returned
push 1, push 2, push 31, 2, 3-
pop1, 23
push 41, 2, 4-
pop, pop14, then 2
12.01.2

Abstract data type

As an abstract data type a stack is defined by its operations and their behaviour, not by its storage: push(x), pop(), peek(), isEmpty() and usually size(). The same interface can be implemented with an array, a linked list or a dynamic array, and callers should not care which. In Java code you declare Deque<Integer> stack = new ArrayDeque<>(); and use only the stack operations.

The next lesson shows the implementations.

Java
1interface IntStack {
2    void push(int x);
3    int pop();            // removes and returns the top
4    int peek();           // returns the top without removing it
5    boolean isEmpty();
6    int size();
7}
12.01.3

Push

push(x) places x on top of the stack in O(1): write it at index size and increment the size (array), or make it the new head (linked list). With a fixed-capacity array it must first check for overflow.

Push values in the animation and watch the top move.

Java
1Deque<Integer> stack = new ArrayDeque<>();
2stack.push(10);      // addFirst: the top is the front of the deque
3stack.push(20);
4System.out.println(stack);      // [20, 10]: the top comes first when printed

Array-backed stack: push, pop, peek, overflow and underflow

Interactive · edit the input

Your input

Try

data[] · capacity 3 · size 0

0
1
2
Setup

An empty stack backed by an array of 3. The top is data[size - 1]; push and pop only touch the end, so both are O(1).

Step 1 / 11
Java
1class ArrayStack {
2    private int[] data; private int size;
3    ArrayStack(int capacity) { data = new int[capacity]; }
4    void push(int x) {
5        if (size == data.length) data = Arrays.copyOf(data, data.length * 2);   // resizable; a fixed stack rejects instead
6        data[size++] = x;
7    }
8    int pop() {
9        if (size == 0) throw new NoSuchElementException("stack underflow");
10        return data[--size];
11    }
12    int peek() {
13        if (size == 0) throw new NoSuchElementException("stack underflow");
14        return data[size - 1];                      // look without removing
15    }
16    boolean isEmpty() { return size == 0; }
17}

Live state

size

0

capacity

3

No condition evaluated on this step
Execution trace (dry run table)Show 11 steps
StepLineStateWhat happens
1L3size=0 capacity=3An empty stack backed by an array of 3. The top is data[size - 1]; push and pop only touch the end, so both are O(1).
2L6op=push(5) size=1 top=5data[size++] = 5: 5 is the new top.
3L6op=push(8) size=2 top=8data[size++] = 8: 8 is the new top.
4L6op=push(3) size=3 top=3data[size++] = 3: 3 is the new top.
5L14op=peek() top=3 size=3peek() returns 3 without removing it: size stays 3.
6L10op=pop() returned=3 size=2Return data[--size] = 3: the most recently pushed value leaves first (LIFO). The slot is simply ignored from now on.
7L10op=pop() returned=8 size=1Return data[--size] = 8: the most recently pushed value leaves first (LIFO). The slot is simply ignored from now on.
8L10op=pop() returned=5 size=0Return data[--size] = 5: the most recently pushed value leaves first (LIFO). The slot is simply ignored from now on.
9L9op=pop() size=0 errors=1pop() on an empty stack: underflow. Java's ArrayDeque.pop throws NoSuchElementException; poll() would return null.
10L6op=push(7) size=1 top=7data[size++] = 7: 7 is the new top.
11L16size=1 errors=1 return=[7]Final stack (bottom to top): [7]; 1 rejected operation.
12.01.4

Pop

pop() removes and returns the top element in O(1): decrement the size and return the element at that index. The vacated slot can be ignored (or set to null for object stacks so the garbage collector can reclaim the object). Pop on an empty stack is an error.

Pop returns values in reverse order of pushing.

Java
1Deque<Integer> stack = new ArrayDeque<>(List.of(3, 2, 1));   // top is 3
2int a = stack.pop();    // 3
3int b = stack.pop();    // 2

Array-backed stack: push, pop, peek, overflow and underflow

Interactive · edit the input

Your input

Try

data[] · capacity 3 · size 0

0
1
2
Setup

An empty stack backed by an array of 3. The top is data[size - 1]; push and pop only touch the end, so both are O(1).

Step 1 / 11
Java
1class ArrayStack {
2    private int[] data; private int size;
3    ArrayStack(int capacity) { data = new int[capacity]; }
4    void push(int x) {
5        if (size == data.length) data = Arrays.copyOf(data, data.length * 2);   // resizable; a fixed stack rejects instead
6        data[size++] = x;
7    }
8    int pop() {
9        if (size == 0) throw new NoSuchElementException("stack underflow");
10        return data[--size];
11    }
12    int peek() {
13        if (size == 0) throw new NoSuchElementException("stack underflow");
14        return data[size - 1];                      // look without removing
15    }
16    boolean isEmpty() { return size == 0; }
17}

Live state

size

0

capacity

3

No condition evaluated on this step
Execution trace (dry run table)Show 11 steps
StepLineStateWhat happens
1L3size=0 capacity=3An empty stack backed by an array of 3. The top is data[size - 1]; push and pop only touch the end, so both are O(1).
2L6op=push(5) size=1 top=5data[size++] = 5: 5 is the new top.
3L6op=push(8) size=2 top=8data[size++] = 8: 8 is the new top.
4L6op=push(3) size=3 top=3data[size++] = 3: 3 is the new top.
5L14op=peek() top=3 size=3peek() returns 3 without removing it: size stays 3.
6L10op=pop() returned=3 size=2Return data[--size] = 3: the most recently pushed value leaves first (LIFO). The slot is simply ignored from now on.
7L10op=pop() returned=8 size=1Return data[--size] = 8: the most recently pushed value leaves first (LIFO). The slot is simply ignored from now on.
8L10op=pop() returned=5 size=0Return data[--size] = 5: the most recently pushed value leaves first (LIFO). The slot is simply ignored from now on.
9L9op=pop() size=0 errors=1pop() on an empty stack: underflow. Java's ArrayDeque.pop throws NoSuchElementException; poll() would return null.
10L6op=push(7) size=1 top=7data[size++] = 7: 7 is the new top.
11L16size=1 errors=1 return=[7]Final stack (bottom to top): [7]; 1 rejected operation.
12.01.5

Peek

peek() (also called top()) returns the top element without removing it, O(1). It lets you inspect before deciding to pop, as in monotonic stack algorithms. On an empty stack Deque.peek() returns null, whereas ArrayDeque.pop() throws.

Use -1 in the operations field of the animation to peek.

Java
1Deque<Integer> stack = new ArrayDeque<>();
2Integer none = stack.peek();    // null when empty
3stack.push(7);
4int top = stack.peek();         // 7, still on the stack

Array-backed stack: push, pop, peek, overflow and underflow

Interactive · edit the input

Your input

Try

data[] · capacity 3 · size 0

0
1
2
Setup

An empty stack backed by an array of 3. The top is data[size - 1]; push and pop only touch the end, so both are O(1).

Step 1 / 11
Java
1class ArrayStack {
2    private int[] data; private int size;
3    ArrayStack(int capacity) { data = new int[capacity]; }
4    void push(int x) {
5        if (size == data.length) data = Arrays.copyOf(data, data.length * 2);   // resizable; a fixed stack rejects instead
6        data[size++] = x;
7    }
8    int pop() {
9        if (size == 0) throw new NoSuchElementException("stack underflow");
10        return data[--size];
11    }
12    int peek() {
13        if (size == 0) throw new NoSuchElementException("stack underflow");
14        return data[size - 1];                      // look without removing
15    }
16    boolean isEmpty() { return size == 0; }
17}

Live state

size

0

capacity

3

No condition evaluated on this step
Execution trace (dry run table)Show 11 steps
StepLineStateWhat happens
1L3size=0 capacity=3An empty stack backed by an array of 3. The top is data[size - 1]; push and pop only touch the end, so both are O(1).
2L6op=push(5) size=1 top=5data[size++] = 5: 5 is the new top.
3L6op=push(8) size=2 top=8data[size++] = 8: 8 is the new top.
4L6op=push(3) size=3 top=3data[size++] = 3: 3 is the new top.
5L14op=peek() top=3 size=3peek() returns 3 without removing it: size stays 3.
6L10op=pop() returned=3 size=2Return data[--size] = 3: the most recently pushed value leaves first (LIFO). The slot is simply ignored from now on.
7L10op=pop() returned=8 size=1Return data[--size] = 8: the most recently pushed value leaves first (LIFO). The slot is simply ignored from now on.
8L10op=pop() returned=5 size=0Return data[--size] = 5: the most recently pushed value leaves first (LIFO). The slot is simply ignored from now on.
9L9op=pop() size=0 errors=1pop() on an empty stack: underflow. Java's ArrayDeque.pop throws NoSuchElementException; poll() would return null.
10L6op=push(7) size=1 top=7data[size++] = 7: 7 is the new top.
11L16size=1 errors=1 return=[7]Final stack (bottom to top): [7]; 1 rejected operation.
12.01.6

IsEmpty

isEmpty() reports whether the stack has no elements, O(1). Check it before pop or peek unless the algorithm guarantees the stack is non-empty (for example after pushing a sentinel). Prefer isEmpty() over size() == 0 for clarity.

Many stack loops have the form while (!stack.isEmpty() && condition).

Java
1Deque<Integer> stack = new ArrayDeque<>();
2while (!stack.isEmpty() && stack.peek() < x) stack.pop();   // short-circuit: peek is only called when non-empty
12.01.7

Underflow

Underflow is popping or peeking an empty stack. ArrayDeque.pop() throws NoSuchElementException, poll() and peek() return null instead, and the legacy Stack throws EmptyStackException. Handle it by checking isEmpty() first, or by returning a sentinel. Underflow in an expression parser usually means the input was malformed.

Try the Underflow preset in the animation.

Java
1Deque<Integer> stack = new ArrayDeque<>();
2try { stack.pop(); } catch (NoSuchElementException e) { System.out.println("underflow"); }
3Integer safe = stack.pollFirst();     // null instead of an exception

Array-backed stack: push, pop, peek, overflow and underflow

Interactive · edit the input

Your input

Try

data[] · capacity 3 · size 0

0
1
2
Setup

An empty stack backed by an array of 3. The top is data[size - 1]; push and pop only touch the end, so both are O(1).

Step 1 / 11
Java
1class ArrayStack {
2    private int[] data; private int size;
3    ArrayStack(int capacity) { data = new int[capacity]; }
4    void push(int x) {
5        if (size == data.length) data = Arrays.copyOf(data, data.length * 2);   // resizable; a fixed stack rejects instead
6        data[size++] = x;
7    }
8    int pop() {
9        if (size == 0) throw new NoSuchElementException("stack underflow");
10        return data[--size];
11    }
12    int peek() {
13        if (size == 0) throw new NoSuchElementException("stack underflow");
14        return data[size - 1];                      // look without removing
15    }
16    boolean isEmpty() { return size == 0; }
17}

Live state

size

0

capacity

3

No condition evaluated on this step
Execution trace (dry run table)Show 11 steps
StepLineStateWhat happens
1L3size=0 capacity=3An empty stack backed by an array of 3. The top is data[size - 1]; push and pop only touch the end, so both are O(1).
2L6op=push(5) size=1 top=5data[size++] = 5: 5 is the new top.
3L6op=push(8) size=2 top=8data[size++] = 8: 8 is the new top.
4L6op=push(3) size=3 top=3data[size++] = 3: 3 is the new top.
5L14op=peek() top=3 size=3peek() returns 3 without removing it: size stays 3.
6L10op=pop() returned=3 size=2Return data[--size] = 3: the most recently pushed value leaves first (LIFO). The slot is simply ignored from now on.
7L10op=pop() returned=8 size=1Return data[--size] = 8: the most recently pushed value leaves first (LIFO). The slot is simply ignored from now on.
8L10op=pop() returned=5 size=0Return data[--size] = 5: the most recently pushed value leaves first (LIFO). The slot is simply ignored from now on.
9L9op=pop() size=0 errors=1pop() on an empty stack: underflow. Java's ArrayDeque.pop throws NoSuchElementException; poll() would return null.
10L6op=push(7) size=1 top=7data[size++] = 7: 7 is the new top.
11L16size=1 errors=1 return=[7]Final stack (bottom to top): [7]; 1 rejected operation.
12.01.8

Fixed vs resizable stack

A fixed-capacity stack has an array of constant size and rejects a push when full (overflow). A resizable stack allocates a larger array (typically double) and copies, so pushes cost amortised O(1). Fixed stacks give predictable memory, which suits embedded code and recursion limits; resizable ones are the default in libraries. Java's call stack is a fixed-size stack, and overflowing it throws StackOverflowError.

Switch the animation between the two policies and push past the capacity.

Fixed capacityResizable
When fullreject or throwallocate a bigger array and copy
push costO(1)amortised O(1), O(n) on a resize
Memorypredictableup to 2× the used size

Array-backed stack: push, pop, peek, overflow and underflow

Interactive · edit the input

Your input

Try

data[] · capacity 3 · size 0

0
1
2
Setup

An empty stack backed by an array of 3. The top is data[size - 1]; push and pop only touch the end, so both are O(1).

Step 1 / 11
Java
1class ArrayStack {
2    private int[] data; private int size;
3    ArrayStack(int capacity) { data = new int[capacity]; }
4    void push(int x) {
5        if (size == data.length) data = Arrays.copyOf(data, data.length * 2);   // resizable; a fixed stack rejects instead
6        data[size++] = x;
7    }
8    int pop() {
9        if (size == 0) throw new NoSuchElementException("stack underflow");
10        return data[--size];
11    }
12    int peek() {
13        if (size == 0) throw new NoSuchElementException("stack underflow");
14        return data[size - 1];                      // look without removing
15    }
16    boolean isEmpty() { return size == 0; }
17}

Live state

size

0

capacity

3

No condition evaluated on this step
Execution trace (dry run table)Show 11 steps
StepLineStateWhat happens
1L3size=0 capacity=3An empty stack backed by an array of 3. The top is data[size - 1]; push and pop only touch the end, so both are O(1).
2L6op=push(5) size=1 top=5data[size++] = 5: 5 is the new top.
3L6op=push(8) size=2 top=8data[size++] = 8: 8 is the new top.
4L6op=push(3) size=3 top=3data[size++] = 3: 3 is the new top.
5L14op=peek() top=3 size=3peek() returns 3 without removing it: size stays 3.
6L10op=pop() returned=3 size=2Return data[--size] = 3: the most recently pushed value leaves first (LIFO). The slot is simply ignored from now on.
7L10op=pop() returned=8 size=1Return data[--size] = 8: the most recently pushed value leaves first (LIFO). The slot is simply ignored from now on.
8L10op=pop() returned=5 size=0Return data[--size] = 5: the most recently pushed value leaves first (LIFO). The slot is simply ignored from now on.
9L9op=pop() size=0 errors=1pop() on an empty stack: underflow. Java's ArrayDeque.pop throws NoSuchElementException; poll() would return null.
10L6op=push(7) size=1 top=7data[size++] = 7: 7 is the new top.
11L16size=1 errors=1 return=[7]Final stack (bottom to top): [7]; 1 rejected operation.

Practice ladder

Now try it yourself

Easy

  • Show the stack after push 1, push 2, pop, push 3
  • What does ArrayDeque.pop() do on an empty deque?

Medium

  • Why does Deque.push add at the front?
  • Explain why a resizable stack still has O(1) amortised push

Advanced

  • Design a stack that supports a maximum size and returns false from push when full

Key takeaways

  • A stack is LIFO: push, pop, peek and isEmpty are all O(1).
  • Underflow (pop on empty) and overflow (push on full) must be handled.
  • Fixed stacks reject when full; resizable stacks double.