从栈、队列到二叉树遍历：5 种数据结构在 Python 3.12 中的实现与复杂度对比

从栈、队列到二叉树遍历5 种数据结构在 Python 3.12 中的实现与复杂度对比当我们需要在程序中高效地组织和管理数据时数据结构的选择往往决定了程序的性能和可维护性。作为计算机科学的核心基础数据结构不仅是理论研究的对象更是解决实际问题的利器。本文将聚焦五种最常用的数据结构——栈、队列、线性表、二叉树以及查找排序算法通过 Python 3.12 的代码实现带你从理论走向实践并深入分析它们的时间与空间复杂度。1. 栈Stack后进先出的数据管理栈是一种遵循**后进先出LIFO**原则的线性数据结构就像一摞盘子你只能从最上面取放。这种特性使得栈在函数调用、表达式求值和浏览器历史记录等场景中表现出色。1.1 Python 实现栈的三种方式在 Python 中我们可以用多种方式实现栈# 方式1使用列表实现适合小型应用 stack [] stack.append(A) # 入栈 stack.append(B) top_element stack.pop() # 出栈返回B # 方式2使用collections.deque线程安全适合高频操作 from collections import deque stack deque() stack.append(C) stack.append(D) stack.pop() # 返回D # 方式3自定义栈类推荐生产环境使用 class Stack: def __init__(self): self._items [] def push(self, item): self._items.append(item) def pop(self): if not self.is_empty(): return self._items.pop() raise IndexError(pop from empty stack) def peek(self): return self._items[-1] if self._items else None def is_empty(self): return len(self._items) 0 def size(self): return len(self._items)1.2 栈的操作复杂度分析操作时间复杂度空间复杂度说明push()O(1)O(1)追加到末尾无需数据移动pop()O(1)O(1)从末尾移除操作高效peek()O(1)O(1)仅访问不修改is_empty()O(1)O(1)检查长度是否为0提示虽然列表的append和pop操作在平均情况下是O(1)但在列表空间不足时可能需要重新分配内存导致最坏情况下时间复杂度为O(n)。对于性能敏感场景建议使用deque。2. 队列Queue先进先出的有序处理队列遵循**先进先出FIFO**原则就像排队买票先来的人先得到服务。这种特性使队列在任务调度、消息传递等场景中不可或缺。2.1 Python 实现队列的最佳实践# 方式1使用collections.deque推荐标准实现 from collections import deque queue deque() queue.append(A) # 入队 queue.append(B) first_item queue.popleft() # 出队返回A # 方式2使用queue.Queue线程安全版本 from queue import Queue q Queue(maxsize3) q.put(X) # 阻塞式入队 q.put(Y) q.get() # 返回X # 方式3自定义循环队列解决假溢出问题 class CircularQueue: def __init__(self, capacity): self.capacity capacity 1 # 留一个空位区分满/空 self.queue [None] * self.capacity self.front 0 self.rear 0 def enqueue(self, item): if self.is_full(): raise Exception(Queue is full) self.queue[self.rear] item self.rear (self.rear 1) % self.capacity def dequeue(self): if self.is_empty(): raise Exception(Queue is empty) item self.queue[self.front] self.front (self.front 1) % self.capacity return item def is_empty(self): return self.front self.rear def is_full(self): return (self.rear 1) % self.capacity self.front2.2 队列操作复杂度对比类型入队时间复杂度出队时间复杂度空间复杂度适用场景普通队列O(1)O(1)O(n)一般应用循环队列O(1)O(1)O(n)固定大小缓冲区优先队列O(log n)O(log n)O(n)任务调度双端队列O(1)O(1)O(n)滑动窗口算法3. 线性表顺序与链式存储的博弈线性表是最基础的数据结构分为顺序存储数组和链式存储链表两种实现方式各有优劣。3.1 顺序表数组实现class ArrayList: def __init__(self): self._items [] self._size 0 def insert(self, index, item): if index 0 or index self._size: raise IndexError(list index out of range) self._items.insert(index, item) self._size 1 def remove(self, item): try: self._items.remove(item) self._size - 1 except ValueError: return False return True def __getitem__(self, index): return self._items[index] def __len__(self): return self._size3.2 链表实现及变体class ListNode: def __init__(self, val0, nextNone): self.val val self.next next class LinkedList: def __init__(self): self.head None self.size 0 def add_at_head(self, val): new_node ListNode(val) new_node.next self.head self.head new_node self.size 1 def add_at_tail(self, val): new_node ListNode(val) if not self.head: self.head new_node else: current self.head while current.next: current current.next current.next new_node self.size 1 def delete_node(self, val): dummy ListNode(0) dummy.next self.head prev, current dummy, self.head while current: if current.val val: prev.next current.next self.size - 1 return True prev, current current, current.next return False3.3 复杂度对比表操作顺序表单链表双向链表说明随机访问O(1)O(n)O(n)数组优势明显头部插入/删除O(n)O(1)O(1)链表更高效尾部插入/删除O(1)O(n)O(1)双向链表优化尾部操作中间插入/删除O(n)O(n)O(n)链表只需修改指针空间占用更少更多最多数组无指针开销4. 二叉树层次化数据组织的艺术二叉树是每个节点最多有两个子节点的树结构在搜索、排序和数据库索引等领域有广泛应用。4.1 二叉树的基本实现class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right class BinaryTree: def __init__(self, rootNone): self.root root def insert(self, val): if not self.root: self.root TreeNode(val) return queue [self.root] while queue: node queue.pop(0) if not node.left: node.left TreeNode(val) return else: queue.append(node.left) if not node.right: node.right TreeNode(val) return else: queue.append(node.right)4.2 二叉树的三种遍历方式def preorder(root): 前序遍历根-左-右 return [root.val] preorder(root.left) preorder(root.right) if root else [] def inorder(root): 中序遍历左-根-右 return inorder(root.left) [root.val] inorder(root.right) if root else [] def postorder(root): 后序遍历左-右-根 return postorder(root.left) postorder(root.right) [root.val] if root else [] # 迭代式实现避免递归栈溢出 def inorder_iterative(root): stack, result [], [] current root while current or stack: while current: stack.append(current) current current.left current stack.pop() result.append(current.val) current current.right return result4.3 二叉树操作复杂度分析操作时间复杂度空间复杂度说明插入O(n)O(n)最坏情况需要遍历所有节点查找O(n)O(n)普通二叉树无优化遍历O(n)O(n)必须访问每个节点平衡二叉树查找O(log n)O(log n)保持平衡时效率显著提升5. 查找与排序数据处理的基石高效的查找和排序算法是处理大规模数据的关键不同场景需要选择不同策略。5.1 二分查找实现def binary_search(arr, target): left, right 0, len(arr) - 1 while left right: mid left (right - left) // 2 if arr[mid] target: return mid elif arr[mid] target: left mid 1 else: right mid - 1 return -1 # Python内置的bisect模块 import bisect sorted_list [1, 3, 4, 4, 6, 8] bisect.bisect_left(sorted_list, 4) # 返回2第一个等于4的位置5.2 快速排序实现def quicksort(arr): if len(arr) 1: return arr pivot arr[len(arr) // 2] left [x for x in arr if x pivot] middle [x for x in arr if x pivot] right [x for x in arr if x pivot] return quicksort(left) middle quicksort(right) # 原地排序版本节省空间 def quicksort_inplace(arr, low0, highNone): if high is None: high len(arr) - 1 if low high: pi partition(arr, low, high) quicksort_inplace(arr, low, pi - 1) quicksort_inplace(arr, pi 1, high) def partition(arr, low, high): pivot arr[high] i low - 1 for j in range(low, high): if arr[j] pivot: i 1 arr[i], arr[j] arr[j], arr[i] arr[i 1], arr[high] arr[high], arr[i 1] return i 15.3 算法复杂度对比表算法平均时间复杂度最坏时间复杂度空间复杂度稳定性适用场景顺序查找O(n)O(n)O(1)-无序数据二分查找O(log n)O(log n)O(1)-已排序数组快速排序O(n log n)O(n²)O(log n)不稳定通用排序大数据量归并排序O(n log n)O(n log n)O(n)稳定需要稳定排序堆排序O(n log n)O(n log n)O(1)不稳定原地排序空间受限在实际项目中数据结构的选择往往需要权衡多种因素。比如内存有限的嵌入式系统可能优先考虑空间效率而高频交易系统则更关注时间效率。Python 的标准库已经提供了许多优化过的数据结构实现但在特殊场景下自定义实现可能更能满足特定需求。