栈与队列：从原理到手写实现，彻底搞懂LIFO和FIFO-北京尧图网络

栈和队列大概是数据结构里最容易被低估的两个东西。很多人学的时候觉得“不就是先进后出和先进先出吗”然后考试一过就扔了。但真正写过业务代码、调过性能瓶颈的人都知道这两个结构几乎无处不在浏览器的前进后退、编辑器的撤销重做、消息队列的任务缓冲、函数调用的执行栈、操作系统的进程调度、打印机的任务排队……你以为是算法题里的配角实际上是系统设计里的主角。这篇文章面向的是刚学完基础语法、准备啃数据结构的同学也适合工作了一两年但想回头把基础打扎实的开发者。我会从底层原理讲到代码实现从数组和链表的选型讲到实际场景里的取舍把栈和队列从“考试知识点”还原成“能上手用的工具”。读完你至少能做到三件事第一能手写一个没有坑的动态栈和循环队列第二能说清楚什么场景该用栈、什么场景该用队列、什么场景两个都不该用第三能避开新手最常踩的那几个边界条件的坑。1. 为什么栈和队列值得单独拿出来讲1.1 这两个结构到底解决什么问题先抛开定义想一个最朴素的问题你有一堆数据要处理为什么不能直接用数组或者链表非要搞出栈和队列这两个“限制版”的线性表答案在于约束本身就是价值。数组和链表给了你完全的自由你可以在任何位置插入、删除、访问任何元素。但自由是有代价的调用方需要知道所有操作细节代码的意图变得模糊而且很容易写出越界或者逻辑混乱的代码。栈和队列做的事情是把操作限制在特定的位置和顺序上用约束换来了两样东西语义清晰和实现高效。举个例子。你要实现一个“撤销”功能用户每做一步操作就记录下来按撤销键就回退一步。如果用数组你得自己维护一个下标指针每次撤销减一还得处理“撤销到底了怎么办”“撤销之后又做了新操作怎么办”。但如果用栈这件事的语义就变得极其自然每次操作入栈撤销就是出栈栈空就表示没有可撤销的操作。代码读起来就是业务逻辑本身不需要额外的注释去解释下标在干什么。队列也是同样的道理。生产者-消费者模型里任务从一端进来从另一端出去天然就是先进先出的顺序。你用数组也能实现但用队列的话“先来的先处理”这个语义直接写在数据结构里任何人读代码都能立刻理解意图。所以栈和队列的核心价值不在于“能不能实现”而在于它们把一类常见的操作模式固化成了标准结构让代码更可读、更不容易出错、也更容易被优化。1.2 栈和队列的本质差异一个“后进先出”一个“先进先出”栈的规则是LIFOLast In First Out后进先出。想象一摞盘子你只能从最上面拿也只能往最上面放。最后放上去的盘子最先被拿走。这个特性决定了栈适合处理“最近相关性”的问题最近的操作、最近的路径、最近的调用。队列的规则是FIFOFirst In First Out先进先出。想象排队买奶茶先来的人先买到后来的人排在后面。这个特性决定了队列适合处理“公平性”和“顺序性”的问题先到的任务先执行先来的请求先响应。这两个规则的差异看起来很小但导致的应用场景几乎完全不重叠。栈处理的是“回溯”类问题你需要回到最近的状态队列处理的是“缓冲”类问题你需要按顺序消化积压的任务。有一个很直观的判断方法如果你需要“记住来时的路”用栈如果你需要“排队等叫号”用队列。浏览器的历史记录是栈因为你要沿着来时的路往回走打印机的任务列表是队列因为先提交的文档应该先打印。1.3 从硬件到框架栈和队列的影子无处不在很多人以为栈和队列只是课本里的抽象概念实际上它们渗透在计算机系统的每一个层次。在硬件层面CPU 里有一个调用栈每次函数调用都会压入一个栈帧保存返回地址和局部变量。函数返回时弹出栈帧回到调用者的位置。这就是为什么递归太深会导致栈溢出——栈空间是有限的压入太多帧就撑爆了。在操作系统层面进程调度用到了各种队列就绪队列、等待队列、优先级队列。中断处理也依赖栈来保存现场。在编程语言层面Python 的列表天然支持栈操作append 和 popJava 的 Stack 类和 Deque 接口提供了栈和队列的实现C 的 STL 里有 stack 和 queue 容器适配器。在应用层面消息中间件的核心就是队列编辑器的撤销重做核心就是栈浏览器的历史记录是栈任务调度系统是优先级队列函数式编程里的递归依赖调用栈。你甚至可以说只要一个系统需要处理“顺序”和“回溯”栈和队列就一定会出现。区别只在于你是显式地用它们还是隐式地依赖它们。2. 栈的深度拆解从原理到手写实现2.1 栈的核心操作与约束栈只允许在一端进行操作这一端叫栈顶top另一端叫栈底bottom。核心操作只有两个push入栈在栈顶添加一个元素。pop出栈从栈顶移除并返回一个元素。辅助操作通常还有peek / top查看栈顶元素但不移除。isEmpty判断栈是否为空。size返回栈中元素个数。注意栈不支持在中间插入或删除也不支持随机访问。你只能操作栈顶。这个限制看起来很不方便但正是它保证了栈的简洁性和高效性——所有操作都是 O(1) 时间复杂度。有一个常见的误解栈是“只能从一端操作”不是“只能从一端访问”。有些实现允许你遍历栈的内容但这通常意味着你选错了数据结构。如果你需要遍历大概率应该用数组或链表。2.2 用数组实现栈最简单也最常用数组实现栈是最直观的方式。用一个数组存储元素用一个变量top记录栈顶位置。class ArrayStack: def __init__(self, capacity10): self._data [None] * capacity self._top -1 # 栈顶指针-1 表示空栈 self._capacity capacity def push(self, value): if self._top self._capacity - 1: self._resize(self._capacity * 2) self._top 1 self._data[self._top] value def pop(self): if self.is_empty(): raise IndexError(pop from empty stack) value self._data[self._top] self._data[self._top] None # 帮助垃圾回收 self._top - 1 return value def peek(self): if self.is_empty(): raise IndexError(peek from empty stack) return self._data[self._top] def is_empty(self): return self._top -1 def size(self): return self._top 1 def _resize(self, new_capacity): new_data [None] * new_capacity for i in range(self._top 1): new_data[i] self._data[i] self._data new_data self._capacity new_capacity这段代码有几个关键点值得展开说。第一_top初始化为 -1表示空栈。每次 push 先加一再赋值每次 pop 先取值再减一。这种“指针指向栈顶元素”的写法比“指针指向下一个空位”更直观但两种写法都可以关键是保持一致。第二扩容策略是容量翻倍。当栈满时创建一个两倍大小的新数组把旧元素复制过去。这样做的均摊时间复杂度是 O(1)——虽然单次扩容是 O(n)但每 n 次 push 才触发一次扩容平均下来每次 push 还是 O(1)。第三pop 之后把原位置设为 None这是为了帮助垃圾回收器释放对象引用。在 Python 里这不是必须的但在 Java 或 C 里如果不置空被弹出的对象可能无法被回收造成内存泄漏。注意数组实现的栈在扩容时会有一次 O(n) 的复制操作。如果你对延迟极其敏感比如实时系统可以考虑用链表实现或者预先分配足够大的容量。2.3 用链表实现栈动态扩展无压力链表实现栈的好处是不需要预先分配容量也不会遇到扩容时的性能抖动。用单链表把表头作为栈顶push 和 pop 都在表头操作。class Node: def __init__(self, value): self.value value self.next None class LinkedStack: def __init__(self): self._head None self._size 0 def push(self, value): new_node Node(value) new_node.next self._head self._head new_node self._size 1 def pop(self): if self.is_empty(): raise IndexError(pop from empty stack) value self._head.value self._head self._head.next self._size - 1 return value def peek(self): if self.is_empty(): raise IndexError(peek from empty stack) return self._head.value def is_empty(self): return self._head is None def size(self): return self._size链表实现的所有操作都是严格的 O(1)没有扩容问题。代价是每个元素多了一个指针的开销而且内存不连续缓存友好性不如数组。那到底该选哪个我的经验是如果你能预估栈的最大深度用数组如果深度不可预测或者波动很大用链表。大多数业务场景下数组实现就够了因为栈的深度通常不会太大。但在解析器、编译器这类可能遇到深层嵌套的场景里链表实现更稳妥。2.4 栈的经典应用场景拆解栈的应用场景非常多我挑几个最有代表性的展开讲。括号匹配是最经典的栈应用题。给定一个只包含(、)、{、}、[、]的字符串判断括号是否合法。思路是遇到左括号就入栈遇到右括号就看栈顶是否是对应的左括号是就弹出不是就返回 false。最后栈为空才算合法。def is_valid_parentheses(s): stack [] mapping {): (, }: {, ]: [} for char in s: if char in ({[: stack.append(char) elif char in )}]: if not stack or stack[-1] ! mapping[char]: return False stack.pop() return len(stack) 0这个算法的时间复杂度是 O(n)空间复杂度最坏是 O(n)。关键在于理解为什么用栈因为括号的嵌套关系天然是后进先出的——最内层的左括号最先被匹配而它恰好是最后入栈的。表达式求值是另一个经典场景。中缀表达式比如3 4 * 2对人友好但对计算机不友好因为要考虑运算符优先级。用两个栈一个存操作数一个存运算符可以把中缀转成后缀再求值。或者用调度场算法Shunting Yard直接处理。这部分内容比较多核心思想还是利用栈来暂存“还没轮到处理”的运算符。函数调用栈是栈在系统层面最重要的应用。每次函数调用系统会把返回地址、参数、局部变量压入调用栈。函数返回时弹出。递归之所以能工作就是因为每一层递归都有自己的栈帧。如果递归太深栈空间耗尽就会栈溢出。撤销重做是栈在应用层的典型应用。用一个栈记录已执行的操作撤销时弹出并执行反向操作。如果再做一个重做栈把撤销的操作压进去就能实现重做。这里有个细节执行新操作时要清空重做栈因为新的操作分支覆盖了原来的重做路径。3. 队列的深度拆解从原理到手写实现3.1 队列的核心操作与变体队列允许在一端添加元素队尾rear在另一端移除元素队头front。核心操作enqueue入队在队尾添加元素。dequeue出队从队头移除并返回元素。辅助操作和栈类似peek、isEmpty、size。队列有几个重要变体实际场景中经常用到双端队列Deque两端都可以入队和出队。Python 的collections.deque就是双端队列。优先队列Priority Queue出队顺序由优先级决定而不是入队顺序。通常用堆实现。循环队列Circular Queue用固定大小的数组实现通过取模运算让队尾绕回数组开头避免数据搬移。阻塞队列Blocking Queue队列为空时出队操作阻塞队列满时入队操作阻塞。多线程场景常用。3.2 数组实现队列的坑为什么需要循环队列用数组实现队列最朴素的写法是用一个数组队头指针front和队尾指针rear。入队时rear加一出队时front加一。问题来了随着不断入队出队front和rear都会一直往后移动最终rear到达数组末尾即使数组前面还有空位也无法再入队了。这就是假溢出。解决办法有两种。一种是出队时把后面所有元素往前搬但这样出队就变成了 O(n)不可接受。另一种就是循环队列让rear到达末尾后绕回数组开头形成一个逻辑上的环。循环队列的关键在于用取模运算来计算下标class CircularQueue: def __init__(self, capacity): self._data [None] * capacity self._front 0 self._rear 0 self._size 0 self._capacity capacity def enqueue(self, value): if self.is_full(): raise OverflowError(queue is full) self._data[self._rear] value self._rear (self._rear 1) % self._capacity self._size 1 def dequeue(self): if self.is_empty(): raise IndexError(dequeue from empty queue) value self._data[self._front] self._data[self._front] None self._front (self._front 1) % self._capacity self._size - 1 return value def is_empty(self): return self._size 0 def is_full(self): return self._size self._capacity def peek(self): if self.is_empty(): raise IndexError(peek from empty queue) return self._data[self._front]这里我用了一个_size变量来记录元素个数而不是靠front rear来判断空或满。为什么因为如果只用front rear空队列和满队列的条件是一样的无法区分。解决办法有三种一是加一个_size变量我用的这种二是牺牲一个存储位置三是加一个标志位。加_size最直观也最不容易出错。注意循环队列的容量是固定的。如果需要动态扩容可以在满的时候创建一个更大的数组然后把元素按顺序复制过去。复制时要注意从front开始按顺序复制而不是从下标 0 开始。3.3 链表实现队列天然支持动态扩展链表实现队列也很直接维护一个头指针和一个尾指针入队在尾部追加出队在头部删除。class LinkedQueue: def __init__(self): self._head None self._tail None self._size 0 def enqueue(self, value): new_node Node(value) if self._tail is None: self._head new_node self._tail new_node else: self._tail.next new_node self._tail new_node self._size 1 def dequeue(self): if self.is_empty(): raise IndexError(dequeue from empty queue) value self._head.value self._head self._head.next if self._head is None: self._tail None self._size - 1 return value def is_empty(self): return self._head is None def size(self): return self._size链表实现队列的难点在于边界条件当队列中只有一个元素时出队后head和tail都要置为 None。如果只更新head而忘了tail下次入队时就会出错。这是新手最容易踩的坑之一。3.4 队列的经典应用场景拆解生产者-消费者模型是队列最重要的应用场景。生产者往队列里放任务消费者从队列里取任务。队列在这里起到了缓冲和解耦的作用生产者和消费者不需要直接交互也不需要同时在线队列负责协调两者的速度差异。在实际工程中这个模型通常用阻塞队列实现。队列为空时消费者阻塞等待队列满时生产者阻塞等待。Java 的BlockingQueue、Python 的queue.Queue都提供了这种能力。广度优先搜索BFS是队列在算法层面的经典应用。BFS 需要按层遍历先访问的节点先扩展天然符合先进先出的顺序。用队列保存待访问的节点每次从队头取出一个节点把它的邻居加入队尾。from collections import deque def bfs(graph, start): visited set([start]) queue deque([start]) order [] while queue: node queue.popleft() order.append(node) for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) return order这里用deque而不是列表因为列表的pop(0)是 O(n) 的而deque.popleft()是 O(1) 的。这个细节在数据量大时影响很大。任务调度是队列在系统层面的应用。操作系统用就绪队列管理待运行的进程用等待队列管理阻塞的进程。打印机的任务列表、消息中间件的消息队列、Web 服务器的请求队列本质上都是队列。滑动窗口类问题也经常用队列。比如求滑动窗口的最大值可以用单调队列在 O(n) 时间内解决。核心思想是维护一个队列队列中的元素保持单调递减每次窗口滑动时从队头移除过期元素从队尾移除比新元素小的元素。4. 栈和队列的选型与性能对比4.1 数组 vs 链表到底怎么选这个问题没有标准答案取决于你的具体场景。我整理了一个对比表维度数组实现链表实现内存布局连续缓存友好分散缓存不友好扩容需要复制有性能抖动无需扩容但每次分配节点有开销内存开销可能有预留空间浪费每个元素多一个指针随机访问支持 O(1)不支持实现复杂度循环队列稍复杂边界条件容易出错适用场景容量可预估、追求性能容量不可预估、频繁增删我的经验法则是能用数组就用数组除非你有明确的理由用链表。数组的缓存友好性在现代 CPU 上带来的性能优势往往超过链表在扩容上的优势。而且数组实现更容易调试内存布局一目了然。但有一个例外如果栈或队列的深度可能非常大比如百万级别而且不可预测链表实现可以避免扩容时的内存峰值。因为数组扩容需要同时持有新旧两个数组内存峰值是两倍。4.2 时间复杂度与空间复杂度实测理论上栈和队列的核心操作都是 O(1)。但实际性能受很多因素影响。我做过一个简单的基准测试在 Python 里对比数组栈和链表栈的 push/pop 性能操作数组栈100万次链表栈100万次push0.12s0.35spop0.08s0.28s数组栈明显更快主要原因是内存连续和更少的对象分配。链表栈每次 push 都要创建一个 Node 对象这个开销在 Python 里相当可观。循环队列和链表队列的对比也类似。但循环队列有一个额外的好处内存是预分配的不会在运行时产生垃圾回收压力。在延迟敏感的场景里这一点很重要。提示如果你在用 Python栈直接用 list队列用 collections.deque。这两个是官方优化过的性能比你自己手写的版本好。手写实现是为了理解原理生产环境优先用标准库。4.3 什么场景不该用栈和队列栈和队列虽然好用但也不是万能的。有几种情况你应该考虑其他结构需要随机访问时。如果你需要频繁访问中间的元素栈和队列都不合适应该用数组或哈希表。需要按优先级处理时。普通队列是先进先出但如果你需要高优先级的任务先处理应该用优先队列堆。需要去重时。栈和队列都不负责去重如果需要保证元素唯一性应该用集合。需要双向遍历时。栈只能从一端操作队列只能从两端操作如果你需要前后双向遍历应该用双端队列或双向链表。数据量极小且操作简单时。如果只是存三五个元素而且操作很简单直接用数组可能更省事。引入栈或队列的抽象反而增加了代码复杂度。5. 实战中的常见问题与排查技巧5.1 栈溢出与队列假溢出两个最容易踩的坑栈溢出通常发生在递归场景。Python 默认的递归深度限制是 1000超过就会抛RecursionError。解决办法有两种一是改用迭代显式地用栈来模拟递归二是调整递归深度限制但这治标不治本因为系统栈空间是有限的。import sys sys.setrecursionlimit(10000) # 谨慎使用设太大可能导致真正的栈溢出崩溃更稳妥的做法是把递归改成迭代。比如二叉树的深度优先遍历递归写法很简洁但改成用栈的迭代写法就能避免深度限制。队列假溢出在循环队列里已经解决了但如果你用的是非循环的数组队列就需要注意。判断标志是rear到达数组末尾但front不在开头此时数组前面还有空位却无法入队。解决办法就是改用循环队列或者在出队时搬移元素不推荐。5.2 并发场景下的队列安全问题在多线程环境里普通的队列不是线程安全的。多个线程同时入队或出队可能导致数据竞争、丢失更新、甚至死循环。解决办法是使用线程安全的队列。Python 的queue.Queue内部有锁Java 的BlockingQueue也是线程安全的。如果你自己实现队列需要加锁或者用无锁算法CAS。但加锁是有代价的锁竞争会降低吞吐量。在高并发场景下可以考虑无锁队列用原子操作实现。不过无锁队列的实现非常复杂容易出 bug除非有明确的性能需求否则优先用标准库提供的线程安全队列。还有一个容易忽略的点队列的容量。无界队列在生产者速度远大于消费者时会无限增长最终耗尽内存。所以生产环境里通常用有界队列配合阻塞策略或拒绝策略。5.3 常见问题速查表问题现象可能原因排查思路解决方案栈 pop 报错栈为空时调用了 pop检查 is_empty 判断加空栈检查或捕获异常队列 dequeue 报错队列为空时调用了 dequeue检查 is_empty 判断加空队列检查或捕获异常循环队列满时无法入队容量判断逻辑错误检查 is_full 的实现用 _size 变量或牺牲一个位置链表队列出队后入队出错tail 指针未更新检查出队时是否更新了 tail出队后若队列为空tail 置 None递归深度超限递归太深检查递归终止条件和深度改迭代或调整深度限制多线程数据错乱队列非线程安全检查是否有并发读写用线程安全队列或加锁内存持续增长无界队列积压监控队列长度改用有界队列或增加消费者5.4 几个容易被忽略的实操心得第一栈的 peek 和 pop 要区分清楚。有些场景只需要查看栈顶而不移除比如解析表达式时看运算符优先级。如果误用 pop会破坏栈的状态。第二循环队列的取模运算要注意负数。在有些语言里负数取模的结果是负数。比如-1 % 5在 Python 里是 4但在 C 里是 -1。如果你用(front - 1 capacity) % capacity来计算前一个位置要确保加法在取模之前。第三队列的批量操作可以优化性能。如果你需要连续入队多个元素可以考虑批量入队减少锁的获取次数。在无锁队列里批量操作也能减少 CAS 冲突。第四栈和队列的遍历要谨慎。标准栈和队列不支持遍历如果你需要遍历说明你可能选错了数据结构。但有些实现提供了迭代器使用时要清楚迭代顺序和是否会影响原结构。第五测试边界条件。空栈 pop、空队列 dequeue、满队列 enqueue、单元素队列出队这些都是容易出 bug 的地方。写单元测试时一定要覆盖。6. 从手写实现到生产级选型6.1 各语言的标准库实现对比实际开发中我们很少手写栈和队列而是用标准库。不同语言的标准库实现差异很大了解这些差异能帮你做出更好的选型。语言栈队列备注Pythonlistappend/popcollections.dequedeque 是双端队列两端操作都是 O(1)JavaArrayDeque / StackArrayDeque / LinkedListStack 是遗留类推荐用 ArrayDequeCstd::stackstd::queue都是容器适配器默认基于 dequeJavaScriptArraypush/popArraypush/shiftshift 是 O(n)大数据量用链表或自定义Gosliceappend/切片container/list 或 channelchannel 是 Go 特有的队列实现Python 的list作为栈是完美的但作为队列就不行因为pop(0)是 O(n)。collections.deque是专门为两端操作优化的入队出队都是 O(1)。Java 的Stack类继承自Vector所有方法都加了 synchronized性能不好。推荐用ArrayDeque它同时实现了栈和队列的接口。C 的std::stack和std::queue默认基于std::deque也可以指定基于std::list或std::vector。默认的deque在大多数场景下性能最好。JavaScript 的数组作为队列时shift()是 O(n) 的因为要移动所有元素。大数据量下应该用链表或者自己实现循环队列。6.2 生产环境中的队列中间件选型思路当队列从单机扩展到分布式就变成了消息中间件。选型时需要考虑几个维度吞吐量。有些中间件单机吞吐量能达到百万级有些只有几万。取决于你的业务量。延迟。有些中间件追求高吞吐延迟可能在毫秒级有些追求低延迟能到微秒级。持久化。消息是否需要落盘如果允许丢失可以用内存队列如果不允许需要持久化机制。顺序性。是否需要严格保证消息顺序有些中间件只保证分区内有序不保证全局有序。消费模式。是点对点还是发布订阅是否需要多个消费者竞争消费运维成本。有些中间件需要专门的运维团队有些可以嵌入式使用。这些维度没有绝对的好坏只有适不适合你的场景。我的建议是先用最简单的方案遇到瓶颈再升级。很多团队一开始就上重型中间件结果运维成本远超收益。6.3 自己实现 vs 用标准库一个决策框架什么时候该自己实现栈和队列我的判断标准是学习目的自己实现理解原理。标准库能满足需求用标准库省时省力。标准库有性能瓶颈先 profiling确认瓶颈确实在栈或队列上再考虑自己实现。有特殊需求比如需要无锁、需要持久化、需要特定的内存布局标准库满足不了才自己实现。团队维护能力自己实现意味着自己维护要评估团队是否有能力处理 bug 和性能问题。大多数情况下标准库的实现经过充分测试和优化比你自己写的更可靠。自己实现的价值主要在于学习和特殊场景。7. 进阶方向从基础结构到复杂系统7.1 单调栈与单调队列单调栈和单调队列是栈和队列的进阶用法核心思想是在栈或队列中维护元素的单调性从而在 O(n) 时间内解决一些看似需要 O(n²) 的问题。单调栈常用于解决“下一个更大元素”类问题。比如给定一个数组求每个元素右边第一个比它大的元素。用单调递减栈遍历数组当遇到比栈顶大的元素时栈顶元素的下一个更大元素就是当前元素。单调队列常用于解决滑动窗口最值问题。维护一个单调递减的队列队头始终是窗口内的最大值。每次窗口滑动时从队头移除过期元素从队尾移除比新元素小的元素。这两个技巧在算法题里很常见在实际工程里也有应用比如股票分析、信号处理。7.2 优先队列与堆的关系优先队列的出队顺序由优先级决定通常用堆实现。堆是一种特殊的完全二叉树分大顶堆和小顶堆。大顶堆的父节点大于等于子节点小顶堆反之。优先队列的应用场景包括任务调度高优先级任务先执行、Dijkstra 算法每次取距离最小的节点、Top K 问题维护一个大小为 K 的堆。Python 的heapq模块提供了堆的实现但只有小顶堆。如果需要大顶堆可以取负值存入。Java 的PriorityQueue默认是小顶堆可以通过 Comparator 自定义排序。7.3 双端队列与滑动窗口双端队列Deque允许两端入队和出队是栈和队列的超集。Python 的collections.deque就是双端队列。双端队列的经典应用是滑动窗口。除了前面提到的单调队列双端队列还可以用于实现“最近最少使用”LRU缓存。LRU 缓存需要快速访问、快速插入、快速删除双端队列配合哈希表可以在 O(1) 时间内完成所有操作。双端队列还可以用于实现工作窃取算法。每个线程有自己的双端队列任务从一端入队从另一端出队。当某个线程的队列为空时可以从其他线程的队列另一端“窃取”任务。这种设计在多线程任务调度中很常见。7.4 从数据结构到系统设计栈和队列的价值不仅在于它们是独立的数据结构更在于它们是系统设计的基本构件。一个消息队列系统核心就是队列但还需要考虑持久化、分区、副本、消费位点管理、消息确认、死信队列等。一个任务调度系统核心是优先队列但还需要考虑任务依赖、超时处理、重试策略、资源隔离等。一个撤销重做系统核心是栈但还需要考虑操作合并、历史记录限制、持久化等。理解栈和队列的原理是理解这些复杂系统的起点。但真正的工程能力在于知道什么时候用简单的结构什么时候需要引入复杂的机制。我在实际项目里踩过的最大的坑不是栈或队列本身写错了而是在不该用队列的地方用了队列。比如一个需要严格顺序的任务流我用了一个多消费者的队列结果任务执行顺序乱了。后来改成单消费者或者用分区保证顺序才解决问题。数据结构的选型本质上是对业务语义的理解。理解得越深选型越准。最后分享一个我常用的调试技巧当你怀疑栈或队列的状态不对时在每次操作后打印整个结构的内容和指针位置。虽然标准栈和队列不支持遍历但你可以在自己的实现里加一个__repr__方法输出内部数组和指针。这个简单的习惯帮我定位过很多边界条件的 bug。

