栈与队列

栈和队列是两种操作受限的线性数据结构：栈是「后进先出（LIFO）」，队列是「先进先出（FIFO）」。虽然简单，但它们是许多高级算法的基石——DFS 本质上用栈，BFS 本质上用队列，括号匹配、表达式求值、单调栈、滑动窗口最大值等经典问题都离不开它们。Go 标准库没有内置 Stack 和 Queue 类型，这反而给了我们理解其底层实现的机会。本篇将从手写实现出发，覆盖栈队列的经典应用，最后用 LeetCode 真题收尾。

一、栈的实现

1. 数组栈（切片实现）

用切片实现栈是最自然的方式，append 对应 push，切片尾部对应栈顶。

package main

import "fmt"

type Stack struct {
	data []int
}

func NewStack() *Stack {
	return &Stack{data: make([]int, 0)}
}

func (s *Stack) Push(val int) {
	s.data = append(s.data, val)
}

func (s *Stack) Pop() (int, bool) {
	if len(s.data) == 0 {
		return 0, false
	}
	val := s.data[len(s.data)-1]
	s.data = s.data[:len(s.data)-1]
	return val, true
}

func (s *Stack) Peek() (int, bool) {
	if len(s.data) == 0 {
		return 0, false
	}
	return s.data[len(s.data)-1], true
}

func (s *Stack) Size() int {
	return len(s.data)
}

func (s *Stack) IsEmpty() bool {
	return len(s.data) == 0
}

func main() {
	s := NewStack()
	s.Push(1)
	s.Push(2)
	s.Push(3)
	fmt.Println("大小:", s.Size())
	if v, ok := s.Peek(); ok {
		fmt.Println("栈顶:", v)
	}
	for !s.IsEmpty() {
		v, _ := s.Pop()
		fmt.Println("弹出:", v)
	}
}

2. 链表栈

用链表头作为栈顶，push/pop 都是 O(1)，且无需扩容。

package main

import "fmt"

type node struct {
	val  int
	next *node
}

type LinkedStack struct {
	top *node
	size int
}

func (s *LinkedStack) Push(val int) {
	s.top = &node{val: val, next: s.top}
	s.size++
}

func (s *LinkedStack) Pop() (int, bool) {
	if s.top == nil {
		return 0, false
	}
	val := s.top.val
	s.top = s.top.next
	s.size--
	return val, true
}

func (s *LinkedStack) Peek() (int, bool) {
	if s.top == nil {
		return 0, false
	}
	return s.top.val, true
}

func (s *LinkedStack) Size() int { return s.size }

func main() {
	s := &LinkedStack{}
	s.Push(10)
	s.Push(20)
	s.Push(30)
	fmt.Println("大小:", s.Size())
	for v, ok := s.Pop(); ok; v, ok = s.Pop() {
		fmt.Println("弹出:", v)
	}
}

3. Go 标准库中没有内置 Stack

Go 没有提供专门的 Stack 类型，社区通常用切片或 container/list 模拟。切片方案最常用、最快。

二、队列的实现

1. 数组队列（环形缓冲区）

朴素数组队列在频繁出队后会导致头部空间浪费，环形缓冲区（ring buffer）能复用空间。Go 标准库没有暴露通用 ring buffer，这里手写一个固定容量的实现：

package main

import "fmt"

type ArrayQueue struct {
	data   []int
	head   int // 队首下标
	tail   int // 下一个入队位置
	size   int
	cap    int
}

func NewArrayQueue(capacity int) *ArrayQueue {
	return &ArrayQueue{
		data: make([]int, capacity),
		cap:  capacity,
	}
}

func (q *ArrayQueue) Enqueue(val int) bool {
	if q.size == q.cap {
		return false // 队满
	}
	q.data[q.tail] = val
	q.tail = (q.tail + 1) % q.cap
	q.size++
	return true
}

func (q *ArrayQueue) Dequeue() (int, bool) {
	if q.size == 0 {
		return 0, false
	}
	val := q.data[q.head]
	q.head = (q.head + 1) % q.cap
	q.size--
	return val, true
}

