Go Guide

Core patterns · Lesson 20 of 62 · about 50 min

Stacks, queues & monotonic stacks

Last-in-first-out and first-in-first-out in Go slices, matching problems, expression evaluation, and the monotonic stack for 'next greater' questions.

pkg.go.dev: container/list ↗go-zero-to-hero ↗
On this page · 12 sections
  1. 01A stack is just a slice
  2. 02Matching: Valid Parentheses
  3. 03Evaluation: Reverse Polish Notation
  4. 04Monotonic stack: next greater element
  5. 05Queues
  6. 06A reusable generic stack
  7. 07The full program
  8. 08Complexity
  9. 09Recognizing the pattern
  10. 10Summary
  11. 11Check your understanding
  12. 12Practice in Go

A stack is just a slice#

OperationGoCost
pushs = append(s, v)O(1) amortized
peek tops[len(s)-1]O(1)
popv := s[len(s)-1]; s = s[:len(s)-1]O(1)
empty?len(s) == 0O(1)

Always check len(s) > 0 before peeking or popping, or you will panic with "index out of range".

Try it

stack_basics.go
Go
package main
 
import "fmt"
 
func main() {
	var s []string
	s = append(s, "a") // push
	s = append(s, "b")
	s = append(s, "c")
	fmt.Println("stack:", s, "top:", s[len(s)-1])
 
	for len(s) > 0 { // pop until empty: last in, first out
		top := s[len(s)-1]
		s = s[:len(s)-1]
		fmt.Println("pop", top, "->", s)
	}
}
Output
stack: [a b c] top: c
pop c -> [a b]
pop b -> [a]
pop a -> []

Matching: Valid Parentheses#

A closing bracket must match the most recent unmatched opener, which is exactly the top of a stack. Trace "{[()]}":

