栈与队列：数据结构基础与Python实现-北京尧图网络

1. 栈与队列的基本概念解析在计算机科学中栈Stack和队列Queue是两种最基础且应用广泛的数据结构。它们都属于线性表但在数据操作方式上有着本质区别。栈遵循后进先出LIFO原则就像我们叠放盘子最后放上去的盘子总是最先被取用而队列则遵循先进先出FIFO原则类似于排队购票先来的人先获得服务。栈的核心操作包括push入栈将元素添加到栈顶pop出栈移除并返回栈顶元素peek查看栈顶返回栈顶元素但不移除isEmpty判空检查栈是否为空队列的核心操作包括enqueue入队将元素添加到队尾dequeue出队移除并返回队首元素front查看队首返回队首元素但不移除isEmpty判空检查队列是否为空2. 栈的深度实现与应用场景2.1 栈的数组实现class ArrayStack: def __init__(self): self._data [] # 用列表存储栈元素 def __len__(self): return len(self._data) def is_empty(self): return len(self._data) 0 def push(self, e): self._data.append(e) # 新元素添加到列表末尾 def pop(self): if self.is_empty(): raise Empty(Stack is empty) return self._data.pop() # 移除并返回最后元素 def peek(self): if self.is_empty(): raise Empty(Stack is empty) return self._data[-1] # 返回最后元素但不移除注意在实际工程中当栈大小可能很大时需要考虑数组扩容的开销。Python的list已经做了优化但其他语言如Java的ArrayList需要手动处理。2.2 栈的链表实现class LinkedStack: class _Node: __slots__ _element, _next # 优化内存使用 def __init__(self, element, next): self._element element self._next next def __init__(self): self._head None self._size 0 def __len__(self): return self._size def is_empty(self): return self._size 0 def push(self, e): self._head self._Node(e, self._head) self._size 1 def pop(self): if self.is_empty(): raise Empty(Stack is empty) answer self._head._element self._head self._head._next self._size - 1 return answer def peek(self): if self.is_empty(): raise Empty(Stack is empty) return self._head._element2.3 栈的经典应用场景函数调用栈程序执行时每次函数调用都会在栈中创建一个栈帧存储局部变量和返回地址。递归函数本质上就是利用栈实现的。表达式求值编译器使用栈来处理运算符优先级例如中缀表达式转后缀表达式逆波兰表示法。括号匹配检查代码中的括号是否成对出现遇到左括号入栈右括号时出栈比对。浏览器历史记录浏览器的后退功能就是典型的栈应用每次访问新页面都会将当前URL压栈。撤销操作Undo文本编辑器中的撤销功能通常使用栈来保存操作历史。3. 队列的深度实现与变体3.1 队列的数组实现class ArrayQueue: DEFAULT_CAPACITY 10 # 初始容量 def __init__(self): self._data [None] * ArrayQueue.DEFAULT_CAPACITY self._size 0 self._front 0 # 队首索引 def __len__(self): return self._size def is_empty(self): return self._size 0 def first(self): if self.is_empty(): raise Empty(Queue is empty) return self._data[self._front] def dequeue(self): if self.is_empty(): raise Empty(Queue is empty) answer self._data[self._front] self._data[self._front] None # 帮助垃圾回收 self._front (self._front 1) % len(self._data) self._size - 1 return answer def enqueue(self, e): if self._size len(self._data): self._resize(2 * len(self._data)) # 扩容 avail (self._front self._size) % len(self._data) self._data[avail] e self._size 1 def _resize(self, cap): old self._data self._data [None] * cap walk self._front for k in range(self._size): self._data[k] old[walk] walk (1 walk) % len(old) self._front 0提示这种实现使用了循环数组来避免数据搬移当队尾到达数组末端时会绕回到数组开头。扩容策略是当数组满时将容量加倍。3.2 队列的链表实现class LinkedQueue: class _Node: __slots__ _element, _next def __init__(self, element, next): self._element element self._next next def __init__(self): self._head None self._tail None self._size 0 def __len__(self): return self._size def is_empty(self): return self._size 0 def first(self): if self.is_empty(): raise Empty(Queue is empty) return self._head._element def dequeue(self): if self.is_empty(): raise Empty(Queue is empty) answer self._head._element self._head self._head._next self._size - 1 if self.is_empty(): self._tail None return answer def enqueue(self, e): newest self._Node(e, None) if self.is_empty(): self._head newest else: self._tail._next newest self._tail newest self._size 13.3 队列的变体与应用双端队列Deque两端都可以进行插入和删除操作。Python中的collections.deque就是高效实现。优先队列Priority Queue元素带有优先级总是优先级最高的先出队。通常用堆实现。循环队列解决普通队列假溢出问题的实现方式也是大多数消息队列的底层实现。阻塞队列当队列空时获取操作会被阻塞队列满时插入操作会被阻塞。Java的BlockingQueue是典型实现。消息队列系统间异步通信的重要组件如RabbitMQ、Kafka等都是队列思想的延伸。4. 算法实战栈与队列的经典问题4.1 用栈实现队列class MyQueue: def __init__(self): self.stack1 [] # 主栈 self.stack2 [] # 辅助栈 def push(self, x): # 入队操作直接压入主栈 self.stack1.append(x) def pop(self): # 如果辅助栈为空将主栈元素全部倒入辅助栈 if not self.stack2: while self.stack1: self.stack2.append(self.stack1.pop()) return self.stack2.pop() def peek(self): if not self.stack2: while self.stack1: self.stack2.append(self.stack1.pop()) return self.stack2[-1] def empty(self): return not self.stack1 and not self.stack2时间复杂度分析push操作O(1)pop/peek操作摊还时间复杂度O(1)虽然有时需要O(n)时间倒栈但每个元素只会被倒一次4.2 用队列实现栈from collections import deque class MyStack: def __init__(self): self.queue deque() def push(self, x): # 入栈时先入队然后将前面的元素全部出队再入队 self.queue.append(x) for _ in range(len(self.queue) - 1): self.queue.append(self.queue.popleft()) def pop(self): return self.queue.popleft() def top(self): return self.queue[0] def empty(self): return not self.queue时间复杂度分析push操作O(n)pop/top操作O(1)4.3 最小栈问题设计一个支持push、pop、top操作并能在常数时间内检索到最小元素的栈。class MinStack: def __init__(self): self.stack [] self.min_stack [] # 辅助栈存储当前最小值 def push(self, x): self.stack.append(x) if not self.min_stack or x self.min_stack[-1]: self.min_stack.append(x) def pop(self): if self.stack.pop() self.min_stack[-1]: self.min_stack.pop() def top(self): return self.stack[-1] def getMin(self): return self.min_stack[-1]关键点使用辅助栈同步记录最小值。当主栈弹出元素等于辅助栈栈顶时辅助栈也弹出。4.4 滑动窗口最大值给定一个数组和滑动窗口的大小找出所有滑动窗口里的最大值。from collections import deque def maxSlidingWindow(nums, k): if not nums: return [] result [] window deque() # 存储的是索引 for i, num in enumerate(nums): # 移除窗口外的元素 if window and window[0] i - k: window.popleft() # 移除比当前元素小的元素保持队列递减 while window and nums[window[-1]] num: window.pop() window.append(i) # 当窗口形成后记录当前窗口最大值 if i k - 1: result.append(nums[window[0]]) return result时间复杂度O(n)每个元素最多被加入和移除队列各一次。5. 栈与队列在系统设计中的应用5.1 函数调用栈的实现细节函数调用栈是程序运行时的核心机制它存储了以下信息函数参数和局部变量返回地址调用者的栈帧指针临时计算结果当发生函数调用时参数按从右到左或特定约定压栈返回地址压栈跳转到函数入口函数内部保存调用者的栈帧指针为局部变量分配栈空间函数返回时返回值通常存放在特定寄存器(如EAX)或栈中指定位置恢复调用者的栈帧指针根据返回地址跳转调用者清理参数栈空间5.2 线程安全队列的实现多线程环境下队列需要保证线程安全。Python的queue模块提供了多种线程安全队列import queue import threading # 基本FIFO队列 q queue.Queue() # 生产者线程 def producer(): for i in range(5): q.put(i) print(fProduced {i}) time.sleep(0.1) # 消费者线程 def consumer(): while True: item q.get() if item is None: # 哨兵值结束信号 break print(fConsumed {item}) q.task_done() # 启动线程 prod_thread threading.Thread(targetproducer) cons_thread threading.Thread(targetconsumer) prod_thread.start() cons_thread.start() # 等待生产者完成 prod_thread.join() # 发送结束信号 q.put(None) cons_thread.join()关键点使用锁保护共享数据使用条件变量实现阻塞等待提供任务完成通知机制(task_done和join)支持优先级队列和LIFO队列变体5.3 消息队列的系统设计现代分布式系统中消息队列是解耦系统的关键组件。设计要点包括持久化消息需要持久化到磁盘防止丢失高可用通过主从复制或多副本保证可用性消息顺序保证分区内消息顺序消费确认消费者正确处理后才确认消息重试机制处理失败的消息需要重试或进入死信队列流量控制防止生产者压垮系统监控报警监控积压消息等关键指标以Kafka为例的核心概念Topic消息类别PartitionTopic的分区保证顺序性和并行处理Offset消息在分区中的唯一标识Consumer Group一组消费者共同消费一个Topic6. 性能优化与常见陷阱6.1 栈溢出与防范栈溢出通常发生在递归深度过大局部变量占用空间过大无限递归防范措施将递归算法改为迭代实现限制递归深度使用堆内存替代栈内存存储大数据尾递归优化部分语言支持# 危险的递归实现 def factorial(n): if n 1: return 1 return n * factorial(n-1) # 改进的迭代实现 def factorial_iter(n): result 1 for i in range(1, n1): result * i return result # 尾递归优化Python不支持仅为示例 def factorial_tail(n, acc1): if n 1: return acc return factorial_tail(n-1, acc*n)6.2 队列的假溢出问题数组实现的队列在频繁入队出队后可能出现数组前部空间无法利用的情况假溢出。解决方案循环队列将数组视为环形通过取模运算实现指针回绕动态扩容当队列满时自动扩容如Java的ArrayDeque链表实现彻底避免空间浪费6.3 内存访问局部性优化栈由于访问模式的特性总是访问栈顶具有极佳的内存局部性CPU缓存命中率高。而队列如果实现不当可能导致缓存命中率下降。优化建议数组实现的队列元素大小尽量是缓存行的整数倍避免队列节点分散在内存各处链表实现的缺点批量处理队列元素减少指针跳转6.4 并发环境下的ABA问题在使用CASCompare-And-Swap实现无锁队列时可能遇到ABA问题一个值从A变成B又变回ACAS无法察觉中间变化。解决方案使用带版本号的指针如Java的AtomicStampedReference使用垃圾回收语言避免内存重用采用危险指针等高级无锁技术7. 现代编程语言中的栈与队列7.1 Python中的实现Python标准库提供了多种栈和队列实现列表作为栈直接使用list的append和pop方法stack [] stack.append(1) # push stack.pop() # popcollections.deque高效的双端队列实现from collections import deque queue deque() queue.append(1) # enqueue queue.popleft() # dequeuequeue模块线程安全的队列实现import queue q queue.Queue() q.put(1) q.get()7.2 Java中的实现Java集合框架提供了丰富的栈和队列实现Stack类继承自Vector线程安全但性能较差StackInteger stack new Stack(); stack.push(1); stack.pop();Deque接口推荐替代StackDequeInteger stack new ArrayDeque(); stack.push(1); stack.pop();Queue接口QueueInteger queue new LinkedList(); queue.offer(1); // enqueue queue.poll(); // dequeue并发队列BlockingQueueInteger bq new LinkedBlockingQueue(); bq.put(1); bq.take();7.3 C中的实现C标准模板库(STL)提供了多种容器stack适配器#include stack std::stackint s; s.push(1); s.pop();queue适配器#include queue std::queueint q; q.push(1); q.pop();deque容器#include deque std::dequeint dq; dq.push_back(1); // enqueue dq.pop_front(); // dequeue dq.push_front(2); // 前端插入 dq.pop_back(); // 后端删除8. 进阶话题与扩展阅读8.1 单调栈与单调队列单调栈/队列是指栈/队列中的元素保持单调递增或递减的顺序常用于解决一些特定问题。单调栈应用下一个更大元素def nextGreaterElement(nums): result [-1] * len(nums) stack [] # 存储索引 for i in range(len(nums)): while stack and nums[i] nums[stack[-1]]: result[stack.pop()] nums[i] stack.append(i) return result单调队列应用滑动窗口最大值见4.4节8.2 持久化栈与队列持久化数据结构支持访问历史版本。实现方式路径复制修改时创建新节点共享未修改部分胖节点每个节点存储所有历史修改应用场景撤销操作、时间旅行调试等。8.3 函数式编程中的栈与队列在函数式语言中栈和队列通常实现为不可变数据结构-- Haskell中的栈操作 push :: a - [a] - [a] push x xs x:xs pop :: [a] - (a, [a]) pop (x:xs) (x, xs) -- 队列通常用两个栈实现 data Queue a Queue [a] [a] enqueue :: a - Queue a - Queue a enqueue x (Queue front back) Queue front (x:back) dequeue :: Queue a - (a, Queue a) dequeue (Queue [] back) dequeue (Queue (reverse back) []) dequeue (Queue (x:xs) back) (x, Queue xs back)8.4 硬件栈与调用约定在计算机体系结构中硬件栈是CPU直接支持的重要功能栈指针寄存器x86的ESP/RSPARM的SP栈操作指令PUSH/POPCALL/RET调用约定规定参数传递、寄存器保存等cdecl参数从右到左压栈调用者清理栈stdcall被调用者清理栈fastcall部分参数通过寄存器传递理解这些底层细节对于优化性能、调试问题非常重要。

栈与队列：数据结构基础与Python实现

相关推荐

分布式系统服务治理：核心原理与实践指南

vcruntime140_1.dll丢失怎么解决？运行库依赖原理与修复指南

vcruntime140_1.dll丢失报错？官方运行库安装与排查全攻略

更多资讯

RFID技术在信创资产管理中的应用与创新

SQL Server日志分析实战：从海量日志到故障定位的完整流程

Selenium自动化测试进阶：多浏览器并行与性能优化

AI Agent Harness 七个子系统：从能跑到能扛的工程实践

Jev 类型安全 SDK 实战：从安装配置到多模型调用的完整指南

Agent执行引擎的五大核心机制：上下文管理、检查点、任务恢复、循环执行与资源管控

今日更新

PLFM_RADAR：从被动告警到主动感知的微服务健康监控系统

SPI隔离设计实战：MAX14431BAEE+与STM32F407工业级应用

数字隔离器如何根治SPI通信地环路干扰：MAX14431与TM4C129实战

本周精选

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

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