Data Structures & Algorithms · Module 04 of 10

Stacks

Last in, first out. Matching, parsing, undo, and the monotonic-stack trick.

Build: Generic stack, min-stack
Solve: Brackets, RPN, monotonic stack

The finish line — what go test shows once every exercise in this module passes

$ go test -v ./04-stacks/ | grep '^--- ' --- PASS: TestStack (0.00s) --- PASS: TestValidParentheses (0.00s) --- PASS: TestEvalRPN (0.00s) --- PASS: TestNextGreater (0.00s) --- PASS: TestDailyTemperatures (0.00s) --- PASS: TestMinStack (0.00s)

Module 4 · tests 6

WHY

Why it matters.

A stack only lets you touch the top: push onto it, pop off it, peek at it. That restriction is exactly what you want whenever the most recent thing is the one that matters next — the innermost open bracket, the last edit to undo, the function to return to. Your program's call stack is one; so is the browser's back button.

IDEAS

The core ideas.

LIFO. Push 1, 2, 3 and you pop 3, 2, 1.

Matching and nesting. When you see an opener, push it. When you see a closer, the top of the stack must be its partner. Anything nested — brackets, HTML tags, function calls — works this way.

Expression evaluation. In Reverse Polish Notation (2 1 + 3 *), operands go on the stack and each operator pops two, computes, and pushes the result. Compilers and calculators use the same idea after converting from normal infix order.

Recursion is a stack. Any recursive algorithm can be rewritten with an explicit stack, and vice versa. Doing it explicitly avoids deep call stacks and gives you control over the order.

The monotonic stack. Keep the stack sorted (say, decreasing). When a new value arrives, pop everything it beats — for each popped item, the new value is its answer ("next greater element"). It looks like a nested loop, but each index is pushed once and popped at most once, so the whole pass is O(n).

COST

Cost of operations.

Operation	Cost
Push	O(1) amortized
Pop / Peek	O(1)
Search	O(n) — not what stacks are for

IN GO

Go specifics.

A slice is a stack. Push is s = append(s, v); pop is v := s[len(s)-1]; s = s[:len(s)-1]. No library type needed.
Clear what you pop. Reslicing doesn't erase the old element, so a popped pointer can't be garbage collected until that slot is overwritten. Set s[len(s)-1] = zero before shrinking when T holds pointers.
Return (T, bool) for Pop and Peek rather than panicking on empty — it's the comma-ok idiom you know from maps.
Goroutine stacks grow on demand, so deep recursion rarely overflows in Go the way it does in C. It still costs memory, and a million-deep DFS is better done iteratively.

EXAMPLE

Worked example: previous smaller element.

For each element, find the nearest value to its left that's smaller (or -1). It's the mirror image of your NextGreater exercise:

func prevSmaller(nums []int) []int {
	out := make([]int, len(nums))
	var stack []int // values, increasing from bottom to top
	for i, v := range nums {
		for len(stack) > 0 && stack[len(stack)-1] >= v {
			stack = stack[:len(stack)-1] // can never be anyone's answer again
		}
		if len(stack) == 0 {
			out[i] = -1
		} else {
			out[i] = stack[len(stack)-1]
		}
		stack = append(stack, v)
	}
	return out
}

The question to ask in every monotonic-stack problem: once something is popped, can it ever matter again? If not, popping it is safe, and you get O(n).

PATTERNS

Patterns to recognize.

Matching pairs — brackets, tags, "remove adjacent duplicates".
Monotonic stack — next/previous greater or smaller, "days until warmer", largest rectangle in a histogram.
Auxiliary stack — min-stack, max-stack: track a summary alongside each element.
Explicit DFS — tree and graph traversal without recursion.

EXERCISES

Your exercises.

Part A wraps a slice in a generic Stack[T]. Part B uses it: brackets, RPN evaluation (including the error cases), two monotonic-stack problems, and MinStack.

go test ./04-stacks/

For EvalRPN, watch operand order: the first value you pop is the right operand.

The files for this module

Everything below is also in the course download, in 04-stacks/. Work in exercises.go; the tests decide when you’re done.

▶ types.go the structs and helpers you’re given · 23 lines›

// Package stack is Module 4: stacks (LIFO).
//
// In Go a stack is just a slice: push is append, pop is reslicing off the
// end. The exercises have you wrap that in a type, then use stacks for
// matching, expression evaluation, and the monotonic-stack pattern.
package stack

import "errors"

// ErrBadExpression is returned by EvalRPN for malformed input.
var ErrBadExpression = errors.New("bad RPN expression")