charactionstack after
{push{
[push{ [
(push{ [ (
)top is (: pop{ [
]top is [: pop{
}top is {: popempty

Valid, because the stack ends empty. For "(]", the ] finds ( on top and fails immediately.

Run the trace

parens_trace.go
Go
package main
 
import "fmt"
 
func isValid(s string) bool {
	pair := map[byte]byte{')': '(', ']': '[', '}': '{'}
	var stack []byte
	for i := 0; i < len(s); i++ {
		c := s[i]
		open, isCloser := pair[c]
		if !isCloser {
			stack = append(stack, c)
			fmt.Printf("  %c push          stack=%s\n", c, stack)
			continue
		}
		if len(stack) == 0 || stack[len(stack)-1] != open {
			fmt.Printf("  %c no matching %c on top: invalid\n", c, open)
			return false
		}
		stack = stack[:len(stack)-1]
		fmt.Printf("  %c pop %c         stack=%s\n", c, open, stack)
	}
	return len(stack) == 0
}
 
func main() {
	for _, s := range []string{"{[()]}", "(]", "(("} {
		fmt.Println(s)
		fmt.Println("  valid:", isValid(s))
	}
}
Output
{[()]}
  { push          stack={
  [ push          stack={[
  ( push          stack={[(
  ) pop (         stack={[
  ] pop [         stack={
  } pop {         stack=
  valid: true
(]
  ( push          stack=(
  ] no matching [ on top: invalid
  valid: false
((
  ( push          stack=(
  ( push          stack=((
  valid: false

"((" never fails during the loop. It is only caught at the end, because the stack is not empty.

Evaluation: Reverse Polish Notation#

In RPN, operators come after their operands: 2 1 + 3 * means (2 + 1) * 3. Numbers are pushed; an operator pops two numbers, applies itself, and pushes the result.

tokenstack after
22
12 1
+3
33 3
*9

The first value popped is the right operand, which matters for - and /.

Run the trace

rpn_trace.go
Go
package main
 
import (
	"fmt"
	"strconv"
)
 
func main() {
	tokens := []string{"5", "1", "2", "+", "4", "*", "+", "3", "-"} // 5 + (1+2)*4 - 3
	var st []int
	for _, t := range tokens {
		switch t {
		case "+", "-", "*", "/":
			b, a := st[len(st)-1], st[len(st)-2] // first pop is the RIGHT operand
			st = st[:len(st)-2]
			var r int
			switch t {
			case "+":
				r = a + b
			case "-":
				r = a - b
			case "*":
				r = a * b
			case "/":
				r = a / b
			}
			st = append(st, r)
			fmt.Printf("%-2s %d %s %d = %-3d stack=%v\n", t, a, t, b, r, st)
		default:
			n, _ := strconv.Atoi(t)
			st = append(st, n)
			fmt.Printf("%-2s push           stack=%v\n", t, st)
		}
	}
	fmt.Println("result:", st[0])
}
Output
5  push           stack=[5]
1  push           stack=[5 1]
2  push           stack=[5 1 2]
+  1 + 2 = 3   stack=[5 3]
4  push           stack=[5 3 4]
*  3 * 4 = 12  stack=[5 12]
+  5 + 12 = 17  stack=[17]
3  push           stack=[17 3]
-  17 - 3 = 14  stack=[14]
result: 14

Monotonic stack: next greater element#

"For each day, how many days until a warmer temperature?" Brute force looks ahead from each day: O(n²). A monotonic stack keeps indexes of days still waiting, with temperatures decreasing from bottom to top. When a warmer day arrives, it is the answer for every waiting day that is colder, so pop them all.

Trace t = [73, 74, 75, 71, 69, 72, 76]:

it[i]pops (index: answer)stack of indexes after (temps)
0730 (73)
1740: 1-0 = 11 (74)
2751: 12 (75)
3712 3 (75 71)
4692 3 4 (75 71 69)
5724: 1, 3: 22 5 (75 72)
6765: 1, 2: 46 (76)

Day 6 never finds a warmer day, so its answer stays 0. Every index is pushed once and popped at most once: O(n).

Run the trace

temps_trace.go
Go
package main
 
import "fmt"
 
func main() {
	t := []int{73, 74, 75, 71, 69, 72, 76}
	ans := make([]int, len(t))
	var stack []int // indexes; their temperatures decrease bottom to top
	for i, temp := range t {
		pops := ""
		for len(stack) > 0 && t[stack[len(stack)-1]] < temp {
			j := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			ans[j] = i - j
			pops += fmt.Sprintf(" %d:%d", j, ans[j])
		}
		stack = append(stack, i)
		fmt.Printf("i=%d t=%d pops=[%-9s] stack=%v\n", i, temp, pops, stack)
	}
	fmt.Println("answer:", ans)
}
Output
i=0 t=73 pops=[         ] stack=[0]
i=1 t=74 pops=[ 0:1     ] stack=[1]
i=2 t=75 pops=[ 1:1     ] stack=[2]
i=3 t=71 pops=[         ] stack=[2 3]
i=4 t=69 pops=[         ] stack=[2 3 4]
i=5 t=72 pops=[ 4:1 3:2 ] stack=[2 5]
i=6 t=76 pops=[ 5:1 2:4 ] stack=[6]
answer: [1 1 4 2 1 1 0]

Flip the comparison for "next smaller", and run right to left for "previous greater". Histogram and stock-span problems are this same pattern.

Step through it

Trapping rain water with a stack

The two pointers lesson computes trapped water column by column. A decreasing stack of bar indexes computes it layer by layer instead. When a bar taller than the top of the stack arrives, the top is the floor of a basin: its left wall is the next index down the stack and its right wall is the new bar. The water layer above that floor is (min(left, right) - floor) × width.

rainstack.go
Go
package main
 
import "fmt"
 
func trap(h []int) int {
	var stack []int // indexes; heights decrease from bottom to top
	water := 0
	for i, height := range h {
		for len(stack) > 0 && h[stack[len(stack)-1]] < height {
			floor := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			if len(stack) == 0 {
				break // no left wall: water would spill out
			}
			left := stack[len(stack)-1]
			depth := min(h[left], height) - h[floor]
			width := i - left - 1
			water += depth * width
			fmt.Printf("  basin between %d and %d over floor %d: %d x %d = %d\n", left, i, floor, depth, width, depth*width)
		}
		stack = append(stack, i)
	}
	return water
}
 
func main() {
	fmt.Println("total:", trap([]int{4, 2, 0, 3, 2, 5}))
}
Output
  basin between 1 and 3 over floor 2: 2 x 1 = 2
  basin between 0 and 3 over floor 1: 1 x 2 = 2
  basin between 3 and 5 over floor 4: 1 x 1 = 1
  basin between 0 and 5 over floor 3: 1 x 4 = 4
total: 9

Both methods are O(n). The stack version is the one that generalizes to "largest rectangle in a histogram", where the same pop-and-measure loop computes rectangle areas instead of water.

Queues#

For a simple queue, a slice works: q = append(q, v) to enqueue and v := q[0]; q = q[1:] to dequeue. Reslicing from the front does not free memory until the whole slice is dropped, which is fine for BFS. For a long-running queue, use a ring buffer, two stacks, or container/list. A buffered channel is a queue shared between goroutines.

Try it

The same three tasks with a slice queue and with container/list, which can also add and remove at both ends:

queues.go
Go
package main
 
import (
	"container/list"
	"fmt"
)
 
func main() {
	q := []string{}
	q = append(q, "job1", "job2", "job3") // enqueue at the back
	for len(q) > 0 {
		job := q[0] // dequeue from the front: first in, first out
		q = q[1:]
		fmt.Println("process", job, "remaining", q)
	}
 
	d := list.New() // a doubly linked list works as a deque
	d.PushBack(2)
	d.PushBack(3)
	d.PushFront(1)
	fmt.Print("deque:")
	for e := d.Front(); e != nil; e = e.Next() {
		fmt.Print(" ", e.Value)
	}
	fmt.Println()
	d.Remove(d.Back())
	fmt.Println("after removing back, len =", d.Len(), "front =", d.Front().Value)
}
Output
process job1 remaining [job2 job3]
process job2 remaining [job3]
process job3 remaining []
deque: 1 2 3
after removing back, len = 2 front = 1

A reusable generic stack#

Go
type Stack[T any] struct{ items []T }
 
func (s *Stack[T]) Push(v T)   { s.items = append(s.items, v) }
func (s *Stack[T]) Len() int   { return len(s.items) }
func (s *Stack[T]) Peek() T    { return s.items[len(s.items)-1] }
func (s *Stack[T]) Pop() T {
	v := s.items[len(s.items)-1]
	s.items = s.items[:len(s.items)-1]
	return v
}

In contest-style solutions, a bare slice is shorter. In your godsa library, the type documents intent.

The full program#

stacks.go
Go
package main
 
import (
	"fmt"
	"strconv"
)
 
func isValid(s string) bool {
	pairs := map[rune]rune{')': '(', ']': '[', '}': '{'}
	var stack []rune
	for _, c := range s {
		if open, isCloser := pairs[c]; isCloser {
			if len(stack) == 0 || stack[len(stack)-1] != open {
				return false
			}
			stack = stack[:len(stack)-1]
		} else {
			stack = append(stack, c)
		}
	}
	return len(stack) == 0
}
 
func evalRPN(tokens []string) int {
	var st []int
	for _, tok := range tokens {
		switch tok {
		case "+", "-", "*", "/":
			b, a := st[len(st)-1], st[len(st)-2] // b popped first: right operand
			st = st[:len(st)-2]
			switch tok {
			case "+":
				st = append(st, a+b)
			case "-":
				st = append(st, a-b)
			case "*":
				st = append(st, a*b)
			case "/":
				st = append(st, a/b)
			}
		default:
			n, _ := strconv.Atoi(tok)
			st = append(st, n)
		}
	}
	return st[0]
}
 
func dailyTemperatures(t []int) []int {
	ans := make([]int, len(t))
	var stack []int // indexes; temperatures decreasing
	for i, temp := range t {
		for len(stack) > 0 && t[stack[len(stack)-1]] < temp {
			j := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			ans[j] = i - j
		}
		stack = append(stack, i)
	}
	return ans
}
 
type MinStack struct{ items [][2]int } // {value, min so far}
 
func (s *MinStack) Push(v int) {
	m := v
	if len(s.items) > 0 {
		m = min(m, s.items[len(s.items)-1][1])
	}
	s.items = append(s.items, [2]int{v, m})
}
func (s *MinStack) Pop()        { s.items = s.items[:len(s.items)-1] }
func (s *MinStack) Top() int    { return s.items[len(s.items)-1][0] }
func (s *MinStack) GetMin() int { return s.items[len(s.items)-1][1] }
 
func main() {
	fmt.Println(isValid("{[()]}"), isValid("(]"), isValid("(("))
	fmt.Println(evalRPN([]string{"2", "1", "+", "3", "*"}), evalRPN([]string{"4", "13", "5", "/", "+"}))
	fmt.Println(dailyTemperatures([]int{73, 74, 75, 71, 69, 72, 76}))
 
	var ms MinStack
	for _, v := range []int{5, 3, 7, 2} {
		ms.Push(v)
	}
	fmt.Print(ms.GetMin(), " ")
	ms.Pop()
	fmt.Print(ms.GetMin(), " ", ms.Top(), "\n")
 
	queue := []string{"a", "b"}
	queue = append(queue, "c")
	front := queue[0]
	queue = queue[1:]
	fmt.Println(front, queue)
}
Output
true false false
9 6
[1 1 4 2 1 1 0]
2 3 7
a [b c]

Complexity#

ProblemTimeSpace
valid parenthesesO(n)O(n)
evaluate RPNO(n)O(n)
daily temperatures (monotonic stack)O(n)O(n)
min stack, every operationO(1)O(n)

Recognizing the pattern#

  • Nesting or matching: brackets, tags, undo, "the most recent unmatched thing".
  • Next greater / smaller element, span, or "how far until": monotonic stack.
  • Expression evaluation or parsing.
  • Processing in arrival order, level by level: queue (you will use it for BFS).

Summary#

  • A slice is a stack: append to push, reslice to pop; check emptiness first.
  • Stacks solve matching and evaluation problems.
  • A monotonic stack answers next-greater questions in O(n) by popping everything the new element resolves.
  • Queues serve in arrival order; a slice works for BFS, a ring buffer or list for long-lived queues.

Check your understanding

Answer before scrolling back up. If you miss one, reread the matching section, then try again.

  1. Q1.How do you pop from a slice-based stack s?

  2. Q2.In Daily Temperatures, what does the stack hold?

  3. Q3.Why is a monotonic stack O(n) even with a loop inside the loop?

  4. Q4.Which structure gives first-in, first-out order?

Practice in Go

Write a table test first, then the solution. On LeetCode, choose Go as the language. Open a hint only after 15 minutes stuck.

Finished this lesson?

Mark it done to track your progress. It is saved in this browser only.