Stacks

Last In, First Out (LIFO)

CS205 Data Structures

Use arrow keys to navigate · Interactive slides ahead!

What is a Stack?

A stack is a collection with a LIFO access policy:

The last element inserted is the first one removed
Access is restricted to one end called the top
You can only add or remove from the top

Analogy: Stack of Plates

Think of a spring-loaded plate dispenser. You always take the top plate. Clean plates go on top. You never pull from the bottom.

Key Idea

LIFO = Last In, First Out. The most recently added element is always the next one to leave.

Interactive Stack

Push items onto the stack, then try pop and peek!

The Stack ADT (Abstract Data Type)

Core Operations

Method	Description	Time
`push(e)`	Add element e to top	O(1)
`pop()`	Remove & return top	O(1)
`top()` / `peek()`	Return top without removing	O(1)
`isEmpty()`	Is the stack empty?	O(1)
`size()`	Number of elements	O(1)

Key Idea

Every operation is O(1) — constant time. A stack does very little, but does it blazing fast.

Java Interface

public interface Stack<E> {

    // Add element to the top
    void push(E element);

    // Remove and return the top
    E pop();

    // Return top without removing
    E top();

    // Is the stack empty?
    boolean isEmpty();

    // Number of elements
    int size();
}
      

Warning

pop() and top() on an empty stack should throw an EmptyStackException (or return null).

Push & Pop Operations

Watch push and pop in action — synced with array-based code highlighting.

Array-Based Push

// t = index of top, starts at -1
public void push(E element) {
    if (size() == data.length)
        throw new FullStackException();
    t++;                // advance top
    data[t] = element;  // store
}
      

Array-Based Pop

public E pop() {
    if (isEmpty())
        throw new EmptyStackException();
    E ans = data[t]; // save top
    data[t] = null;  // GC help
    t--;             // shrink
    return ans;
}
      

Array Visualization

Array capacity: 8 | t = 2 | size = 3

Key Idea

Push is always O(1) — just increment t and store. Pop is O(1) — read, null out, decrement t.

Peek / Top

Look at the top element without removing it

Implementation

// Array-based
public E top() {
    if (isEmpty())
        throw new EmptyStackException();
    return data[t]; // no modification
}
      

Analogy

peek() = looking at the top plate without picking it up. pop() = actually taking it.

top() vs pop()

Aspect	`top()`	`pop()`
Returns top?	Yes	Yes
Removes top?	No	Yes
Changes size?	No	Yes (-1)
Destructive?	No	Yes

Visual Comparison

Array-Based Implementation

Store elements in an array, track the top index

Memory Layout

Key Idea

Stack "grows right" in the array. Index 0 is bottom, index t is top. Empty stack: t = -1.

Complete Java Class

public class ArrayStack<E> implements Stack<E> {
    private E[] data;
    private int t = -1; // top index

    public ArrayStack(int capacity) {
        data = (E[]) new Object[capacity];
    }
    public int size()      { return t + 1; }
    public boolean isEmpty() { return t == -1; }

    public void push(E e) {
        if (size() == data.length)
            throw new FullStackException();
        data[++t] = e;
    }
    public E pop() {
        if (isEmpty()) throw new EmptyStackException();
        E ans = data[t]; data[t] = null; t--;
        return ans;
    }
    public E top() {
        if (isEmpty()) throw new EmptyStackException();
        return data[t];
    }
}
      

Array-Based: When the Array is Full

Dynamic resizing with doubling strategy

Dynamic Resizing Demo

Capacity: 2 | Size: 0 | Push items to see doubling in action

Amortized Analysis

Doubling seems expensive (O(n) copy), but happens rarely.

Key Idea: Amortized O(1)

Total cost of n pushes is O(n), so each push is O(1) amortized. The occasional resize is "paid for" by cheap pushes.

Warning

Never grow by a constant (e.g. +10). That gives O(n) amortized per push. Always double.

Linked-List-Based Implementation

Push and pop at the head of a singly linked list

Push = Insert at Head

Pop = Remove Head

Key Idea

Push/pop at the head of a singly linked list is O(1). No resizing needed. No fixed limit.

Complete Java Class

