引子老王食堂的打饭长龙还记得上一篇里那位在食堂盯着一摞盘子悟出栈的老王吗那天他在洗碗台前琢磨出了后进先出的栈意犹未尽。一转身却被食堂里另一个更热闹的场景吸引住了——打饭窗口前排起了一条长长的队伍。学生们自觉地一个接一个排在后面打饭师傅则永远从队伍最前头的那位开始打。打完一个前头那位心满意足地走了后面的人自动往前挪一步新来的同学则乖乖地排到队伍的最末尾。老王盯着这条井然有序的长龙又一次拍了大腿眼睛放光“妙啊你们看这条队伍也有个雷打不动的规矩——和那摞盘子刚好反过来盘子是’后来的先走’可这队伍是’先来的先打饭、先来的先离开’谁先排上谁就先被服务公平得很”打饭师傅笑道“王哥排队不就这样嘛先来后到天经地义。”老王哈哈大笑“就是这’天经地义’四个字里头又藏着计算机世界里一个无比重要、无比公平的’摆货家什’啊而且它正好是’那摞盘子’的’镜像兄弟’”这个藏在打饭长龙里的家什正是我们这一篇的主角也是栈那位最经典的对照搭档——队列Queue。第一章队列是什么一支只能尾进头出的队伍要理解队列你只需牢牢记住食堂里那条打饭长龙的画面。队列的全部精髓就浓缩在它那条铁打的规矩里新来的只能排到队尾被服务的只能是队头。一头进另一头出绝不插队、绝不逆行。这条规矩带来了一个无比鲜明的特征它也有个专门的名字叫——FIFOFirst In, First Out“先进先出”。翻译成大白话就是“先来的先走。”是不是觉得特别耳熟没错它正好和上一篇栈的LIFO后进先出针锋相对、完美镜像我们先来认识队列的几个行话队头Front队伍的最前面是唯一出去的地方打饭、离开队尾Rear队伍的最后面是唯一进来的地方新人排队入队Enqueue从队尾加入一个新成员出队Dequeue从队头送走一个老成员。我们来看一支队伍是怎么排长又变短的入队过程新人只能从队尾排 来了A 来了B 来了C 队头 队尾 队头 队尾 队头 队尾 [ A ] [ A ][ B ] [ A ][ B ][ C ] ↑进来 ↑ ↑进来 ↑ ↑进来 出队过程只能从队头走 A先走 B再走 队头 队尾 队头 队尾 [ B ][ C ] [ C ] ↑A从这头离开 ↑B从这头离开核心画面队列就是一支只能从队尾进、从队头出的队伍。你想插队、想从中间走对不起规矩不允许先来的先服务后来的乖乖等——这就是先进先出公平、有序最讲先来后到。第二章栈 vs 队列——一场出入口的镜像对决讲到这里必须把队列和上一篇的栈拉到一起好好对比一下——因为它俩简直就是一对镜像兄弟它们的区别只在一个地方出入口在哪里。栈一摞盘子 队列一条长龙 形象 ┌───┐ ────────────→ │ C │← 顶进出都在这 进→[A][B][C]→出 │ B │ 队尾↑ ↑队头 │ A │ 尾进 头出 └───┘ 规矩 LIFO 后进先出 FIFO 先进先出 出入口 同一头顶进出 一头进另一头出 谁先走 最后来的先走 最先来的先走 关键词 反悔、返回 公平、有序老王一语道破了它俩的精髓栈是’一个口’——进也从顶上进出也从顶上出挤在一头所以’后来的反而先走’。队列是’两个口’——尾巴进脑袋出一进一出泾渭分明所以’先来的就先走’。一个像’死胡同’进去了得原路退出来一个像’过道’从这头进、那头出畅通无阻。深刻规律栈和队列是数据结构世界里又一对经典的对照搭档就像数组 vs 链表那样。栈后进先出擅长处理反悔、返回、层层深入的事队列先进先出擅长处理排队、调度、先来后到的事。它们没有谁好谁坏只是分别对应了现实世界里两种最常见的秩序——“后来居上和先来后到”。第三章队列的动作——简单、公平、快O(1)和栈一样队列的操作也简单到极致——就两个动作3.1 入队Enqueue从队尾加入新成员来了乖乖排到队伍最末尾。3.2 出队Dequeue从队头送走轮到服务了永远是队头那位先走。而且你送走的必然是最早来的那一个。就这么两个动作。因为永远只在队头和队尾两个固定端点操作不用动中间的任何人所以它也快得惊人无论这支队伍有10个人还是1000万人——入队、出队永远只是队尾加一个/队头走一个一步到位。这正是我们最爱的、最快的O(1) 时间复杂度一个小插曲队列的底层与环形智慧和栈一样队列底层也是既可以用数组、也可以用链表搭起来的数组链表这两位老前辈又一次重出江湖。不过用数组实现队列时会遇到一个有趣的小麻烦队头的人不断离开前面就空出一截位置可这些位置白白浪费了队伍只往后排前面腾出的地儿用不上。聪明的工程师想了个妙招——让队列首尾相连弯成一个圈后面排满了就绕回到前面空出来的位置接着排。这就叫环形队列循环队列把空间利用得明明白白一点不浪费。普通队列[空][空][C][D][E] ← 前面两格白白浪费了 环形队列 ┌──→ 弯成圈前面的空位绕回来接着用 [F][G][C][D][E] ← 一格不浪费小智慧环形队列告诉我们——有时候把直线思维弯成循环思维就能让原本浪费的资源重新流动起来。这又是一个换个角度柳暗花明的妙例。第四章队列的用武之地——凡是排队皆是队列队列的应用比栈还要直白——只要现实里有排队、按先来后到处理的地方背后几乎都是一个队列在工作4.1 经典应用一打印机的任务排队办公室里十个人同时往一台打印机发文件为什么不会乱成一锅粥因为打印机内部有一个队列谁先点了打印谁的任务就先入队打印机则老老实实从队头开始一个一个打。先发的先打印后发的乖乖排队等——公平有序绝不插队。4.2 经典应用二叫号系统银行、医院、餐厅你去银行办业务取个号A052然后坐等屏幕叫到你。这就是一个活生生的队列你取号就是入队排到队尾柜员每办完一个就叫下一号就是出队队头离开。严格的先来后到保证了排队的公平——这正是先进先出在守护着秩序。4.3 经典应用三你刷的每一条消息、每一个视频你发微信、抢演唱会门票、双十一下单……成千上万的请求涌向服务器怎么办服务器用队列把这些请求排好队按先来后到一个个处理避免一拥而上、瞬间崩溃。这叫消息队列是支撑起整个互联网扛住高并发的幕后功臣。你抢票时那句前面还有2000人排队背后就是一个巨大的队列4.4 经典应用四树和图的层层探索BFS这是队列一个稍高级、但极其重要的应用——广度优先搜索BFS。想象你要在一座迷宫里找出口广度优先的策略是先把眼前所有的岔路都看一遍再一层一层向外扩散像水波纹一样。而维持这种一层一层、先发现的先探索的秩序靠的正是队列后面讲树和图时它还会闪亮登场。恍然大悟原来队列就是现实世界排队的完美映射凡是需要公平对待、先来后到、按顺序处理的地方队列就在默默维持着秩序。它不像栈那样玩反悔、返回的花样它只专注于一件朴素而伟大的事——让每一个先来的都不被辜负。第五章队列的性格画像老王给队列也画了一张性格画像和栈的那张并排贴在一起队列一条长龙 核心规矩 FIFO 先进先出尾进头出 入队/出队 ⚡ 极快 O(1)只动队头队尾 能否插队 ❌ 不行必须老实排到队尾 关键词 公平、有序、先来后到 一句话 最讲规矩的排队大师让先来的不被辜负老王看着栈和队列这两张并排的画像感慨万千你看这两兄弟——栈教会我们’反悔与返回’的智慧队列则守护着’公平与秩序’的底线。一个让我们在做错时能’回头’一个让我们在拥挤时仍’有序’。它俩看着简单可这世间的运转还真离不开它们呢尾声一条长龙的智慧亦是人生的智慧老王的一条长龙从食堂的打饭奇观讲到打印机、叫号机、抢票系统的幕后真相终于把队列这个看似平凡、实则公平的家什说了个透。但当我们合上书会发现这一条朴素的队伍竟也排着几分耐人寻味的人生哲理。第一“先来后到”是这世间最朴素的公平。队列用一条简单的规矩——“先进先出”——守护着排队的公平谁先来谁先被服务没有特权没有插队。这何尝不是文明社会最珍贵的底色那一条条自觉排起的长龙背后是一种朴素的契约精神——我尊重先来后到相信只要老实排队就终会轮到我。一个愿意为公平排队、也愿意守护这份公平的人本身就在为这个世界增添着一份秩序的温柔。第二急不得也跳不得耐心等待自有回响。队列里没有捷径——你想插队规矩不允许。你能做的就是排在该在的位置一步一步往前挪。这像极了人生的许多时刻。我们总想一步登天、弯道超车可有些事就是急不得、跳不得需要你老老实实地排队、踏踏实实地积累。别羡慕那些看似插队的人——真正的成长没有捷径你认真排过的每一步队攒下的每一分耐心终会在轮到你的那一刻给你回响。第三把直线弯成循环浪费也能变成流动。还记得那个环形队列的妙招吗把白白浪费的空位弯成一个圈重新利用起来。这是一种了不起的智慧——当资源看似用尽、浪费时换一种’循环’的眼光往往就能让它重新流动。人生和事业又何尝不是很多看似走到尽头的困境并非真的无路可走而是我们还困在直线的思维里。 试着把它弯成一个循环让能量重新流转起来——你会发现绝处往往藏着逢生。下次当你在银行安静地等待叫号、在抢票时看着前方排队人数、或是在食堂里自觉地排到长龙末尾时请记得——在那看不见的背后正有一条条朴素的队伍用它先进先出的古老智慧为这个拥挤的世界又公平又有序地守护着每一份先来后到。队列就是这门关于公平与秩序、先来后到的、朴素而温暖的智慧。它和栈这位镜像兄弟一道共同道出了那个朴素而隽永的真理——有些事要懂得回头栈有些事要学会排队队列该反悔时能从容退回该等待时能耐心守序——一个人若能在这两者间拿捏好分寸便能在这熙熙攘攘的人间走得既灵活又坦荡。这就是藏在一条长龙背后的队列的全部浪漫。