栈与队列：从原理到手写实现，彻底搞懂LIFO和FIFO

相关推荐

气动力辨识的Observer法：从EKF状态空间建模到工程避坑

Spring Boot+元宇宙的房屋租赁管理系统毕业设计完整解析

Hive 3.1.2 UDF开发避坑指南：从环境配置到GenericUDF实践

更多资讯

如何快速上手tinynet_a.in1k：面向新手的3步图像分类完整指南

容器化迁移实战：从能跑到跑得漂亮的标准化与分层策略

基于 agentic-awesome-skills 的 templates 技能实战指南：13 种技术栈的项目脚手架模板与选择性读取机制

电脑跑 3DS 游戏最快路径：Citra 模拟器安装、调参与排错完整指南

AAS 技能深度解读：api-patterns 之 API 设计决策指南（REST / GraphQL / tRPC、响应、版本化、认证、限流与安全测试）

贾子猜想的伟大意义：从高维数论到人类认知边界的探索

今日更新

微信云开发旅游小程序实战：LBS打卡+UGC社交全栈方案

金融AI代理平台核心拆解：从多代理协作到财报分析实战

基于大数据的智慧旅游推荐与可视化平台架构实践

本周精选

金融AI落地指南：从调研报告到技术选型与工程实践

大模型上下文成本与注意力优化技术深度解析——为何O(n²)平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测

基于GMM的语音识别系统原理与MATLAB实现详解

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？