public class LinkedStack<E>
    implements Stack<E> {

    private SinglyLinkedList<E> list
        = new SinglyLinkedList<>();

    public int size()      { return list.size(); }
    public boolean isEmpty() { return list.isEmpty(); }

    public void push(E e) {
        list.addFirst(e); // O(1)
    }
    public E pop() {
        return list.removeFirst(); // O(1)
    }
    public E top() {
        return list.first(); // O(1)
    }
}
      

Array vs Linked List Implementation

Tradeoffs between the two approaches

Criterion	Array-Based	Linked-List-Based
push / pop	O(1) amortized	O(1) worst-case
Memory/element	Low — just the element	Higher — element + pointer
Wasted space	Up to N unused slots	None
Resize cost	O(n) occasionally	Never needed
Max size	Fixed (unless dynamic)	Limited only by memory
Cache perf	Excellent — contiguous	Poor — scattered

When to Use Array

When you know the max size, or need best cache performance. Most practical implementations use arrays.

When to Use Linked List

When size is unpredictable, or you need guaranteed O(1) worst-case per operation.

Application: Parenthesis Matching

Check if brackets are balanced using a stack

Algorithm

Scan left to right
Opening ( [ { → push
Closing ) ] } → pop and check match
At end: stack must be empty

Stack Visualization

Application: Evaluating Postfix Expressions

Evaluate expressions like 3 4 + 2 * using a stack

What is Postfix (Reverse Polish)?

Infix	Postfix
`3 + 4`	`3 4 +`
`(3 + 4) * 2`	`3 4 + 2 *`
`3 + 4 * 2`	`3 4 2 * +`

Algorithm

Number: push it
Operator: pop two, compute, push result
Final value on stack = answer

Stack

Application: Infix to Postfix Conversion

Shunting-Yard Algorithm (Dijkstra)

Algorithm Rules