func (q *ArrayQueue) Size() int    { return q.size }
func (q *ArrayQueue) IsEmpty() bool { return q.size == 0 }

func main() {
	q := NewArrayQueue(3)
	q.Enqueue(1)
	q.Enqueue(2)
	q.Enqueue(3)
	fmt.Println("入队第4个:", q.Enqueue(4)) // false，满
	for !q.IsEmpty() {
		v, _ := q.Dequeue()
		fmt.Println("出队:", v)
	}
}

2. 链表队列

链表队列维护 head 和 tail 指针，入队 O(1)、出队 O(1)，且无容量限制。

package main

import "fmt"

type qnode struct {
	val  int
	next *qnode
}

type LinkedQueue struct {
	head *qnode
	tail *qnode
	size int
}

func (q *LinkedQueue) Enqueue(val int) {
	n := &qnode{val: val}
	if q.tail == nil {
		q.head = n
		q.tail = n
	} else {
		q.tail.next = n
		q.tail = n
	}
	q.size++
}

func (q *LinkedQueue) Dequeue() (int, bool) {
	if q.head == nil {
		return 0, false
	}
	val := q.head.val
	q.head = q.head.next
	if q.head == nil {
		q.tail = nil
	}
	q.size--
	return val, true
}

func (q *LinkedQueue) Size() int { return q.size }

func main() {
	q := &LinkedQueue{}
	q.Enqueue(1)
	q.Enqueue(2)
	q.Enqueue(3)
	for v, ok := q.Dequeue(); ok; v, ok = q.Dequeue() {
		fmt.Println("出队:", v)
	}
}

3. 双端队列（Deque）

双端队列两端都能进出，是滑动窗口算法的基础。用切片实现时头部操作是 O(n)，若要 O(1) 需用环形缓冲区或链表。Go 标准库 container/list 可直接当 Deque 用。

package main

import "fmt"

// 用切片实现的简化 Deque，头部操作 O(n)，演示用
type Deque struct {
	data []int
}

func (d *Deque) PushBack(v int)  { d.data = append(d.data, v) }
func (d *Deque) PushFront(v int) { d.data = append([]int{v}, d.data...) }
func (d *Deque) PopBack() (int, bool) {
	if len(d.data) == 0 {
		return 0, false
	}
	v := d.data[len(d.data)-1]
	d.data = d.data[:len(d.data)-1]
	return v, true
}
func (d *Deque) PopFront() (int, bool) {
	if len(d.data) == 0 {
		return 0, false
	}
	v := d.data[0]
	d.data = d.data[1:]
	return v, true
}
func (d *Deque) Len() int { return len(d.data) }

func main() {
	d := &Deque{}
	d.PushBack(2)
	d.PushBack(3)
	d.PushFront(1)
	fmt.Println("队列:", d.data)
	d.PopBack()
	d.PopFront()
	fmt.Println("操作后:", d.data)
}

三、栈的应用

1. 括号匹配

经典栈应用：遇到左括号入栈，遇到右括号检查栈顶是否匹配。

package main

import "fmt"

func isValid(s string) bool {
	pairs := map[byte]byte{')': '(', ']': '[', '}': '{'}
	stack := make([]byte, 0)
	for i := 0; i < len(s); i++ {
		c := s[i]
		if c == '(' || c == '[' || c == '{' {
			stack = append(stack, c)
		} else {
			if len(stack) == 0 || stack[len(stack)-1] != pairs[c] {
				return false
			}
			stack = stack[:len(stack)-1]
		}
	}
	return len(stack) == 0
}

func main() {
	fmt.Println("()[]{}:", isValid("()[]{}")) // true
	fmt.Println("([)]:", isValid("([)]"))     // false
	fmt.Println("{[]}:", isValid("{[]}"))     // true
}

2. 表达式求值（中缀转后缀 + 求值）

package main

import (
	"fmt"
	"strconv"
)