// Stack is a generic LIFO stack backed by a slice. The top is the last element.
type Stack[T any] struct {
	items []T
}

// MinStack is an int stack that can also report its minimum in O(1).
// Hint: keep a second slice where mins[i] is the minimum of vals[:i+1].
type MinStack struct {
	vals []int
	mins []int
}

exercises.go — your work: every function is a stub marked TODO96 lines

//go:build !solutions

package stack

// ============================================================
// Part A — the stack itself
// ============================================================

// Push adds v to the top. Target: amortized O(1).
func (s *Stack[T]) Push(v T) {
	// TODO
}

// Pop removes and returns the top, or (zero, false) if empty.
// Tip: zero out the vacated slot so pointer values can be garbage collected.
// Target: O(1).
func (s *Stack[T]) Pop() (T, bool) {
	// TODO
	var zero T
	return zero, false
}

// Peek returns the top without removing it, or (zero, false) if empty.
func (s *Stack[T]) Peek() (T, bool) {
	// TODO
	var zero T
	return zero, false
}

// Len returns the number of items.
func (s *Stack[T]) Len() int {
	// TODO
	return 0
}

// IsEmpty reports whether the stack has no items.
func (s *Stack[T]) IsEmpty() bool {
	// TODO
	return true
}

// ============================================================
// Part B — stack problems (use your Stack type)
// ============================================================

// ValidParentheses reports whether every (, [ and { is closed by the right
// bracket in the right order. Other characters are ignored.
// "([]{})" -> true, "(]" -> false, "((" -> false. Target: O(n).
func ValidParentheses(str string) bool {
	// TODO
	return false
}

// EvalRPN evaluates an expression in Reverse Polish Notation with integer
// + - * / (division truncates toward zero, as Go's / does).
// ["2" "1" "+" "3" "*"] -> 9. Return ErrBadExpression for an unknown token,
// too few operands, leftover operands, or division by zero. Target: O(n).
func EvalRPN(tokens []string) (int, error) {
	// TODO
	return 0, nil
}

// NextGreater returns, for each element, the first larger element to its
// right, or -1 if none. [2 1 2 4 3] -> [4 2 4 -1 -1].
// Pattern: monotonic stack of indices still waiting for an answer.
// Target: O(n) — each index is pushed and popped at most once.
func NextGreater(nums []int) []int {
	// TODO
	return nil
}

// DailyTemperatures returns, for each day, how many days until a warmer
// temperature, or 0 if none. [73 74 75 71 69 72 76 73] -> [1 1 4 2 1 1 0 0].
// Same pattern as NextGreater. Target: O(n).
func DailyTemperatures(temps []int) []int {
	// TODO
	return nil
}

// Push adds v to the MinStack. Target: O(1).
func (m *MinStack) Push(v int) {
	// TODO
}

// Pop removes and returns the top, or (0, false) if empty. Target: O(1).
func (m *MinStack) Pop() (int, bool) {
	// TODO
	return 0, false
}

// Min returns the smallest value currently on the stack, or (0, false) if
// empty. Target: O(1) — no scanning.
func (m *MinStack) Min() (int, bool) {
	// TODO
	return 0, false
}

▶ stack_test.go the tests — the same file checks yours or the reference · 135 lines›

package stack

import (
	"errors"
	"slices"
	"testing"
)

func TestStack(t *testing.T) {
	var s Stack[string]
	if !s.IsEmpty() || s.Len() != 0 {
		t.Fatal("new stack should be empty")
	}
	for _, v := range []string{"a", "b", "c"} {
		s.Push(v)
	}
	if s.Len() != 3 || s.IsEmpty() {
		t.Fatalf("Len() = %d, IsEmpty() = %v after 3 pushes", s.Len(), s.IsEmpty())
	}
	if v, ok := s.Peek(); !ok || v != "c" {
		t.Fatalf("Peek() = (%q, %v), want (\"c\", true)", v, ok)
	}
	for _, want := range []string{"c", "b", "a"} {
		if v, ok := s.Pop(); !ok || v != want {
			t.Fatalf("Pop() = (%q, %v), want (%q, true)", v, ok, want)
		}
	}
	if _, ok := s.Pop(); ok {
		t.Error("Pop() on empty stack should return ok=false")
	}
	if _, ok := s.Peek(); ok {
		t.Error("Peek() on empty stack should return ok=false")
	}
}

