栈与队列：从线性结构到任务调度

摘要栈和队列是最基础、也最常用的线性数据结构。栈遵循“后进先出”适合表达撤销、括号匹配、递归调用和深度优先搜索队列遵循“先进先出”适合表达任务排队、广度优先搜索和生产者消费者模型。本文从栈与队列的基本操作开始介绍 Python 中的list、deque和queue并通过括号匹配、浏览器前进后退、任务队列和广度优先搜索示例理解它们的使用场景和复杂度。一、背景与问题很多业务逻辑都隐含“顺序规则”撤销操作总是撤销最近一次动作。浏览器后退总是回到上一个页面。排队取号要按先来后到处理。消息队列要按入队顺序消费。树或图的遍历需要管理待访问节点。如果只使用普通列表随意插入和删除很容易写出逻辑混乱或性能不佳的代码。栈和队列就是为这些顺序规则提供明确模型的数据结构。栈最近加入的元素最先被处理 队列最早加入的元素最先被处理清楚地选择栈或队列可以让代码表达业务顺序而不是依赖隐含约定。二、核心概念1. 栈栈是一种后进先出结构常用操作包括操作含义push入栈pop出栈peek查看栈顶元素is_empty判断是否为空栈可以用餐盘堆叠来理解最后放上去的盘子最先被拿走。2. 队列队列是一种先进先出结构常用操作包括操作含义enqueue入队dequeue出队front查看队首is_empty判断是否为空队列可以用排队买票来理解先排队的人先被服务。3. 双端队列双端队列允许从两端插入和删除。Python 的collections.deque提供高效的两端操作fromcollectionsimportdeque ddeque()d.append(1)d.appendleft(0)d.pop()d.popleft()当需要频繁从头部删除元素时deque通常比list.pop(0)更合适。4. 阻塞队列多线程任务处理中可以使用queue.Queue。它提供线程安全的入队和出队操作适合生产者-消费者模型。普通算法题通常使用deque并发任务通常使用queue.Queue。三、工作原理1. 栈的操作成本使用 Pythonlist尾部作为栈顶操作写法复杂度入栈append均摊O(1)出栈popO(1)查看栈顶stack[-1]O(1)不要使用列表头部作为栈顶因为头部插入和删除会移动元素。2. 队列的操作成本使用list.pop(0)出队需要移动后续元素复杂度为O(n)。使用deque.popleft()通常为O(1)。list: pop(0) 后后续元素整体前移 deque: popleft() 直接移除队首节点或块3. 顺序语义比实现更重要栈和队列的关键不是“底层怎么存”而是它们表达的访问顺序最近优先栈。最早优先队列。两端都需要操作双端队列。多线程协调线程安全队列。选错结构会让代码难读也会引发性能问题。四、实战示例1. 用列表实现栈classStack:def__init__(self)-None:self._items:list[int][]defpush(self,value:int)-None:self._items.append(value)defpop(self)-int:ifself.is_empty():raiseIndexError(pop from empty stack)returnself._items.pop()defpeek(self)-int:ifself.is_empty():raiseIndexError(peek from empty stack)returnself._items[-1]defis_empty(self)-bool:returnlen(self._items)0实际 Python 代码中不一定需要封装Stack类直接使用列表也可以。但封装有助于表达语义和控制边界。2. 括号匹配defis_valid_parentheses(text:str)-bool:pairs{):(,]:[,}:{,}stack:list[str][]forcharintext:ifcharin([{:stack.append(char)elifcharin)]}:ifnotstackorstack[-1]!pairs[char]:returnFalsestack.pop()returnnotstackprint(is_valid_parentheses(a[0] func(x)))print(is_valid_parentheses(([)]))括号匹配是典型的栈问题因为每个右括号都必须匹配最近的未闭合左括号。3. 浏览器前进后退classBrowserHistory:def__init__(self,home:str)-None:self.currenthome self.back_stack:list[str][]self.forward_stack:list[str][]defvisit(self,url:str)-None:self.back_stack.append(self.current)self.currenturl self.forward_stack.clear()defback(self)-str:ifself.back_stack:self.forward_stack.append(self.current)self.currentself.back_stack.pop()returnself.currentdefforward(self)-str:ifself.forward_stack:self.back_stack.append(self.current)self.currentself.forward_stack.pop()returnself.current后退栈和前进栈共同维护浏览历史。访问新页面后前进历史应被清空。4. 用deque实现队列fromcollectionsimportdequeclassQueue:def__init__(self)-None:self._items:deque[int]deque()defenqueue(self,value:int)-None:self._items.append(value)defdequeue(self)-int:ifself.is_empty():raiseIndexError(dequeue from empty queue)returnself._items.popleft()defis_empty(self)-bool:returnlen(self._items)0队列使用append入队使用popleft出队避免列表头部删除的移动成本。5. 任务调度队列fromcollectionsimportdeque tasksdeque([parse_file,clean_data,generate_report])whiletasks:tasktasks.popleft()print(running:,task)这里的任务按加入顺序执行符合先进先出FIFO的规则。6. 广度优先搜索fromcollectionsimportdequedefbfs(graph:dict[str,list[str]],start:str)-list[str]:visitedset([start])order:list[str][]queuedeque([start])whilequeue:nodequeue.popleft()order.append(node)forneighboringraph.get(node,[]):ifneighbornotinvisited:visited.add(neighbor)queue.append(neighbor)returnorder graph{A:[B,C],B:[D],C:[E],D:[],E:[],}print(bfs(graph,A))广度优先搜索使用队列保存待访问节点保证先发现的节点先被处理。7. 深度优先搜索defdfs_iterative(graph:dict[str,list[str]],start:str)-list[str]:visitedset()order:list[str][]stack[start]whilestack:nodestack.pop()ifnodeinvisited:continuevisited.add(node)order.append(node)forneighborinreversed(graph.get(node,[])):ifneighbornotinvisited:stack.append(neighbor)returnorder深度优先搜索可以用递归也可以显式使用栈。显式栈能避免递归深度限制。8. 生产者消费者模型fromqueueimportQueuefromthreadingimportThreaddefworker(queue:Queue[str])-None:whileTrue:taskqueue.get()try:iftaskSTOP:returnprint(processing:,task)finally:queue.task_done()task_queue:Queue[str]Queue()threadThread(targetworker,args(task_queue,))thread.start()task_queue.put(task-1)task_queue.put(task-2)task_queue.put(STOP)task_queue.join()thread.join()多线程中不要用普通列表手写共享队列。线程安全队列可以处理基本同步问题。五、常见问题与实践建议1. 为什么不建议用list.pop(0)做队列因为删除头部元素后后续元素需要整体前移数据量大时成本明显。队列场景优先使用deque.popleft()。2. 栈是否只能用来做算法题不是。撤销操作、表达式解析、调用栈、页面导航、状态回退都可以用栈模型表达。3. 队列是否一定先进先出普通队列是先进先出但还有优先队列、双端队列、延迟队列等变体。不同队列表达不同调度规则。4. 递归和栈有什么关系函数递归调用会使用调用栈保存执行状态。递归能写出简洁代码但深度过大时可能栈溢出。可以用显式栈改写递归。5. 什么时候使用queue.Queue当多个线程之间需要安全传递任务时使用。单线程算法中使用deque更轻量。六、进阶思考1. 单调栈单调栈用于维护递增或递减关系常见于“下一个更大元素”“柱状图最大矩形”等问题。它的特点是元素可能入栈一次、出栈一次因此整体复杂度通常为O(n)。2. 优先队列优先队列不是按进入时间处理而是按优先级处理。Python 中可以使用heapq实现最小堆importheapq tasks:list[tuple[int,str]][]heapq.heappush(tasks,(2,low))heapq.heappush(tasks,(1,high))print(heapq.heappop(tasks))优先队列适合任务调度、最短路径和 Top K 问题。3. 环形队列固定容量队列可以使用数组和头尾指针实现环形队列避免频繁移动元素。它常用于缓冲区、限流窗口和嵌入式场景。4. 边界条件实现栈和队列时至少测试空结构出栈或出队。只有一个元素。连续入队和出队。容量达到上限。多次交替操作。数据结构越基础越容易因为边界条件被忽略而出错。结论栈和队列是表达顺序规则的基础工具。栈适合最近优先的场景队列适合最早优先的场景deque适合高效两端操作queue.Queue适合多线程任务传递。掌握栈与队列后可以继续学习哈希表、递归、树和图。它们会在表达式解析、搜索算法、任务调度和系统设计中反复出现。参考资料Pythoncollections.deque文档https://docs.python.org/3/library/collections.html#collections.dequePythonqueue文档https://docs.python.org/3/library/queue.htmlPython 数据结构教程https://docs.python.org/3/tutorial/datastructures.html