Number: output immediately
( : push onto operator stack
) : pop & output until (
Operator: while top has ≥ precedence, pop & output; then push

Precedence: * / → 2 (higher) + - → 1 (lower)

Application: Function Call Stack

How your computer manages function calls

How It Works

Every function call pushes a stack frame. Every return pops it.

int main() {
    int x = factorial(3);
}
int factorial(int n) {
    if (n == 0) return 1;
    return n * factorial(n - 1);
}

Key Idea

Recursion is the call stack in action. Deep recursion = tall stack → possible StackOverflowError.

Call Stack

Application: Undo / Redo

Two stacks power every editor's undo system

How It Works

Perform action: push onto Undo, clear Redo
Undo: pop from Undo → push onto Redo
Redo: pop from Redo → push onto Undo

Important

A new action clears the Redo stack. You lose forward history when you branch off.

Application: Browser Back / Forward

Navigation history uses two stacks — same pattern as Undo/Redo!

How It Works

Visit: push current onto Back, clear Forward
Back: push current onto Forward, pop Back
Forward: push current onto Back, pop Forward

Same Pattern!

Browser history = Undo/Redo with pages instead of actions. Back stack = Undo stack, Forward stack = Redo stack.

Common Pitfalls

Mistakes to avoid when working with stacks

1. Popping an Empty Stack

The #1 stack bug. Always check isEmpty() before pop() or top().

// BAD
E val = stack.pop();  // crash!
// GOOD
if (!stack.isEmpty()) {
    E val = stack.pop();
}

2. Stack Overflow

Deep recursion = deep call stack. Too deep → StackOverflowError.

// Infinite recursion!
int bad(int n) {
    return bad(n - 1);
    // no base case!
}

3. Wrong Pop Order

In postfix, operand order matters for - and /.

// For "5 3 -"
b = stack.pop(); // 3
a = stack.pop(); // 5
// Correct: a - b = 5-3 = 2
// Wrong:   b - a = 3-5 = -2

Remember

First popped = second operand.
Second popped = first operand.

Summary & Cheat Sheet

Stack at a Glance

Operations

Operation	Time	Notes
`push(e)`	O(1)*	Add to top
`pop()`	O(1)	Remove & return top
`top()`	O(1)	Return top (no remove)
`isEmpty()`	O(1)	Check if empty
`size()`	O(1)	Element count

* O(1) amortized for dynamic array

Implementations

Array-Based

Simple, fast, great cache performance. Amortized O(1) with doubling.

Linked-List-Based

No size limit, guaranteed O(1) worst-case. Extra memory for pointers.

Applications

Application	How Stacks Help
Parenthesis matching	Push open, pop on close
Postfix evaluation	Push nums, pop for ops
Infix → postfix	Operator stack (shunting-yard)
Function calls	Call stack / recursion
Undo / Redo	Two stacks
Browser history	Back & Forward stacks

One Sentence

A stack is a restricted list where you can only touch the top — and that restriction makes it powerful, fast, and useful everywhere.

Challenge A: Predict the Stack

What's left on the stack after processing [ ( { } ] )?

Input: `[ ( { } ] )`

Trace through the parenthesis matching algorithm mentally. What happens?

Trace It Out

Challenge B: Fix the Bug

This postfix evaluator has a bug. Find and fix it!

Buggy Code

for (String tok : tokens) {
    if (isNumber(tok)) {
        stack.push(Integer.parseInt(tok));
    } else {
        int a = stack.pop();
        int b = stack.pop();
        stack.push(compute(a, tok, b));
    }
}

Test: "8 3 -" should give 5, but this code gives -5.

Which line has the bug?

Think About It

Stack State for "8 3 -"

After pushing 8 then 3:

top → 3
8

First pop gets 3 (stored in a).
Second pop gets 8 (stored in b).
Then we compute a op b = 3 - 8 = -5

Challenge C: How Many Resizes?

Array-based stack starts with capacity 2, doubles when full. How many resizes after 17 pushes?

Setup

Initial capacity: 2
Resize strategy: double when full
Total pushes: 17

Quiz: Stack Fundamentals

3 quick questions to test your understanding

Q1: What does LIFO stand for?

Q2: You push A, B, C, D in that order. What does pop() return?

Q3: What is the worst-case time for push() in an array-based stack?

Challenge: Evaluate This Postfix Expression

Manually evaluate 5 1 2 + 4 * + 3 - — what's the result?

Expression: `5 1 2 + 4 * + 3 -`

Work through it token by token using the postfix algorithm.

Tips

Numbers → push
Operators → pop two, compute, push result
Watch the operand order for -!

Challenge: What Gets Printed?

Trace through this code and predict the output

Code

Stack<Integer> s = new Stack<>();
s.push(10);
s.push(20);
s.push(30);
System.out.print(s.pop() + " ");
s.push(40);
s.push(50);
System.out.print(s.pop() + " ");
System.out.print(s.pop() + " ");
System.out.print(s.pop() + " ");

Stacks

What is a Stack?

Analogy: Stack of Plates

Key Idea

Interactive Stack

The Stack ADT (Abstract Data Type)

Core Operations

Key Idea

Java Interface

Warning

Push & Pop Operations

Array-Based Push

Array-Based Pop

Array Visualization

Key Idea

Peek / Top

Implementation

Analogy

top() vs pop()

Visual Comparison

Array-Based Implementation

Memory Layout

Key Idea

Complete Java Class

Array-Based: When the Array is Full

Dynamic Resizing Demo

Amortized Analysis

Key Idea: Amortized O(1)

Warning

Linked-List-Based Implementation

Push = Insert at Head

Pop = Remove Head

Key Idea

Complete Java Class

Array vs Linked List Implementation

When to Use Array

When to Use Linked List

Application: Parenthesis Matching

Algorithm

Stack Visualization

Application: Evaluating Postfix Expressions

What is Postfix (Reverse Polish)?

Algorithm

Stack

Application: Infix to Postfix Conversion

Algorithm Rules

Application: Function Call Stack

How It Works

Key Idea

Call Stack

Application: Undo / Redo

How It Works

Important

Application: Browser Back / Forward

How It Works

Same Pattern!

Common Pitfalls

1. Popping an Empty Stack

2. Stack Overflow

3. Wrong Pop Order

Remember

Summary & Cheat Sheet

Stack at a Glance

Operations

Implementations

Array-Based

Linked-List-Based

Applications

One Sentence

Challenge A: Predict the Stack

Input: [ ( { } ] )

Trace It Out

Challenge B: Fix the Bug

Buggy Code

Which line has the bug?

Think About It

Stack State for "8 3 -"

The Fix

Challenge C: How Many Resizes?

Setup

Input: `[ ( { } ] )`

Expression: `5 1 2 + 4 * + 3 -`