// 中缀转后缀
func infixToPostfix(expr string) []string {
	var output []string
	var ops []byte
	prec := map[byte]int{'+': 1, '-': 1, '*': 2, '/': 2}

	for i := 0; i < len(expr); i++ {
		c := expr[i]
		if c == ' ' {
			continue
		}
		if c >= '0' && c <= '9' {
			j := i
			for j < len(expr) && expr[j] >= '0' && expr[j] <= '9' {
				j++
			}
			output = append(output, expr[i:j])
			i = j - 1
		} else if c == '(' {
			ops = append(ops, c)
		} else if c == ')' {
			for len(ops) > 0 && ops[len(ops)-1] != '(' {
				output = append(output, string(ops[len(ops)-1]))
				ops = ops[:len(ops)-1]
			}
			ops = ops[:len(ops)-1] // 弹出 (
		} else {
			for len(ops) > 0 && ops[len(ops)-1] != '(' && prec[ops[len(ops)-1]] >= prec[c] {
				output = append(output, string(ops[len(ops)-1]))
				ops = ops[:len(ops)-1]
			}
			ops = append(ops, c)
		}
	}
	for len(ops) > 0 {
		output = append(output, string(ops[len(ops)-1]))
		ops = ops[:len(ops)-1]
	}
	return output
}

// 后缀表达式求值
func evalPostfix(tokens []string) int {
	var stack []int
	for _, t := range tokens {
		if n, err := strconv.Atoi(t); err == nil {
			stack = append(stack, n)
		} else {
			b := stack[len(stack)-1]
			a := stack[len(stack)-2]
			stack = stack[:len(stack)-2]
			switch t {
			case "+":
				stack = append(stack, a+b)
			case "-":
				stack = append(stack, a-b)
			case "*":
				stack = append(stack, a*b)
			case "/":
				stack = append(stack, a/b)
			}
		}
	}
	return stack[0]
}

func main() {
	expr := "3 + 4 * 2 / ( 1 - 5 )"
	postfix := infixToPostfix(expr)
	fmt.Println("后缀:", postfix)
	fmt.Println("结果:", evalPostfix(postfix)) // 3 + 8/-4 = 3 - 2 = 1
}

3. 单调栈：下一个更大元素

单调栈维护一个单调递减（或递增）的栈，用于解决「下一个更大/更小元素」类问题。

package main

import "fmt"

// 返回每个元素右侧第一个比它大的元素下标，没有则 -1
func nextGreaterElement(nums []int) []int {
	n := len(nums)
	ans := make([]int, n)
	for i := range ans {
		ans[i] = -1
	}
	stack := []int{} // 存下标，对应值单调递减
	for i := 0; i < n; i++ {
		for len(stack) > 0 && nums[stack[len(stack)-1]] < nums[i] {
			top := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			ans[top] = nums[i]
		}
		stack = append(stack, i)
	}
	return ans
}

func main() {
	nums := []int{2, 1, 2, 4, 3}
	fmt.Println("下一个更大:", nextGreaterElement(nums)) // [4 2 4 -1 -1]
}

四、队列的应用

1. BFS 层序遍历

队列是 BFS 的标准工具。下面以二叉树层序遍历为例：

package main

import "fmt"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func levelOrder(root *TreeNode) [][]int {
	var result [][]int
	if root == nil {
		return result
	}
	queue := []*TreeNode{root}
	for len(queue) > 0 {
		size := len(queue)
		level := make([]int, 0, size)
		for i := 0; i < size; i++ {
			node := queue[0]
			queue = queue[1:]
			level = append(level, node.Val)
			if node.Left != nil {
				queue = append(queue, node.Left)
			}
			if node.Right != nil {
				queue = append(queue, node.Right)
			}
		}
		result = append(result, level)
	}
	return result
}

func main() {
	root := &TreeNode{Val: 1,
		Left:  &TreeNode{Val: 2, Left: &TreeNode{Val: 4}},
		Right: &TreeNode{Val: 3, Right: &TreeNode{Val: 5}}}
	fmt.Println("层序遍历:", levelOrder(root)) // [[1] [2 3] [4 5]]
}