func TestValidParentheses(t *testing.T) {
	for _, tc := range []struct {
		in   string
		want bool
	}{
		{"()", true},
		{"([]{})", true},
		{"{[()()]}", true},
		{"f(x[0]) { return }", true},
		{"(]", false},
		{"([)]", false},
		{"((", false},
		{")", false},
		{"", true},
	} {
		if got := ValidParentheses(tc.in); got != tc.want {
			t.Errorf("ValidParentheses(%q) = %v, want %v", tc.in, got, tc.want)
		}
	}
}

func TestEvalRPN(t *testing.T) {
	for _, tc := range []struct {
		in   []string
		want int
	}{
		{[]string{"2", "1", "+", "3", "*"}, 9},
		{[]string{"4", "13", "5", "/", "+"}, 6},
		{[]string{"10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"}, 22},
		{[]string{"7", "-2", "/"}, -3},
		{[]string{"42"}, 42},
	} {
		got, err := EvalRPN(tc.in)
		if err != nil || got != tc.want {
			t.Errorf("EvalRPN(%v) = (%d, %v), want (%d, nil)", tc.in, got, err, tc.want)
		}
	}
	for _, bad := range [][]string{
		{"1", "+"},
		{"1", "2"},
		{"1", "x", "+"},
		{"1", "0", "/"},
		{},
	} {
		if _, err := EvalRPN(bad); !errors.Is(err, ErrBadExpression) {
			t.Errorf("EvalRPN(%v) error = %v, want ErrBadExpression", bad, err)
		}
	}
}

func TestNextGreater(t *testing.T) {
	for _, tc := range []struct{ in, want []int }{
		{[]int{2, 1, 2, 4, 3}, []int{4, 2, 4, -1, -1}},
		{[]int{1, 2, 3}, []int{2, 3, -1}},
		{[]int{3, 2, 1}, []int{-1, -1, -1}},
		{[]int{5, 5}, []int{-1, -1}},
	} {
		if got := NextGreater(tc.in); !slices.Equal(got, tc.want) {
			t.Errorf("NextGreater(%v) = %v, want %v", tc.in, got, tc.want)
		}
	}
}

func TestDailyTemperatures(t *testing.T) {
	for _, tc := range []struct{ in, want []int }{
		{[]int{73, 74, 75, 71, 69, 72, 76, 73}, []int{1, 1, 4, 2, 1, 1, 0, 0}},
		{[]int{30, 40, 50, 60}, []int{1, 1, 1, 0}},
		{[]int{60, 50, 40}, []int{0, 0, 0}},
	} {
		if got := DailyTemperatures(tc.in); !slices.Equal(got, tc.want) {
			t.Errorf("DailyTemperatures(%v) = %v, want %v", tc.in, got, tc.want)
		}
	}
}

func TestMinStack(t *testing.T) {
	var m MinStack
	if _, ok := m.Min(); ok {
		t.Fatal("Min() on empty stack should return ok=false")
	}
	steps := []struct {
		push    int
		wantMin int
	}{{5, 5}, {3, 3}, {7, 3}, {3, 3}, {1, 1}}
	for _, s := range steps {
		m.Push(s.push)
		if got, ok := m.Min(); !ok || got != s.wantMin {
			t.Fatalf("after Push(%d), Min() = (%d, %v), want (%d, true)", s.push, got, ok, s.wantMin)
		}
	}
	for _, wantMinAfterPop := range []int{3, 3, 3, 5} {
		m.Pop()
		if got, _ := m.Min(); got != wantMinAfterPop {
			t.Fatalf("after Pop, Min() = %d, want %d", got, wantMinAfterPop)
		}
	}
	if v, ok := m.Pop(); !ok || v != 5 {
		t.Errorf("last Pop() = (%d, %v), want (5, true)", v, ok)
	}
}

Before you open the solution

Try not to open solution.go until your tests pass, or until you’ve been stuck for a solid half hour. Then compare: different-but-correct is fine; notice where the reference is simpler. go test -tags solutions ./04-stacks/ runs the same tests against it.

▶ solution.go reference solutions — build tag solutions · 150 lines›

//go:build solutions

package stack

import "strconv"

func (s *Stack[T]) Push(v T) { s.items = append(s.items, v) }

func (s *Stack[T]) Pop() (T, bool) {
	var zero T
	if len(s.items) == 0 {
		return zero, false
	}
	last := len(s.items) - 1
	v := s.items[last]
	s.items[last] = zero // let the GC reclaim pointer values
	s.items = s.items[:last]
	return v, true
}

func (s *Stack[T]) Peek() (T, bool) {
	var zero T
	if len(s.items) == 0 {
		return zero, false
	}
	return s.items[len(s.items)-1], true
}

func (s *Stack[T]) Len() int { return len(s.items) }

