Golang学习-栈（Stack）-平芜编程栈

栈（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)

缺点：

每个节点额外存储指针，内存开销更大
指针跳转导致缓存不友好

三、基于切片的栈实现

packagemainimport"fmt"// ArrayStack 基于切片的栈typeArrayStackstruct{data[]int}funcNewArrayStack()*ArrayStack{return&ArrayStack{data:make([]int,0),}}// Push 入栈 O(1) 均摊func(s*ArrayStack)Push(valint){s.data=append(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.data=s.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("\"(a+b)*[c-d]\" 匹配?",isBracketMatch("(a+b)*[c-d]"))// truefmt.Println("\"(a+b]*[c-d)\" 匹配?",isBracketMatch("(a+b]*[c-d)"))// falsefmt.Println("\"((()))\" 匹配?",isBracketMatch("((()))"))// truefmt.Println("\"(()\" 匹配?",isBracketMatch("(()"))// false}funcmustPeek(s*ArrayStack)int{v,_:=s.Peek()returnv}

运行结果

栈大小: 3 栈顶元素: 3 出栈: 3 出栈: 2 栈大小: 1 --- 括号匹配检测 --- "(a+b)*[c-d]" 匹配? true "(a+b]*[c-d)" 匹配? false "((()))" 匹配? true "(()" 匹配? false

四、基于链表的栈实现

packagemainimport"fmt"// stackNode 链表栈节点typestackNodestruct{dataintnext*stackNode}// LinkedStack 基于链表的栈typeLinkedStackstruct{top*stackNode// 栈顶指针，指向链表头lenint}funcNewLinkedStack()*LinkedStack{return&LinkedStack{}}// Push 入栈 O(1) — 头插法func(s*LinkedStack)Push(valint){s.top=&stackNode{data:val,next:s.top}s.len++}// Pop 出栈 O(1) — 头删法func(s*LinkedStack)Pop()(int,bool){ifs.top==nil{return0,false}val:=s.top.data s.top=s.top.next s.len--returnval,true}// Peek 查看栈顶 O(1)func(s*LinkedStack)Peek()(int,bool){ifs.top==nil{return0,false}returns.top.data,true}func(s*LinkedStack)IsEmpty()bool{returns.top==nil}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{return&StackQueue{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)。

七、两种实现对比

维度	切片实现	链表实现
Push	O(1) 均摊	O(1) 严格
Pop	O(1) 均摊	O(1) 严格
内存连续性	好（缓存友好）	差（指针跳转）
扩容开销	有（拷贝）	无
额外内存	无	每节点一个指针
代码复杂度	低	中
适用场景	通用、数据量可控	数据量极大或不确定