2. 滑动窗口最大值（单调队列）

单调队列维护一个双端队列，队首始终是当前窗口最大值的下标。

package main

import "fmt"

// 返回每个大小为 k 的滑动窗口的最大值
func maxSlidingWindow(nums []int, k int) []int {
	n := len(nums)
	if n == 0 || k == 0 {
		return nil
	}
	var result []int
	deque := []int{} // 存下标，对应值单调递减
	for i := 0; i < n; i++ {
		// 移除超出窗口的下标
		for len(deque) > 0 && deque[0] <= i-k {
			deque = deque[1:]
		}
		// 维护单调递减：移除比当前小的
		for len(deque) > 0 && nums[deque[len(deque)-1]] <= nums[i] {
			deque = deque[:len(deque)-1]
		}
		deque = append(deque, i)
		if i >= k-1 {
			result = append(result, nums[deque[0]])
		}
	}
	return result
}

func main() {
	nums := []int{1, 3, -1, -3, 5, 3, 6, 7}
	fmt.Println("滑动窗口最大值 k=3:", maxSlidingWindow(nums, 3)) // [3 3 5 5 6 7]
}

五、Go 标准库：container/list 实现栈和队列

container/list 是双向链表，可同时充当栈和队列：

package main

import (
	"container/list"
	"fmt"
)

func main() {
	// 当栈用
	stack := list.New()
	stack.PushBack(1)
	stack.PushBack(2)
	stack.PushBack(3)
	fmt.Println("栈顶:", stack.Back().Value)
	for stack.Len() > 0 {
		e := stack.Back()
		fmt.Println("出栈:", e.Value)
		stack.Remove(e)
	}

	// 当队列用
	queue := list.New()
	queue.PushBack(1)
	queue.PushBack(2)
	queue.PushBack(3)
	for queue.Len() > 0 {
		e := queue.Front()
		fmt.Println("出队:", e.Value)
		queue.Remove(e)
	}
}

六、LeetCode 经典题解析

1. 有效括号（LC 20）

前面已实现 isValid，回顾思路：左括号入栈，右括号匹配栈顶，最后栈空即有效。

2. 每日温度（LC 739）

题目：对每天的温度，求下一个更高温度出现在几天后。

思路：单调递减栈存下标，遇到更高温度时弹出栈顶并计算差值。

package main

import "fmt"

func dailyTemperatures(temps []int) []int {
	n := len(temps)
	ans := make([]int, n)
	stack := []int{}
	for i := 0; i < n; i++ {
		for len(stack) > 0 && temps[stack[len(stack)-1]] < temps[i] {
			top := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			ans[top] = i - top
		}
		stack = append(stack, i)
	}
	return ans
}

func main() {
	temps := []int{73, 74, 75, 71, 69, 72, 76, 73}
	fmt.Println("每日温度:", dailyTemperatures(temps)) // [1 1 4 2 1 1 0 0]
}

3. 柱状图中最大矩形（LC 84）

题目：给定柱状图各柱高度，求最大矩形面积。

思路：单调递增栈，对每个柱子找左右两侧第一个比它矮的位置，宽度即矩形底。

package main

import "fmt"

func largestRectangleArea(heights []int) int {
	heights = append(heights, 0) // 哨兵，确保最后清空栈
	stack := []int{}
	maxArea := 0
	for i := 0; i < len(heights); i++ {
		for len(stack) > 0 && heights[stack[len(stack)-1]] > heights[i] {
			h := heights[stack[len(stack)-1]]
			stack = stack[:len(stack)-1]
			width := i
			if len(stack) > 0 {
				width = i - stack[len(stack)-1] - 1
			}
			if h*width > maxArea {
				maxArea = h * width
			}
		}
		stack = append(stack, i)
	}
	return maxArea
}

func main() {
	heights := []int{2, 1, 5, 6, 2, 3}
	fmt.Println("最大矩形面积:", largestRectangleArea(heights)) // 10
}

