文章目录0基础入门Go线性结构栈和队列一、栈Stack像叠衣服一样“后进先出”1\. 栈的核心操作0基础也能懂2\. Go实现极简栈无复杂语法复制就能跑3\. 栈的实际用途知道用在哪才好理解二、队列Queue像排队买奶茶一样“先进先出”1\. 队列的核心操作和栈对比着记更简单2\. Go实现极简线性队列同样无复杂语法3\. 队列的实际用途贴近生活好记三、栈和队列的核心区别一张表看懂0基础不混淆四、0基础总结重点记这3点不迷路0基础入门Go线性结构栈和队列【引言】在上一篇博客中我们详细讲解了Go中切片的核心操作——copy方法了解了切片作为顺序表的基础特性而今天我们要在此基础上延伸学习线性结构中最常用的两个“工具”——栈和队列。它们既是切片应用的重要场景也是后续我们学习哈希表下一篇内容的基础相当于“承上启下”的关键知识点切片的特性决定了栈和队列的常见实现方式而栈和队列的线性逻辑又能帮助我们更好地理解后续哈希表的非线性存储逻辑跟着节奏一步步来0基础也能轻松吃透。大家好我是刚入门Go的编程小白今天想和大家分享两个最基础、最常用的线性结构——栈和队列。很多0基础的朋友一听到“数据结构”就头大觉得是高深莫测的东西但其实它们就藏在我们的日常生活里用类比的方式一讲就懂。先跟大家说个小前提什么是「线性结构」简单说就是“数据像排队一样排成一条直线每个数据只有一个前一个和一个后一个除了开头和结尾”就像我们排队买奶茶、叠衣服都是线性的没有分支。栈和队列就是线性结构里最典型的两个“小伙伴”只是它们的“使用规则”不一样。一、栈Stack像叠衣服一样“后进先出”先想一个生活场景我们叠衣服的时候总是把先洗好的衣服放在最下面后洗好的衣服叠在上面。等要穿的时候只能从最上面开始拿先拿最后叠的那件才能拿到下面的。这就是栈的核心逻辑——后进先出LIFO也可以叫“先进后出”。用更直白的话讲栈就像一个“密封的圆筒”只有一个开口数据只能从这个开口“放进去”入栈也只能从这个开口“拿出来”出栈不能从中间插着放、也不能从中间抽出来。为了更直观理解我们用一个简单的示意图展示栈的结构和核心操作类比叠衣服示意图放在代码块里清晰醒目【栈的文字示意图类比叠衣服】 ┌─────────┐ │ 3 │ ← 栈顶最后入栈最先出栈类比最上面的衣服 │ 2 │ ← 中间元素 │ 1 │ ← 栈底最先入栈最后出栈类比最下面的衣服 └─────────┘ 操作流程说明 1. 入栈1 → 2 → 3依次叠在上面和叠衣服一致先叠1再叠2最后叠3 2. 出栈3 → 2 → 1先拿最上面的3再拿2最后拿最下面的1 3. 全程只有栈顶一个操作口符合“后进先出”逻辑。1. 栈的核心操作0基础也能懂入栈Push把数据“叠”到栈的最上面就像叠衣服时新衣服放在最顶层出栈Pop把栈最上面的数据“拿”走就像拿衣服时先拿最顶层的查看栈顶Peek看看最上面是什么数据但不拿走就像看看叠在最上面的是哪件衣服判断空栈IsEmpty看看栈里有没有数据就像看看衣服叠完了没或者拿完了没。2. Go实现极简栈无复杂语法复制就能跑Go里没有自带的栈结构但我们用「切片」就能轻松实现一个切片的append添加和len长度方法刚好对应栈的入栈和判断空栈非常简单。补充栈的实现有两种常见方式——顺序表如切片、数组和链表两者各有优劣并非顺序表绝对最优需结合数据量和场景选择1. 顺序表切片/数组日常开发中小数据量场景最常见。栈的核心操作是“末尾入栈、末尾出栈”顺序表的末尾操作append、删除末尾元素时间复杂度是O(1)效率极高且代码简单但需注意扩容和内存浪费问题切片扩容时会申请更大的内存空间通常是原容量的2倍若数据量极大后又大幅减少扩容后的空闲内存无法释放会造成内存浪费且大数据量下频繁扩容也会有性能损耗。2. 链表大数据量、需频繁增减数据的场景更优。链表实现栈无需担心扩容问题增减元素时只需修改指针无需移动大量数据也不会造成内存浪费且链表的内存是按需分配数据减少时内存可及时释放适合大数据处理场景。但链表需要额外维护指针代码比顺序表复杂日常小数据量场景下几乎不用。栈的两种实现方式对比示意图放在代码块里直观区分【栈的两种实现方式对比】 ┌─────────────────────────────────────────────────┐ │ 顺序表切片实现栈 │ ├─────────────────────────────────────────────────┤ │ 初始化空切片var stack []int │ │ 入栈append(stack, num) 末尾添加O(1) │ │ 出栈stack stack[:len(stack)-1]O(1) │ │ 优点代码简单、操作高效 │ │ 缺点大数据量扩容后易造成内存浪费 │ └─────────────────────────────────────────────────┘ ┌─────────────────────────────────────────────────┐ │ 链表实现栈 │ ├─────────────────────────────────────────────────┤ │ 初始化定义链表节点维护头指针栈顶 │ │ 入栈修改头指针添加新节点O(1) │ │ 出栈修改头指针删除栈顶节点O(1) │ │ 优点无扩容问题、不浪费内存 │ │ 缺点代码复杂、需维护指针 │ └─────────────────────────────────────────────────┘packagemainimportfmt// 定义栈结构用切片存储数据切片本身就是线性的完美适配typeStackstruct{data[]int// 存储栈里的数据这里用int举例其他类型也可以}// 入栈往栈顶添加数据类比叠衣服func(s*Stack)Push(numint){s.dataappend(s.data,num)// 切片末尾添加就是栈顶}// 出栈从栈顶删除并返回数据类比拿衣服func(s*Stack)Pop()(int,error){// 先判断栈是否为空空栈不能出栈ifs.IsEmpty(){return0,fmt.Errorf(栈为空无法出栈)}// 切片最后一个元素就是栈顶先取出再删除top:s.data[len(s.data)-1]s.datas.data[:len(s.data)-1]returntop,nil}// 查看栈顶只看不删func(s*Stack)Peek()(int,error){ifs.IsEmpty(){return0,fmt.Errorf(栈为空无栈顶元素)}returns.data[len(s.data)-1],nil}// 判断栈是否为空func(s*Stack)IsEmpty()bool{returnlen(s.data)0}// 测试一下看看效果funcmain(){// 初始化一个空栈stack:Stack{}// 入栈1-2-3类比叠衣服1在最下3在最上stack.Push(1)stack.Push(2)stack.Push(3)fmt.Println(入栈后栈顶元素,stack.Peek())// 输出3// 出栈先出3再出2类比拿衣服先拿最上面的3pop1,_:stack.Pop()fmt.Println(第一次出栈,pop1)// 输出3pop2,_:stack.Pop()fmt.Println(第二次出栈,pop2)// 输出2fmt.Println(出栈两次后栈是否为空,stack.IsEmpty())// 输出false还有1}3. 栈的实际用途知道用在哪才好理解不用记复杂的场景记住两个最常见的浏览器的“后退”功能你浏览页面1→页面2→页面3后退时先退页面3再退页面2就是栈的逻辑括号匹配比如判断 (())、()() 是否合法就是用栈来存储左括号遇到右括号就出栈匹配0基础暂时不用深究知道就行。二、队列Queue像排队买奶茶一样“先进先出”讲完栈再看队列它的主流逻辑和栈刚好相反但要注意队列并非只有一种逻辑也存在先进后出的特殊队列如双端队列的特殊使用场景不过我们今天重点讲「线性结构的常规队列」。还是用生活场景类比常规队列排队买奶茶先到的人排在前面先拿到奶茶后到的人排在后面只能等前面的人都拿到了才能轮到自己。这就是线性结构常规队列的核心逻辑——先进先出FIFO。队列就像一个“两头开口的管道”数据只能从“一端进”队尾从“另一端出”队头不能插队、也不能从中间进出完美贴合线性结构的特点。用生活场景类比文字示意图放在代码块里理解队列的核心操作【队列的文字示意图类比排队买奶茶】 ┌─────────┬─────────┬─────────┐ │ 1队头 │ 2中间 │ 3队尾 │ ← 排队的顾客数据 └─────────┴─────────┴─────────┘ ↓ ↓ ↓ 出队口 中间位置 入队口 操作流程说明 1. 入队4 → 排在3后面队尾队列变成 [1,2,3,4] 2. 出队1先离开队头队列变成 [2,3,4] 3. 全程只能从队尾入、队头出符合“先进先出”逻辑。示意图说明排队买奶茶时顾客依次排到队尾入队先到的顾客先买完离开出队和队列“先进先出”的逻辑完全一致。补充说明队列有很多类型比如循环队列、链式队列、双端队列等其中双端队列可实现先进后出的效果类似栈但我们今天只聚焦「线性结构的常规队列」也就是顺序队列其核心逻辑是先进先出不用管其他复杂类型和特殊场景0基础先掌握这个核心就够了。1. 队列的核心操作和栈对比着记更简单入队Enqueue把数据放到队列的末尾就像排队时站到队尾出队Dequeue把队列最前面的数据拿走就像排队时最前面的人买完奶茶离开查看队头Front看看最前面是什么数据但不拿走就像看看队伍最前面的人是谁判断空队列IsEmpty看看队列里有没有数据就像看看队伍有没有人。2. Go实现极简线性队列同样无复杂语法和栈一样Go也没有自带的队列我们还是用切片实现重点区分“队头”和“队尾”——切片的开头是队头切片的末尾是队尾入队就是append出队就是删除切片的第一个元素。补充线性队列的实现同样有顺序表切片、数组和链表两种方式两者各有适用场景日常开发中顺序表切片更常见但需注意其局限性顺序表实现队列时出队删除第一个元素需要移动所有元素时间复杂度是O(n)元素越多移动越慢。如果队列数据量小、操作不频繁顺序表切片足够用若数据量大、出队频繁链表实现更优——链表出队时只需修改头指针时间复杂度O(1)无需移动元素效率更高但链表代码稍复杂0基础可先掌握顺序表实现。队列两种实现方式对比示意图放在代码块里清晰易读【队列的两种实现方式对比】 ┌─────────────────────────────────────────────────┐ │ 顺序表切片实现队列 │ ├─────────────────────────────────────────────────┤ │ 初始化空切片var queue []int │ │ 入队append(queue, num) 队尾O(1) │ │ 出队queue queue[1:] 移动元素O(n) │ │ 优点代码简单、小数据量适用 │ │ 缺点大数据量出队慢、可能浪费内存 │ └─────────────────────────────────────────────────┘ ┌─────────────────────────────────────────────────┐ │ 链表实现队列 │ ├─────────────────────────────────────────────────┤ │ 初始化定义链表节点维护头、尾指针 │ │ 入队修改尾指针添加新节点O(1) │ │ 出队修改头指针删除队头节点O(1) │ │ 优点大数据量高效、无扩容浪费 │ │ 缺点代码复杂、需维护指针 │ └─────────────────────────────────────────────────┘packagemainimportfmt// 定义队列结构用切片存储数据线性结构typeQueuestruct{data[]int// 存储队列数据int类型举例}// 入队往队尾添加数据类比排队站到队尾func(q*Queue)Enqueue(numint){q.dataappend(q.data,num)// 切片末尾添加就是队尾}// 出队从队头删除并返回数据类比排队最前面的人离开func(q*Queue)Dequeue()(int,error){// 先判断队列是否为空空队列不能出队ifq.IsEmpty(){return0,fmt.Errorf(队列为空无法出队)}// 切片第一个元素是队头先取出再删除front:q.data[0]q.dataq.data[1:]// 切片从索引1开始相当于删除第一个元素returnfront,nil}// 查看队头只看不删func(q*Queue)Front()(int,error){ifq.IsEmpty(){return0,fmt.Errorf(队列为空无队头元素)}returnq.data[0],nil}// 判断队列是否为空func(q*Queue)IsEmpty()bool{returnlen(q.data)0}// 测试一下funcmain(){// 初始化一个空队列queue:Queue{}// 入队1-2-3类比排队1在最前3在队尾queue.Enqueue(1)queue.Enqueue(2)queue.Enqueue(3)fmt.Println(入队后队头元素,queue.Front())// 输出1// 出队先出1再出2类比排队1先买完离开然后是2deq1,_:queue.Dequeue()fmt.Println(第一次出队,deq1)// 输出1deq2,_:queue.Dequeue()fmt.Println(第二次出队,deq2)// 输出2fmt.Println(出队两次后队列是否为空,queue.IsEmpty())// 输出false还有3}3. 队列的实际用途贴近生活好记消息通知我们手机收到的消息按时间顺序排列先收到的先显示、先处理就是队列打印队列多个人同时打印文件打印机按顺序打印先提交的先打印后提交的排队也是队列的逻辑。三、栈和队列的核心区别一张表看懂0基础不混淆对比项栈Stack线性队列Queue核心逻辑后进先出LIFO像叠衣服先进先出FIFO像排队买奶茶操作端只有一个开口栈顶入栈、出栈都在这两个开口队头出、队尾进Go实现切片append入栈、删除末尾出栈切片append入队、删除开头出队最优/常见实现小数据量顺序表切片大数据量链表小数据量顺序表切片大数据量链表生活类比叠衣服、浏览器后退、装快递箱子排队买奶茶、打印文件、消息通知补充表格中两种结构的实现选择可结合上面的示意图理解小数据量优先选顺序表切片简单高效大数据量优先选链表无扩容、不浪费内存。四、0基础总结重点记这3点不迷路栈和队列都是「线性结构」数据排成一条直线没有分支栈后进先出先放的后拿只有一个操作口Go用切片就能实现实现上小数据量用顺序表切片最常见大数据量、需频繁增减数据时链表更优无扩容烦恼、不浪费内存纠正“顺序表绝对最优”的误区兼顾扩容和内存浪费问题。线性队列主流逻辑是先进先出先放的先拿有两个操作口队头出、队尾进同样用切片实现也存在先进后出的特殊线性队列如双端队列的特殊使用但常规场景下以先进先出为主实现上小数据量用顺序表切片最常见大数据量用链表更优。其实数据结构没有那么可怕只要把抽象的逻辑和生活中的场景结合起来再动手跑一跑简单的代码0基础也能轻松掌握。今天的栈和队列就讲到这里后续可以再深入学习更复杂的队列类型但先把这个基础打牢就够啦如果大家有不懂的地方或者想补充其他知识点欢迎在评论区留言哦【结语】到这里Go中栈和队列的核心知识点就全部讲解完毕了。我们不难发现栈和队列的实现始终围绕着上一篇提到的切片顺序表展开同时也了解了链表在大数据场景下的优势这既是对切片copy知识点的延伸也为我们下一篇要学习的哈希表做好了铺垫。下一篇我们将跳出线性结构的范畴学习非线性结构中的哈希表看看它如何解决栈和队列在查找效率上的局限继续跟着节奏一步步夯实Go数据结构的基础关注我点赞、收藏⭐本篇内容注文档部分内容可能由 AI 生成