Python数据结构进阶：栈与队列的实现与应用

Python数据结构进阶：栈与队列的实现与应用

---

一、栈（Stack） 1.1 定义与特性 后进先出（LIFO）原则： 最后添加的元素最先被移除 类比场景：网页浏览器的返回按钮、餐厅盘子叠放 1.2 核心操作 操作时间复杂度功能说明push()O(1)元素入栈pop()O(1)移除栈顶元素peek()O(1)查看栈顶元素is_empty()O(1)判断栈是否为空 1.3 典型应用场景

案例1：括号匹配验证 输入示例："([{}])" → 有效 错误示例："({[)]}" → 无效

案例2：逆波兰表达式求值 表达式：["4", "13", "5", "/", "+"] → 等价于 4 + (13 / 5)

---

二、队列（Queue） 2.1 定义与特性 先进先出（FIFO）原则： 最先添加的元素最先被移除 类比场景：超市结账排队、打印机任务队列 2.2 核心操作 操作时间复杂度功能说明enqueue()O(1)元素入队dequeue()O(1)移除队首元素front()O(1)查看队首元素is_empty()O(1)判断队列是否为空 2.3 典型应用场景

案例1：任务调度系统 处理顺序：请求1 → 请求2 → 请求3

案例2：广度优先搜索（BFS） 遍历顺序：层级1 → 层级2 → 层级3

---

三、Python实现代码 3.1 栈的实现（三种方式） # 方式1：使用列表实现 class ListStack: def __init__(self): self.items = [] def push(self, item): self.items.append(item) def pop(self): return self.items.pop() def peek(self): return self.items[-1] if not self.is_empty() else None def is_empty(self): return len(self.items) == 0 # 方式2：使用collections.deque from collections import deque class DequeStack: def __init__(self): self.container = deque() def push(self, val): self.container.append(val) def pop(self): return self.container.pop() def peek(self): return self.container[-1] if self.container else None # 方式3：自定义链表实现 class Node: def __init__(self, value): self.value = value self.next = None class LinkedListStack: def __init__(self): self.top = None def push(self, item): new_node = Node(item) new_node.next = self.top self.top = new_node def pop(self): if self.top is None: raise Exception("Stack is empty") value = self.top.value self.top = self.top.next return value 3.2 队列的实现（两种方式） # 方式1：使用deque双端队列 from collections import deque class ListQueue: def __init__(self): self.items = deque() def enqueue(self, item): self.items.append(item) def dequeue(self): return self.items.popleft() if self.items else None def front(self): return self.items[0] if self.items else None # 方式2：循环数组实现 class CircularQueue: def __init__(self, capacity): self.capacity = capacity self.queue = [None]*capacity self.head = 0 self.tail = 0 self.size = 0 def enqueue(self, item): if self.size == self.capacity: raise Exception("Queue is full") self.queue[self.tail] = item self.tail = (self.tail + 1) % self.capacity self.size += 1 def dequeue(self): if self.size == 0: return None item = self.queue[self.head] self.head = (self.head + 1) % self.capacity self.size -= 1 return item

---

四、每日挑战：括号匹配验证 4.1 问题描述

实现函数 is_valid_parentheses(s)：

输入示例： "()[]{}" → 返回True "([)]" → 返回False "({[]})" → 返回True 4.2 实现思路 创建空栈和映射表 {')': '(', ']': '[', '}': '{'}遍历每个字符： 左括号：入栈右括号：检查栈顶是否匹配 最后检查栈是否为空 4.3 参考答案 def is_valid_parentheses(s: str) -> bool: stack = [] mapping = {')': '(', ']': '[', '}': '{'} for char in s: if char in mapping.values(): stack.append(char) elif char in mapping.keys(): if not stack or stack[-1] != mapping[char]: return False stack.pop() return not stack

---

五、扩展练习 实现支持最小值查询的栈（要求所有操作O(1)时间复杂度）用队列实现栈的push/pop/top操作设计循环队列实现（参考Leetcode 622题）实现逆波兰表达式计算器（参考Leetcode 150题）

---

通过这个结构化的教程，学习者可以系统掌握栈和队列的核心概念，并通过代码实践和挑战题目深化理解。建议按照以下学习路径：

理解基本概念 → 2. 手写实现代码 → 3. 完成每日挑战 → 4. 尝试扩展练习