七、复杂度分析汇总

操作	切片栈/队列	链表栈/队列	环形缓冲区队列
入栈/队	O(1) 均摊	O(1)	O(1)
出栈/队（栈/队尾）	O(1)	O(1)	O(1)
出队（队头，切片）	O(n)	O(1)	O(1)
访问栈顶	O(1)	O(1)	-
空间	连续	分散	连续

八、小结

栈与队列是「受限的线性表」，本篇要点：

栈 LIFO：切片实现最简单，append 入栈、切片尾部出栈。链表实现头插头删也 O(1)。
队列 FIFO：朴素切片队列出队 O(n)，环形缓冲区和链表队列能实现 O(1) 入队出队。
双端队列两端都能进出，是滑动窗口算法的基础；Go 中常用 container/list 模拟。
栈的应用：括号匹配、表达式求值（中缀转后缀）、DFS、单调栈（下一个更大元素）。
队列的应用：BFS 层序遍历、单调队列（滑动窗口最大值）。
单调栈维护单调性，解决「下一个更大/更小」类问题；单调队列解决「滑动窗口最值」问题，都是 O(n) 的利器。
Go 没有内置 Stack/Queue，工程中按需选择切片或 container/list，注意 container/list 存 any 有装箱开销。

栈和队列虽然简单，但单调栈、单调队列是面试中区分度很高的考点，建议结合每日温度、柱状图最大矩形、滑动窗口最大值三题反复练习。下一篇我们进入哈希表与 Go map 的世界，理解 O(1) 查找的奥秘。

入门篇

进阶篇

资深篇

栈与队列

一、栈的实现

1. 数组栈（切片实现）

2. 链表栈

3. Go 标准库中没有内置 Stack

二、队列的实现

1. 数组队列（环形缓冲区）

2. 链表队列

3. 双端队列（Deque）

三、栈的应用

1. 括号匹配

2. 表达式求值（中缀转后缀 + 求值）

3. 单调栈：下一个更大元素

四、队列的应用

1. BFS 层序遍历

2. 滑动窗口最大值（单调队列）

五、Go 标准库：container/list 实现栈和队列

六、LeetCode 经典题解析

1. 有效括号（LC 20）

2. 每日温度（LC 739）

3. 柱状图中最大矩形（LC 84）

七、复杂度分析汇总

八、小结

栈与队列 ​

一、栈的实现 ​

1. 数组栈（切片实现） ​

2. 链表栈 ​

3. Go 标准库中没有内置 Stack ​

二、队列的实现 ​

1. 数组队列（环形缓冲区） ​

2. 链表队列 ​

3. 双端队列（Deque） ​

三、栈的应用 ​

1. 括号匹配 ​

2. 表达式求值（中缀转后缀 + 求值） ​

3. 单调栈：下一个更大元素 ​

四、队列的应用 ​

1. BFS 层序遍历 ​

2. 滑动窗口最大值（单调队列） ​

五、Go 标准库：container/list 实现栈和队列 ​

六、LeetCode 经典题解析 ​

1. 有效括号（LC 20） ​

2. 每日温度（LC 739） ​

3. 柱状图中最大矩形（LC 84） ​

七、复杂度分析汇总 ​

八、小结 ​

栈与队列

一、栈的实现

1. 数组栈（切片实现）

2. 链表栈

3. Go 标准库中没有内置 Stack

二、队列的实现

1. 数组队列（环形缓冲区）

2. 链表队列

3. 双端队列（Deque）

三、栈的应用

1. 括号匹配

2. 表达式求值（中缀转后缀 + 求值）

3. 单调栈：下一个更大元素

四、队列的应用

1. BFS 层序遍历

2. 滑动窗口最大值（单调队列）

五、Go 标准库：container/list 实现栈和队列

六、LeetCode 经典题解析

1. 有效括号（LC 20）

2. 每日温度（LC 739）

3. 柱状图中最大矩形（LC 84）

七、复杂度分析汇总

八、小结