func (s *Stack[T]) IsEmpty() bool { return len(s.items) == 0 }

func ValidParentheses(str string) bool {
	pairs := map[rune]rune{')': '(', ']': '[', '}': '{'}
	var st Stack[rune]
	for _, r := range str {
		switch r {
		case '(', '[', '{':
			st.Push(r)
		case ')', ']', '}':
			top, ok := st.Pop()
			if !ok || top != pairs[r] {
				return false
			}
		}
	}
	return st.IsEmpty()
}

func EvalRPN(tokens []string) (int, error) {
	var st Stack[int]
	for _, tok := range tokens {
		switch tok {
		case "+", "-", "*", "/":
			b, ok1 := st.Pop()
			a, ok2 := st.Pop()
			if !ok1 || !ok2 {
				return 0, ErrBadExpression
			}
			switch tok {
			case "+":
				st.Push(a + b)
			case "-":
				st.Push(a - b)
			case "*":
				st.Push(a * b)
			case "/":
				if b == 0 {
					return 0, ErrBadExpression
				}
				st.Push(a / b)
			}
		default:
			n, err := strconv.Atoi(tok)
			if err != nil {
				return 0, ErrBadExpression
			}
			st.Push(n)
		}
	}
	if st.Len() != 1 {
		return 0, ErrBadExpression
	}
	v, _ := st.Pop()
	return v, nil
}

func NextGreater(nums []int) []int {
	out := make([]int, len(nums))
	var st Stack[int] // indices whose answer isn't known yet; values decreasing
	for i, v := range nums {
		for {
			top, ok := st.Peek()
			if !ok || nums[top] >= v {
				break
			}
			st.Pop()
			out[top] = v
		}
		st.Push(i)
	}
	for !st.IsEmpty() {
		i, _ := st.Pop()
		out[i] = -1
	}
	return out
}

func DailyTemperatures(temps []int) []int {
	out := make([]int, len(temps))
	var st Stack[int]
	for i, t := range temps {
		for {
			top, ok := st.Peek()
			if !ok || temps[top] >= t {
				break
			}
			st.Pop()
			out[top] = i - top
		}
		st.Push(i)
	}
	return out
}

func (m *MinStack) Push(v int) {
	m.vals = append(m.vals, v)
	if len(m.mins) == 0 {
		m.mins = append(m.mins, v)
	} else {
		m.mins = append(m.mins, min(v, m.mins[len(m.mins)-1]))
	}
}

func (m *MinStack) Pop() (int, bool) {
	if len(m.vals) == 0 {
		return 0, false
	}
	last := len(m.vals) - 1
	v := m.vals[last]
	m.vals, m.mins = m.vals[:last], m.mins[:last]
	return v, true
}

func (m *MinStack) Min() (int, bool) {
	if len(m.mins) == 0 {
		return 0, false
	}
	return m.mins[len(m.mins)-1], true
}

FURTHER

Going further.

Extend EvalRPN into a calculator that takes normal infix input (3 + 4 * 2) using the shunting-yard algorithm — two stacks, one for operators.
LeetCode practice: Largest Rectangle in Histogram, Decode String, Asteroid Collision.

QUIZ

Check yourself.

Three questions. Answer each one in your head — or out loud — before you open the answer.

Question 1

EvalRPN(["3", "4", "-"]) should return…

A1
B-1
C7
Dan error

Show the answer

B — The first pop is the right operand (4), the second is the left (3): 3 - 4 = -1. Swapping them is the classic bug.

Question 2

NextGreater has a while loop inside a for loop. Why is it still O(n)?

AThe inner loop runs at most once per iteration
BEach index is pushed once and popped at most once, so total inner work is O(n)
CGo optimizes nested loops
DIt's actually O(n²) in the worst case

Show the answer

B — Amortized analysis: count total pushes and pops over the whole run, not per iteration.

Question 3

Your generic Stack[T] holds pointers. Why set the vacated slot to the zero value in Pop?

AGo requires it
BSo the popped object can be garbage collected — the old slot would otherwise keep it reachable
CTo make Pop O(1)
DTo keep len and cap equal

Show the answer

B — Reslicing s[:n-1] leaves the old element in the backing array, still referenced, until that slot is reused.

Where to next.

Commit your work before you move on to module 5, so git log shows your own progress through the course.

Stacks

Why it matters.

The core ideas.

Cost of operations.

Go specifics.

Worked example: previous smaller element.

Patterns to recognize.

Your exercises.

The files for this module

Going further.

Check yourself.

Where to next.

← Previous: Module 3 — Linked Lists

Next →: Module 5 — Queues

Course home