在学编程的过程中，你一定听过「数据结构」这个词。简单来说，数据结构就是组织和存储数据的方式。选对了数据结构，代码写起来轻松，运行效率也高。今天我们来聊三个最基础、面试也最爱问的数据结构：Stack（栈）、Queue（队列）和 Hash Table（哈希表）。都是 Python 里天天用到的东西，搞明白它们的原理和时间复杂度，对写代码帮助很大。
一、Stack（栈）
栈是一种 LIFO（Last In, First Out） 的数据结构，也就是「后进先出」。你可以把它想象成一摞盘子——最后放上去的盘子，是最先被拿走的。
基本操作
push：把元素压入栈顶，O(1)pop：弹出栈顶元素，O(1)peek / top：查看栈顶元素但不弹出，O(1)
Python 里没有专门的 Stack 类，直接用 list 就行：
# 用 Python list 实现栈
stack = []
# push - 压栈
stack.append(1)
stack.append(2)
stack.append(3)
print(stack) # [1, 2, 3]
# pop - 弹栈
top = stack.pop()
print(top) # 3
print(stack) # [1, 2]
# peek - 查看栈顶
print(stack[-1]) # 2如果追求更规范的写法，也可以用 collections.deque，性能更好一些：
from collections import deque
stack = deque()
stack.append(1)
stack.append(2)
stack.pop() # 2栈的应用场景
栈的应用非常广泛：
- 函数调用栈：程序运行时，每次函数调用都会在调用栈上压入一个 frame，返回时弹出。递归爆栈就是因为栈太深了。
- 括号匹配：判断
([{}])是否合法，经典栈题。 - 浏览器的后退功能：本质上就是一个栈。
- DFS（深度优先搜索）：递归版本隐式用栈，迭代版本显式用栈。
# 括号匹配 - LeetCode 20
def is_valid(s: str) -> bool:
stack = []
mapping = {')': '(', ']': '[', '}': '{'}
for char in s:
if char in mapping:
# 遇到右括号，检查栈顶
top = stack.pop() if stack else '#'
if mapping[char] != top:
return False
else:
# 左括号压栈
stack.append(char)
return len(stack) == 0
print(is_valid("([{}])")) # True
print(is_valid("([)]")) # False二、Queue（队列）
队列和栈相反，是一种 FIFO（First In, First Out） 的数据结构，即「先进先出」。就像排队买奶茶——先来的人先拿到奶茶。
基本操作
enqueue：从队尾入队，O(1)dequeue：从队头出队，O(1)peek：查看队头元素，O(1)
⚠️ 不要用 list 当队列！虽然 list.pop(0) 能出队，但它是 O(n) 操作，因为要移动所有元素。推荐用 collections.deque：
from collections import deque
queue = deque()
# enqueue - 入队
queue.append('A')
queue.append('B')
queue.append('C')
print(queue) # deque(['A', 'B', 'C'])
# dequeue - 出队
first = queue.popleft()
print(first) # 'A'
print(queue) # deque(['B', 'C'])队列的应用场景
- BFS（广度优先搜索）：层序遍历树、图的最短路径，核心就是队列。
- 任务调度：操作系统进程调度、消息队列（如 RabbitMQ、Kafka）。
- 缓存淘汰策略：LRU Cache 底层用的就是哈希表 + 双向链表（队列的变体）。
# BFS 示例：二叉树层序遍历
from collections import deque
def level_order(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return resultPriority Queue（优先队列）
普通队列按入队顺序出队，优先队列则按优先级出队。Python 里用 heapq 实现：
import heapq
pq = []
heapq.heappush(pq, 3)
heapq.heappush(pq, 1)
heapq.heappush(pq, 2)
print(heapq.heappop(pq)) # 1（最小的先出）
print(heapq.heappop(pq)) # 2三、Hash Table（哈希表）
哈希表可能是日常编程中用得最多的数据结构了。Python 的 dict 和 set 底层都是哈希表。它通过 hash function 把 key 映射到数组的某个位置，从而实现极快的查找。
时间复杂度
- 插入 / 删除 / 查找：平均 O(1)，最坏 O(n)（哈希冲突严重时退化）
- 空间复杂度：O(n)
用起来很简单，Python 的 dict 就是哈希表：
# Python dict 本质就是哈希表
student = {
'name': 'Alice',
'age': 20,
'gpa': 3.8
}
# 查找 - O(1)
print(student['name']) # 'Alice'
# 插入 - O(1)
student['major'] = 'CS'
# 删除 - O(1)
del student['gpa']
# 检查 key 是否存在 - O(1)
print('age' in student) # True哈希冲突（Collision）
不同的 key 经过 hash function 可能得到相同的 index，这就是 哈希冲突。常见的解决方法有两种：
- Chaining（链地址法）：每个 bucket 存一个链表，冲突的元素都挂在这个链表上。
- Open Addressing（开放寻址法）：冲突了就按某种规则探测下一个空位。
Python 的 dict 用的是开放寻址法的一种变体。
经典应用：Two Sum
哈希表最经典的面试题就是 Two Sum。暴力解法 O(n²)，用哈希表优化到 O(n)：
# LeetCode 1: Two Sum
def two_sum(nums: list, target: int) -> list:
seen = {} # val -> index
for i, num in enumerate(nums):
complement = target - num
if complement in seen: # O(1) 查找！
return [seen[complement], i]
seen[num] = i
return []
print(two_sum([2, 7, 11, 15], 9)) # [0, 1]Python dict 的内部机制
了解一些底层细节有助于理解性能。Python dict 从 3.6 开始是有序的（按插入顺序），底层用一个 dense array 存 key-value pairs，用一个 sparse array 存 hash indices。这样既省空间又保序。当 dict 的使用率超过 2/3 时会自动 resize。
四、三者对比总结
# 三种数据结构速查表
"""
数据结构 | 原理 | 插入 | 删除 | 查找 | Python 实现
---------|---------|--------|--------|--------|-------------
Stack | LIFO | O(1) | O(1) | O(n) | list / deque
Queue | FIFO | O(1) | O(1) | O(n) | deque
Hash Table| Hash映射| O(1)* | O(1)* | O(1)* | dict / set
* 平均情况，最坏 O(n)
"""数据结构的选择决定了算法的效率。写代码之前先想清楚：我的数据是先进后出还是先进先出？我需要快速查找吗？想明白了再选结构，事半功倍。
五、推荐练习
光看不练假把式，推荐几道经典 LeetCode 题目来巩固：
- 栈：#20 Valid Parentheses、#155 Min Stack、#84 Largest Rectangle in Histogram
- 队列：#102 Binary Tree Level Order Traversal、#622 Design Circular Queue
- 哈希表：#1 Two Sum、#49 Group Anagrams、#128 Longest Consecutive Sequence
这三个数据结构是后续学习 Tree、Graph、DP 的基础，务必打牢。下次我们来聊聊 Linked List 和 Binary Search Tree，敬请期待 🚀