1. 项目缘起为什么我们总在重复造轮子干了这么多年开发我发现一个挺有意思的现象无论是刚入行的新手还是有一定经验的工程师在面试或者做项目时一旦被问到“手写一个栈或者队列”总有人会卡壳。不是忘了处理边界条件就是性能设计上差点意思。更常见的是很多人对Python里list、collections.deque用得很溜但被问到“它们底层是怎么实现栈和队列操作的有什么坑”时就有点含糊其辞了。这其实不怪大家。Python的标准库太强大了list.append()和list.pop()用起来就像栈collections.deque的popleft()和append()用起来就像队列以至于我们很少需要从零开始实现它们。但正是这种“拿来就用”的便利让我们错过了理解数据结构精髓的机会。栈Stack的“后进先出”LIFO和队列Queue的“先进先出”FIFO这两个概念是构建更复杂系统比如函数调用栈、消息队列、DFS/BFS算法的基石。你不亲手用最基础的数组在Python里是列表和指针或索引把它们搭出来就很难真正体会“为什么在某些场景下数组实现队列效率低”或者“为什么栈特别适合做括号匹配和撤销操作”。所以这篇内容我想彻底抛开list当栈用的“捷径”也不用deque这个“外挂”就老老实实地从最底层的设计思想开始带你用Python把栈和队列“白手起家”地实现一遍。我会把每一步为什么这么做、可能会遇到什么坑、以及如何权衡不同实现方案的利弊都掰开揉碎了讲清楚。这不仅仅是应付面试更是为了让你在遇到需要定制化数据结构比如一个最大容量固定、满了要等待的阻塞队列或者一个需要支持遍历的栈的场景时心里有底手上有活儿。2. 栈Stack的精髓与两种底层实现抉择栈的核心操作就三个入栈push、出栈pop、查看栈顶peek/top。它的行为很像我们平时摞盘子你只能从最上面放一个新盘子push也只能从最上面拿走一个盘子pop。你想看看最上面是什么盘子但不能拿走peek。这个特性决定了它的底层存储和操作方式。在Python中最常见的想法就是用列表list来模拟。但这里有个关键选择我们把列表的哪一头当作栈顶这直接决定了操作的性能。2.1 方案一列表尾部作为栈顶推荐这是最高效的实现方式。因为Python的列表list是一个动态数组它在尾部进行追加append和删除pop操作的时间复杂度是O(1)即常数时间与列表长度无关。class StackUsingListTail: def __init__(self): 初始化一个空栈。内部使用一个列表来存储数据。 self._items [] # 使用一个下划线开头约定为“私有”变量提示不要直接访问 def push(self, item): 将元素item压入栈顶。 self._items.append(item) # O(1) 操作 def pop(self): 弹出并返回栈顶元素。如果栈为空则抛出IndexError。 if self.is_empty(): raise IndexError(Pop from an empty stack) return self._items.pop() # 默认弹出最后一个元素O(1)操作 def peek(self): 返回栈顶元素但不弹出。如果栈为空则抛出IndexError。 if self.is_empty(): raise IndexError(Peek from an empty stack) return self._items[-1] # 索引-1直接访问最后一个元素O(1)操作 def is_empty(self): 检查栈是否为空。 return len(self._items) 0 def size(self): 返回栈中元素的个数。 return len(self._items) def __str__(self): 返回栈的字符串表示从栈底到栈顶。 return fStack({self._items}) def __iter__(self): 使栈可迭代从栈底到栈顶。注意这不会弹出元素。 return iter(self._items)为什么这么设计性能考量append和pop()是Python列表优化得最好的操作。它们直接在内存中数组的末尾进行不需要移动其他元素。简洁性代码极其直观几乎就是对列表API的简单封装。实战心得在pop和peek操作前检查栈是否为空是一个非常好的习惯。这避免了list.pop()在空列表上调用时抛出不太友好的IndexError: pop from empty list我们可以抛出更语义化的异常或者在特定场景下返回一个默认值比如None。这在设计健壮的API时很重要。2.2 方案二列表头部作为栈顶不推荐但值得了解如果我们固执地要把列表开头索引0当作栈顶那么每次push对应list.insert(0, item)和pop对应list.pop(0)都需要移动列表中的所有后续元素时间复杂度是O(n)。这在数据量大时是灾难性的。class StackUsingListHead: def __init__(self): self._items [] def push(self, item): O(n)操作在列表头部插入元素需要移动所有现有元素。 self._items.insert(0, item) def pop(self): O(n)操作从列表头部弹出元素同样需要移动所有剩余元素。 if self.is_empty(): raise IndexError(Pop from an empty stack) return self._items.pop(0) # 注意是pop(0) def peek(self): if self.is_empty(): raise IndexError(Peek from an empty stack) return self._items[0] # 访问头部是O(1) # is_empty, size等方法同上对比与启示 通过这个对比你就能深刻理解“选择比努力更重要”在数据结构设计上的体现。同样是Python列表选错了操作端性能天差地别。这也解释了为什么在算法题里如果你需要频繁在序列两端进行增删collections.deque双端队列是比list更好的选择因为它的appendleft和popleft也是O(1)。注意在我们这个“白手起家”的实现里我们坚持用list来挑战。但在生产环境中如果你需要一个栈直接用list尾部作栈顶就是最佳实践。如果需要线程安全你可能需要考虑queue.LifoQueue。2.3 栈的实战应用场景与代码演练理解了实现我们得用起来。栈的经典应用场景能帮你巩固对它的理解。场景一括号匹配检查编译器、解释器和任何需要处理成对符号如(),[],{}的地方都会用到。思路是遍历字符串遇到左括号就入栈遇到右括号就检查栈顶是否是对应的左括号是则出栈否则不匹配。最后栈应为空。def is_valid_parentheses(s: str) - bool: stack StackUsingListTail() # 或者直接用 list: stack [] mapping {): (, ]: [, }: {} for char in s: if char in mapping.values(): # 左括号 stack.push(char) elif char in mapping.keys(): # 右括号 if stack.is_empty() or stack.pop() ! mapping[char]: return False # 其他字符忽略 return stack.is_empty() # 测试 print(is_valid_parentheses(()[]{})) # True print(is_valid_parentheses(([)])) # False场景二函数调用栈这是栈最本质的应用。每次调用函数系统会将当前函数的返回地址、局部变量等信息“压栈”函数返回时再“出栈”恢复之前的执行状态。我们可以用一个简单的栈来模拟这个过程class CallStackSimulator: def __init__(self): self.stack StackUsingListTail() self.current_func None def call_function(self, func_name): print(f调用函数: {func_name}) if self.current_func: self.stack.push(self.current_func) self.current_func func_name self.print_stack() def return_from_function(self): if self.stack.is_empty(): print(f函数 {self.current_func} 返回调用栈已清空。) self.current_func None else: returned_func self.current_func self.current_func self.stack.pop() print(f函数 {returned_func} 返回回到函数: {self.current_func}) self.print_stack() def print_stack(self): print(f当前调用栈 (栈底-栈顶): {list(self.stack._items)} 当前执行函数: {self.current_func}) # 模拟 A - B - C 的调用 sim CallStackSimulator() sim.call_function(main) sim.call_function(A) sim.call_function(B) sim.return_from_function() # B返回 sim.call_function(C) sim.return_from_function() # C返回 sim.return_from_function() # A返回 sim.return_from_function() # main返回通过这个模拟你能直观地看到栈是如何管理函数调用顺序的后调用的函数BC先返回。3. 队列Queue的实现挑战与环形数组方案队列就像现实中的排队先来的人先服务FIFO。核心操作是入队enqueue、出队dequeue、查看队首front/peek。用Python列表实现队列会遇到比栈更典型的性能问题。3.1 朴素列表实现的性能陷阱最直观的想法是用列表存储append入队pop(0)出队。class NaiveQueue: def __init__(self): self._items [] def enqueue(self, item): self._items.append(item) # O(1) def dequeue(self): if self.is_empty(): raise IndexError(Dequeue from an empty queue) return self._items.pop(0) # O(n) 问题在这里 def front(self): if self.is_empty(): raise IndexError(Front from an empty queue) return self._items[0] def is_empty(self): return len(self._items) 0 def size(self): return len(self._items)这个实现的dequeue是O(n)的因为pop(0)需要将后面所有的元素向前移动一位。对于需要高频出队的场景这是不可接受的。3.2 优化方案双指针与“环形”数组思想为了解决上述问题一个经典的思路是使用固定大小的数组列表并用两个指针或索引_front和_rear来分别标记队首和队尾的下一个位置即下一个元素该放的位置。当指针移动到数组末尾时让它绕回到开头形成一个逻辑上的“环形”这就是环形队列Circular Queue。设计细节与边界处理初始化创建一个固定长度的列表比如capacity_front和_rear都指向0。队列为空时_front _rear。入队将元素放到_rear指向的位置然后_rear (_rear 1) % capacity。取模运算%实现了“绕回”。出队取出_front指向位置的元素然后_front (_front 1) % capacity。队满判断这里有个小技巧。如果(_rear 1) % capacity _front我们就认为队列满了。这意味着我们有意浪费一个存储单元用来区分“队满”和“队空”两者都是_front _rear的情况。这是环形队列实现中一个非常关键且容易出错的点。class CircularQueue: def __init__(self, capacity10): 初始化一个固定容量的环形队列。 Args: capacity: 队列的容量。实际可用容量为 capacity-1。 self._capacity capacity 1 # 多分配一个单位用于区分空和满 self._items [None] * self._capacity self._front 0 # 指向队头元素 self._rear 0 # 指向队尾下一个空位置 def enqueue(self, item): 入队操作。如果队列已满则抛出异常。 if self.is_full(): raise Exception(CircularQueue is full) self._items[self._rear] item self._rear (self._rear 1) % self._capacity print(f入队: {item}, front{self._front}, rear{self._rear}) def dequeue(self): 出队操作。如果队列为空则抛出异常。 if self.is_empty(): raise Exception(CircularQueue is empty) item self._items[self._front] self._items[self._front] None # 可选帮助垃圾回收 self._front (self._front 1) % self._capacity print(f出队: {item}, front{self._front}, rear{self._rear}) return item def front(self): if self.is_empty(): raise Exception(CircularQueue is empty) return self._items[self._front] def is_empty(self): return self._front self._rear def is_full(self): return (self._rear 1) % self._capacity self._front def size(self): 计算队列中的元素数量。需要考虑绕回的情况。 return (self._rear - self._front self._capacity) % self._capacity def __str__(self): 可视化队列内容有助于调试。 if self.is_empty(): return CircularQueue: [] result [] i self._front while i ! self._rear: result.append(self._items[i]) i (i 1) % self._capacity return fCircularQueue: {result}为什么选择浪费一个单元这是为了判断逻辑的简洁和高效。判断(_rear 1) % capacity _front是一个O(1)的操作。如果不想浪费这个单元就需要引入一个额外的布尔变量_is_full来记录状态或者在_front _rear时通过遍历或计算size来区分是空还是满这都增加了复杂度。在内存不极度紧张的情况下浪费一个单元的代价是完全可以接受的。实战踩坑点初始化容量用户传入的capacity期望的是可用容量但我们内部需要capacity 1。这个1很容易被忘记导致逻辑错误。取模运算所有对_front和_rear的更新都必须记得取模% self._capacity这是实现“环形”的关键。size的计算不能简单地用rear - front因为可能rear比front小绕回了。公式(rear - front capacity) % capacity是标准解法务必理解其推导。3.3 动态扩容环形队列上面的环形队列是固定容量的这在很多场景下不够灵活。我们可以借鉴Python列表动态扩容的思路实现一个能自动扩容的环形队列。基本思路是当队列满时创建一个更大的新数组比如2倍大小然后将旧队列中的所有元素按顺序复制到新数组的开头并重置_front0,_rearsize。class DynamicCircularQueue: def __init__(self, initial_capacity10): self._capacity initial_capacity 1 self._items [None] * self._capacity self._front 0 self._rear 0 def enqueue(self, item): if self.is_full(): self._resize(2 * self._capacity) # 扩容为当前容量的2倍 self._items[self._rear] item self._rear (self._rear 1) % self._capacity def _resize(self, new_capacity): 将队列扩容或缩容到新的容量。 old_items self._items old_size self.size() # 新容量至少要比元素数量多1 new_capacity max(new_capacity, old_size 1) self._items [None] * new_capacity # 将旧队列的元素按顺序复制到新数组 for i in range(old_size): self._items[i] old_items[(self._front i) % len(old_items)] self._front 0 self._rear old_size self._capacity new_capacity print(f队列已扩容新容量: {self._capacity - 1}) def dequeue(self): if self.is_empty(): raise Exception(Queue is empty) item self._items[self._front] self._items[self._front] None self._front (self._front 1) % self._capacity # 可选当元素数量过少时缩容避免空间浪费。例如小于容量的1/4且容量大于初始容量时。 if 0 self.size() self._capacity // 4 and self._capacity 20: self._resize(self._capacity // 2) return item # 其他方法 is_empty, is_full, front, size 与 CircularQueue 相同这个动态版本更接近实用的数据结构。它平衡了时间和空间效率大部分enqueue和dequeue操作仍是O(1)的只有在触发_resize时是O(n)。这种“均摊分析”下每个操作的平均时间复杂度仍然是O(1)。4. 双端队列Deque与优先队列Priority Queue的扩展思考掌握了基础的栈和队列我们可以看看它们的两个重要变种这能极大拓展你解决问题的工具箱。4.1 双端队列Deque栈和队列的合体双端队列允许在两端进行高效的插入和删除。它兼具栈和队列的能力。用我们已有的知识你可以尝试基于两个栈或者一个双向链表来实现它。但Python的collections.deque是基于双向链表实现的在两端操作都是O(1)是处理滑动窗口、撤销历史等问题的利器。这里我们可以基于两个栈模拟一个双端队列虽然效率不是最优但有助于理解一个栈负责前端操作一个栈负责后端操作。当从一个栈pop为空时将另一个栈的所有元素“倒”过来。class DequeUsingStacks: 使用两个栈模拟双端队列。注意部分操作在最坏情况下是O(n)。 def __init__(self): self._front_stack [] # 栈顶对应双端队列的头部 self._back_stack [] # 栈顶对应双端队列的尾部 def push_front(self, item): 在头部添加元素。 self._front_stack.append(item) def push_back(self, item): 在尾部添加元素。 self._back_stack.append(item) def pop_front(self): 从头部弹出元素。 if not self._front_stack: # 如果前栈为空将后栈的所有元素倒入前栈顺序会反转 while self._back_stack: self._front_stack.append(self._back_stack.pop()) if not self._front_stack: raise IndexError(Pop front from an empty deque) return self._front_stack.pop() def pop_back(self): 从尾部弹出元素。 if not self._back_stack: while self._front_stack: self._back_stack.append(self._front_stack.pop()) if not self._back_stack: raise IndexError(Pop back from an empty deque) return self._back_stack.pop()这个实现揭示了双端队列的一种可能内部机制也展示了“摊还分析”的概念虽然pop_front和pop_back在某些时候需要O(n)的时间来“倒栈”但每个元素最多被倒入和倒出一次所以平均下来每个操作还是O(1)。4.2 优先队列Priority Queue谁重要谁先出普通队列是先进先出优先队列则是“优先级高者先出”。它通常使用二叉堆Binary Heap这种数据结构来实现以保证入队和出队操作都能在O(log n)时间内完成。Python的heapq模块提供了基于列表的最小堆实现。我们可以用列表模拟一个最小堆来实现一个简单的优先队列import heapq class PriorityQueue: def __init__(self): self._heap [] self._index 0 # 用于处理优先级相同时的比较 def push(self, item, priority): 将元素按优先级入队。 注意heapq实现的是最小堆所以优先级数值小的先出队。 如果想实现最大堆可以将优先级取负数存入。 # 存入一个三元组 (priority, index, item) # index用于当priority相同时按插入顺序决定保证稳定性 heapq.heappush(self._heap, (priority, self._index, item)) self._index 1 def pop(self): 弹出优先级最高的元素优先级值最小的。 if self.is_empty(): raise IndexError(Pop from an empty priority queue) priority, index, item heapq.heappop(self._heap) return item def is_empty(self): return len(self._heap) 0关键点heapq只保证堆顶是最小元素。我们存入(priority, index, item)元组Python会比较元组的第一个元素优先级如果相同再比较第二个索引这确保了同优先级元素的先进先出顺序稳定性。如果你需要最大优先队列一个常用技巧是存入(-priority, index, item)。优先队列的应用极其广泛从操作系统的进程调度、网络带宽管理到算法中的Dijkstra最短路径算法、Huffman编码、定时任务调度都离不开它。5. 从实现到应用算法实战与性能对比纸上得来终觉浅绝知此事要躬行。最后我们通过两个经典的算法问题来综合运用栈和队列并直观感受不同实现带来的性能差异。5.1 使用栈实现队列使用队列实现栈这是一类经典的面试题考验你对这两种数据结构本质的理解。题目一用栈实现队列思路需要两个栈一个stack_in专门负责入队一个stack_out专门负责出队。入队时直接压入stack_in。出队时如果stack_out为空则将stack_in中的所有元素依次弹出并压入stack_out这样stack_out的栈顶就是最早进入stack_in的元素即队首然后从stack_out弹出即可。class QueueUsingStacks: def __init__(self): self._stack_in [] self._stack_out [] def enqueue(self, x): self._stack_in.append(x) def dequeue(self): if self.empty(): raise Exception(Queue is empty) if not self._stack_out: # 将输入栈的元素全部倒入输出栈 while self._stack_in: self._stack_out.append(self._stack_in.pop()) return self._stack_out.pop() def front(self): if self.empty(): raise Exception(Queue is empty) if not self._stack_out: while self._stack_in: self._stack_out.append(self._stack_in.pop()) return self._stack_out[-1] def empty(self): return not self._stack_in and not self._stack_out复杂度分析每个元素最多经历两次入栈和两次出栈从stack_in到stack_out一次从stack_out弹出一次所以enqueue是O(1)dequeue和front的均摊时间复杂度也是O(1)。题目二用队列实现栈思路可以用一个队列来模拟。入栈时将新元素入队然后将队列中除了这个新元素之外的所有元素依次出队再入队。这样新元素就被移动到了队列的头部相当于栈顶。from collections import deque class StackUsingQueue: def __init__(self): self._q deque() def push(self, x): self._q.append(x) # 将新元素之前的元素全部移到它后面 for _ in range(len(self._q) - 1): self._q.append(self._q.popleft()) def pop(self): if self.empty(): raise Exception(Stack is empty) return self._q.popleft() # 因为push操作后队首就是栈顶 def top(self): if self.empty(): raise Exception(Stack is empty) return self._q[0] def empty(self): return len(self._q) 0复杂度分析push操作是O(n)因为需要移动n-1个元素pop和top是O(1)。这是用时间换空间的思路。5.2 性能压测不同实现的效率差距理论分析很重要但实际跑一下数据更直观。我们来对比一下几种队列实现的出队操作性能。import time from collections import deque def test_queue_performance(queue_class, enqueue_list, dequeue_times): 测试队列实现的性能 q queue_class() start time.perf_counter() # 入队 for item in enqueue_list: q.enqueue(item) # 出队 for _ in range(dequeue_times): q.dequeue() end time.perf_counter() return end - start # 准备测试数据 test_size 10000 data list(range(test_size)) # 测试不同的队列 print(f测试数据量: {test_size}) print(- * 50) # 1. 朴素队列 (pop(0)是O(n)) try: # 注意NaiveQueue的dequeue是O(n)测试全部出队会很慢这里只测试一部分 partial_dequeue 1000 t test_queue_performance(NaiveQueue, data[:partial_dequeue*2], partial_dequeue) print(fNaiveQueue (出队{partial_dequeue}次): {t:.4f} 秒) except Exception as e: print(fNaiveQueue 测试出错: {e}) # 2. 环形队列 (固定容量需确保容量足够) circular_capacity test_size 1 class FixedCircularQueue: # 简单包装一下传入容量 def __init__(self): self._q CircularQueue(capacitytest_size) def enqueue(self, item): self._q.enqueue(item) def dequeue(self): return self._q.dequeue() t test_queue_performance(FixedCircularQueue, data, test_size) print(fCircularQueue (固定容量): {t:.4f} 秒) # 3. 动态环形队列 t test_queue_performance(DynamicCircularQueue, data, test_size) print(fDynamicCircularQueue: {t:.4f} 秒) # 4. Python标准库的deque (作为基准) class DequeWrapper: def __init__(self): self._q deque() def enqueue(self, item): self._q.append(item) def dequeue(self): return self._q.popleft() t test_queue_performance(DequeWrapper, data, test_size) print(fcollections.deque (基准): {t:.4f} 秒)运行这段代码你会清晰地看到NaiveQueue在数据量大时慢得惊人而CircularQueue和DynamicCircularQueue的表现与高度优化的deque处于同一数量级。这就是理解底层实现价值的最有力证明一个糟糕的实现pop(0)足以毁掉整个系统的吞吐量。6. 总结与个人踩坑心得走完这一趟从零实现栈和队列的旅程我希望你收获的不仅仅是几段可以运行的Python代码。更重要的是理解这些简单数据结构背后的设计哲学、性能权衡和适用场景。几个我踩过或者见别人踩过的坑值得你特别注意list当作栈用一定要用尾部操作这是老生常谈但永远有人犯的错误。记住stack.append(x)和stack.pop()是黄金搭档。如果你看到代码里用insert(0, x)和pop(0)来模拟栈性能警报就应该拉响。环形队列的“满”和“空”判断这是我初学数据结构时最迷糊的地方。记住那个“浪费一个单元”的判满公式(rear 1) % capacity front并理解为什么要这么做。自己画图跟着指针走几遍比死记硬背强十倍。动态扩容的触发时机和缩容策略像DynamicCircularQueue那样扩容通常选择翻倍2倍这是一个经验值能在空间和时间之间取得较好的平衡。缩容则要谨慎避免在容量边界频繁扩容缩容“抖动”。通常选择当元素数量降到容量的1/4以下时才缩容到1/2并且设置一个最小容量阈值。优先队列的优先级定义使用heapq时存入堆中的元素必须是可比较的。对于自定义对象你需要实现__lt__方法或者像我们例子中那样存入(priority, item)元组。另外heapq是最小堆要实现最大堆存入(-priority, item)是标准技巧。线程安全不是免费的我们上面实现的所有结构都不是线程安全的。如果需要在多线程环境下使用栈或队列不要自己用list或deque加锁直接使用queue模块提供的Queue、LifoQueue或PriorityQueue它们是经过充分测试的线程安全实现。最后数据结构的学习动手实现一遍是最好的方式。它让你摆脱了“黑盒”魔法真正理解了工具的原理和边界。下次当你使用list、deque或者heapq时你脑子里浮现的将不再是模糊的API而是清晰的指针移动、数组扩容和堆调整的画面。这种掌控感才是我们不断深入底层细节的意义所在。