栈Stack一、栈的核心概念栈是一种后进先出LIFO, Last In First Out的线性数据结构。可以把它想象成一摞盘子你只能在顶部放盘子和取盘子最先放进去的盘子最后才能取出来。栈只有一端开放称为栈顶 Top所有操作都发生在这一端Push入栈将元素放到栈顶Pop出栈移除并返回栈顶元素Peek查看栈顶返回栈顶元素但不移除栈的特性操作时间复杂度Push 入栈O(1)Pop 出栈O(1)Peek 查看栈顶O(1)查找O(n)空间复杂度O(n)栈的典型应用场景函数调用栈程序运行时的函数嵌套调用就是栈结构括号匹配编译器检查()[]{}是否配对表达式求值后缀表达式逆波兰表示法的计算浏览器后退将访问历史压栈后退时弹栈DFS 深度优先搜索用栈替代递归实现撤销操作Undo每次操作压栈撤销时弹栈二、两种实现方式栈可以用数组或 Go 切片或链表来实现两种方式各有优劣2.1 基于切片数组的实现利用 Go 切片的动态扩容特性栈顶就是切片末尾。优点实现简单代码量少内存连续CPU 缓存命中率高Go 切片自动管理扩容缺点扩容时需要拷贝数据均摊 O(1)大量 Push 可能触发多次扩容2.2 基于链表的实现栈顶是链表头节点Push 做头插Pop 做头删。优点不需要预分配内存按需分配没有扩容拷贝开销每个 Push/Pop 都是严格的 O(1)缺点每个节点额外存储指针内存开销更大指针跳转导致缓存不友好三、基于切片的栈实现packagemainimportfmt// ArrayStack 基于切片的栈typeArrayStackstruct{data[]int}funcNewArrayStack()*ArrayStack{returnArrayStack{data:make([]int,0),}}// Push 入栈 O(1) 均摊func(s*ArrayStack)Push(valint){s.dataappend(s.data,val)}// Pop 出栈 O(1) 均摊func(s*ArrayStack)Pop()(int,bool){iflen(s.data)0{return0,false}index:len(s.data)-1val:s.data[index]s.datas.data[:index]returnval,true}// Peek 查看栈顶 O(1)func(s*ArrayStack)Peek()(int,bool){iflen(s.data)0{return0,false}returns.data[len(s.data)-1],true}// IsEmpty 判空func(s*ArrayStack)IsEmpty()bool{returnlen(s.data)0}// Size 返回栈大小func(s*ArrayStack)Size()int{returnlen(s.data)}funcmain(){stack:NewArrayStack()// 入栈 1,2,3stack.Push(1)stack.Push(2)stack.Push(3)fmt.Println(栈大小:,stack.Size())// 3fmt.Println(栈顶元素:,mustPeek(stack))// 3// 出栈val,_:stack.Pop()fmt.Println(出栈:,val)// 3val,_stack.Pop()fmt.Println(出栈:,val)// 2fmt.Println(栈大小:,stack.Size())// 1// 括号匹配检测fmt.Println(\n--- 括号匹配检测 ---)fmt.Println(\(ab)*[c-d]\ 匹配?,isBracketMatch((ab)*[c-d]))// truefmt.Println(\(ab]*[c-d)\ 匹配?,isBracketMatch((ab]*[c-d)))// falsefmt.Println(\((()))\ 匹配?,isBracketMatch(((()))))// truefmt.Println(\(()\ 匹配?,isBracketMatch((()))// false}funcmustPeek(s*ArrayStack)int{v,_:s.Peek()returnv}运行结果栈大小: 3 栈顶元素: 3 出栈: 3 出栈: 2 栈大小: 1 --- 括号匹配检测 --- (ab)*[c-d] 匹配? true (ab]*[c-d) 匹配? false ((())) 匹配? true (() 匹配? false四、基于链表的栈实现packagemainimportfmt// stackNode 链表栈节点typestackNodestruct{dataintnext*stackNode}// LinkedStack 基于链表的栈typeLinkedStackstruct{top*stackNode// 栈顶指针指向链表头lenint}funcNewLinkedStack()*LinkedStack{returnLinkedStack{}}// Push 入栈 O(1) — 头插法func(s*LinkedStack)Push(valint){s.topstackNode{data:val,next:s.top}s.len}// Pop 出栈 O(1) — 头删法func(s*LinkedStack)Pop()(int,bool){ifs.topnil{return0,false}val:s.top.data s.tops.top.next s.len--returnval,true}// Peek 查看栈顶 O(1)func(s*LinkedStack)Peek()(int,bool){ifs.topnil{return0,false}returns.top.data,true}func(s*LinkedStack)IsEmpty()bool{returns.topnil}func(s*LinkedStack)Size()int{returns.len}funcmain(){stack:NewLinkedStack()stack.Push(100)stack.Push(200)stack.Push(300)fmt.Println(栈大小:,stack.Size())// 3fmt.Println(栈顶:,mustPeek2(stack))// 300for!stack.IsEmpty(){val,_:stack.Pop()fmt.Println(出栈:,val)// 300, 200, 100}}funcmustPeek2(s*LinkedStack)int{v,_:s.Peek()returnv}运行结果栈大小: 3 栈顶: 300 出栈: 300 出栈: 200 出栈: 100五、实战应用括号匹配检测括号匹配是栈最经典的应用。算法思路遍历字符串的每个字符遇到左括号([{→ 压入栈中遇到右括号)]}→ 弹出栈顶元素检查是否匹配遍历结束后栈应为空// isBracketMatch 检查字符串中的括号是否匹配funcisBracketMatch(sstring)bool{stack:NewArrayStack()pairs:map[rune]rune{):(,]:[,}:{,}for_,ch:ranges{switchch{case(,[,{:stack.Push(int(ch))case),],}:top,ok:stack.Pop()if!ok||top!int(pairs[ch]){returnfalse}}}returnstack.IsEmpty()}算法分析时间复杂度O(n)每个字符最多入栈出栈一次空间复杂度O(n)最坏情况全部是左括号六、实战应用用栈实现队列队列是 FIFO 结构而栈是 LIFO 结构。用两个栈可以模拟一个队列入队直接压入 input 栈出队如果 output 栈为空将 input 栈所有元素依次弹出并压入 output 栈此时顺序反转然后从 output 栈弹出// StackQueue 双栈实现队列typeStackQueuestruct{inStack*ArrayStack outStack*ArrayStack}funcNewStackQueue()*StackQueue{returnStackQueue{inStack:NewArrayStack(),outStack:NewArrayStack(),}}// Enqueue 入队 — 直接压入 inStackfunc(q*StackQueue)Enqueue(valint){q.inStack.Push(val)}// Dequeue 出队 — 从 outStack 弹出空则倒灌func(q*StackQueue)Dequeue()(int,bool){ifq.outStack.IsEmpty(){// 将 inStack 所有元素倒入 outStackfor!q.inStack.IsEmpty(){val,_:q.inStack.Pop()q.outStack.Push(val)}}returnq.outStack.Pop()}每个元素最多被 Push/Pop 两次一次进 inStack一次进 outStack均摊时间复杂度 O(1)。七、两种实现对比维度切片实现链表实现PushO(1) 均摊O(1) 严格PopO(1) 均摊O(1) 严格内存连续性好缓存友好差指针跳转扩容开销有拷贝无额外内存无每节点一个指针代码复杂度低中适用场景通用、数据量可控数据量极大或不确定实践建议日常开发中优先用切片实现简单高效。只有当数据量极大且 Push 频率非常高扩容拷贝成为瓶颈时才考虑链表实现。Go 标准库没有提供内置的 Stack 类型但切片本身就足够好用。八、总结栈是一种受限的线性结构——只允许在栈顶操作。正是这个限制赋予了它 LIFO 的特性和 O(1) 的 push/pop 效率。理解栈的关键在于LIFO 特性最后放入的最先取出两种实现切片简单高效和链表严格 O(1)核心应用括号匹配、表达式求值、DFS、函数调用、Undo/Redo双栈技巧两个栈可以模拟队列体现了用受限工具构建复杂结构的思维
栈Stack一、栈的核心概念栈是一种后进先出LIFO, Last In First Out的线性数据结构。可以把它想象成一摞盘子你只能在顶部放盘子和取盘子最先放进去的盘子最后才能取出来。栈只有一端开放称为栈顶 Top所有操作都发生在这一端Push入栈将元素放到栈顶Pop出栈移除并返回栈顶元素Peek查看栈顶返回栈顶元素但不移除栈的特性操作时间复杂度Push 入栈O(1)Pop 出栈O(1)Peek 查看栈顶O(1)查找O(n)空间复杂度O(n)栈的典型应用场景函数调用栈程序运行时的函数嵌套调用就是栈结构括号匹配编译器检查()[]{}是否配对表达式求值后缀表达式逆波兰表示法的计算浏览器后退将访问历史压栈后退时弹栈DFS 深度优先搜索用栈替代递归实现撤销操作Undo每次操作压栈撤销时弹栈二、两种实现方式栈可以用数组或 Go 切片或链表来实现两种方式各有优劣2.1 基于切片数组的实现利用 Go 切片的动态扩容特性栈顶就是切片末尾。优点实现简单代码量少内存连续CPU 缓存命中率高Go 切片自动管理扩容缺点扩容时需要拷贝数据均摊 O(1)大量 Push 可能触发多次扩容2.2 基于链表的实现栈顶是链表头节点Push 做头插Pop 做头删。优点不需要预分配内存按需分配没有扩容拷贝开销每个 Push/Pop 都是严格的 O(1)缺点每个节点额外存储指针内存开销更大指针跳转导致缓存不友好三、基于切片的栈实现packagemainimportfmt// ArrayStack 基于切片的栈typeArrayStackstruct{data[]int}funcNewArrayStack()*ArrayStack{returnArrayStack{data:make([]int,0),}}// Push 入栈 O(1) 均摊func(s*ArrayStack)Push(valint){s.dataappend(s.data,val)}// Pop 出栈 O(1) 均摊func(s*ArrayStack)Pop()(int,bool){iflen(s.data)0{return0,false}index:len(s.data)-1val:s.data[index]s.datas.data[:index]returnval,true}// Peek 查看栈顶 O(1)func(s*ArrayStack)Peek()(int,bool){iflen(s.data)0{return0,false}returns.data[len(s.data)-1],true}// IsEmpty 判空func(s*ArrayStack)IsEmpty()bool{returnlen(s.data)0}// Size 返回栈大小func(s*ArrayStack)Size()int{returnlen(s.data)}funcmain(){stack:NewArrayStack()// 入栈 1,2,3stack.Push(1)stack.Push(2)stack.Push(3)fmt.Println(栈大小:,stack.Size())// 3fmt.Println(栈顶元素:,mustPeek(stack))// 3// 出栈val,_:stack.Pop()fmt.Println(出栈:,val)// 3val,_stack.Pop()fmt.Println(出栈:,val)// 2fmt.Println(栈大小:,stack.Size())// 1// 括号匹配检测fmt.Println(\n--- 括号匹配检测 ---)fmt.Println(\(ab)*[c-d]\ 匹配?,isBracketMatch((ab)*[c-d]))// truefmt.Println(\(ab]*[c-d)\ 匹配?,isBracketMatch((ab]*[c-d)))// falsefmt.Println(\((()))\ 匹配?,isBracketMatch(((()))))// truefmt.Println(\(()\ 匹配?,isBracketMatch((()))// false}funcmustPeek(s*ArrayStack)int{v,_:s.Peek()returnv}运行结果栈大小: 3 栈顶元素: 3 出栈: 3 出栈: 2 栈大小: 1 --- 括号匹配检测 --- (ab)*[c-d] 匹配? true (ab]*[c-d) 匹配? false ((())) 匹配? true (() 匹配? false四、基于链表的栈实现packagemainimportfmt// stackNode 链表栈节点typestackNodestruct{dataintnext*stackNode}// LinkedStack 基于链表的栈typeLinkedStackstruct{top*stackNode// 栈顶指针指向链表头lenint}funcNewLinkedStack()*LinkedStack{returnLinkedStack{}}// Push 入栈 O(1) — 头插法func(s*LinkedStack)Push(valint){s.topstackNode{data:val,next:s.top}s.len}// Pop 出栈 O(1) — 头删法func(s*LinkedStack)Pop()(int,bool){ifs.topnil{return0,false}val:s.top.data s.tops.top.next s.len--returnval,true}// Peek 查看栈顶 O(1)func(s*LinkedStack)Peek()(int,bool){ifs.topnil{return0,false}returns.top.data,true}func(s*LinkedStack)IsEmpty()bool{returns.topnil}func(s*LinkedStack)Size()int{returns.len}funcmain(){stack:NewLinkedStack()stack.Push(100)stack.Push(200)stack.Push(300)fmt.Println(栈大小:,stack.Size())// 3fmt.Println(栈顶:,mustPeek2(stack))// 300for!stack.IsEmpty(){val,_:stack.Pop()fmt.Println(出栈:,val)// 300, 200, 100}}funcmustPeek2(s*LinkedStack)int{v,_:s.Peek()returnv}运行结果栈大小: 3 栈顶: 300 出栈: 300 出栈: 200 出栈: 100五、实战应用括号匹配检测括号匹配是栈最经典的应用。算法思路遍历字符串的每个字符遇到左括号([{→ 压入栈中遇到右括号)]}→ 弹出栈顶元素检查是否匹配遍历结束后栈应为空// isBracketMatch 检查字符串中的括号是否匹配funcisBracketMatch(sstring)bool{stack:NewArrayStack()pairs:map[rune]rune{):(,]:[,}:{,}for_,ch:ranges{switchch{case(,[,{:stack.Push(int(ch))case),],}:top,ok:stack.Pop()if!ok||top!int(pairs[ch]){returnfalse}}}returnstack.IsEmpty()}算法分析时间复杂度O(n)每个字符最多入栈出栈一次空间复杂度O(n)最坏情况全部是左括号六、实战应用用栈实现队列队列是 FIFO 结构而栈是 LIFO 结构。用两个栈可以模拟一个队列入队直接压入 input 栈出队如果 output 栈为空将 input 栈所有元素依次弹出并压入 output 栈此时顺序反转然后从 output 栈弹出// StackQueue 双栈实现队列typeStackQueuestruct{inStack*ArrayStack outStack*ArrayStack}funcNewStackQueue()*StackQueue{returnStackQueue{inStack:NewArrayStack(),outStack:NewArrayStack(),}}// Enqueue 入队 — 直接压入 inStackfunc(q*StackQueue)Enqueue(valint){q.inStack.Push(val)}// Dequeue 出队 — 从 outStack 弹出空则倒灌func(q*StackQueue)Dequeue()(int,bool){ifq.outStack.IsEmpty(){// 将 inStack 所有元素倒入 outStackfor!q.inStack.IsEmpty(){val,_:q.inStack.Pop()q.outStack.Push(val)}}returnq.outStack.Pop()}每个元素最多被 Push/Pop 两次一次进 inStack一次进 outStack均摊时间复杂度 O(1)。七、两种实现对比维度切片实现链表实现PushO(1) 均摊O(1) 严格PopO(1) 均摊O(1) 严格内存连续性好缓存友好差指针跳转扩容开销有拷贝无额外内存无每节点一个指针代码复杂度低中适用场景通用、数据量可控数据量极大或不确定实践建议日常开发中优先用切片实现简单高效。只有当数据量极大且 Push 频率非常高扩容拷贝成为瓶颈时才考虑链表实现。Go 标准库没有提供内置的 Stack 类型但切片本身就足够好用。八、总结栈是一种受限的线性结构——只允许在栈顶操作。正是这个限制赋予了它 LIFO 的特性和 O(1) 的 push/pop 效率。理解栈的关键在于LIFO 特性最后放入的最先取出两种实现切片简单高效和链表严格 O(1)核心应用括号匹配、表达式求值、DFS、函数调用、Undo/Redo双栈技巧两个栈可以模拟队列体现了用受限工具构建复杂结构的思维
