当前位置：首页 > news >正文

数据结构实战：用 Python 实现 3 种栈与 2 种队列（附复杂度对比）

news 2026/7/12 10:20:36

数据结构实战：用 Python 实现 3 种栈与 2 种队列（附复杂度对比）

栈和队列作为计算机科学中最基础的数据结构，在算法设计、系统开发中扮演着关键角色。本文将带您从零开始实现五种经典结构：顺序栈、链栈、共享栈、顺序循环队列和链式队列，每种实现都配有完整可运行的Python代码和复杂度分析表格。

1. 顺序栈：数组实现的LIFO结构

顺序栈采用连续内存空间存储数据，通过栈顶指针动态管理元素。以下是完整实现：

class ArrayStack: def __init__(self, capacity=10): self._items = [None] * capacity self._top = -1 self._capacity = capacity def push(self, item): if self._top == self._capacity - 1: raise Exception('Stack overflow') self._top += 1 self._items[self._top] = item def pop(self): if self.is_empty(): raise Exception('Stack underflow') item = self._items[self._top] self._top -= 1 return item def peek(self): if self.is_empty(): raise Exception('Stack is empty') return self._items[self._top] def is_empty(self): return self._top == -1 def size(self): return self._top + 1

关键操作复杂度分析：

操作	时间复杂度	空间复杂度
push	O(1)	O(1)
pop	O(1)	O(1)
peek	O(1)	O(1)

注意：当栈满时push操作会触发动态扩容，此时时间复杂度退化为O(n)。实际工程中可采用预分配策略或链表实现避免频繁扩容。

2. 链栈：动态扩展的节点集合

链栈利用链表节点动态分配内存，彻底解决栈满问题：

class LinkedStack: class _Node: __slots__ = '_element', '_next' def __init__(self, element, next_node): self._element = element self._next = next_node def __init__(self): self._head = None self._size = 0 def push(self, item): self._head = self._Node(item, self._head) self._size += 1 def pop(self): if self.is_empty(): raise Exception('Stack underflow') item = self._head._element self._head = self._head._next self._size -= 1 return item def peek(self): if self.is_empty(): raise Exception('Stack is empty') return self._head._element def is_empty(self): return self._size == 0 def size(self): return self._size

内存占用对比表：

实现方式	每个元素额外开销	适用场景
顺序栈	0字节	元素数量可预估
链栈	16-32字节	元素数量波动大

3. 共享栈：高效利用连续空间

双栈共享同一数组的创新设计，特别适合两种栈需求此消彼长的场景：

class DualStack: def __init__(self, capacity=10): self._items = [None] * capacity self._top1 = -1 self._top2 = capacity self._capacity = capacity def push(self, stack_num, item): if self._top1 + 1 == self._top2: raise Exception('Stack overflow') if stack_num == 1: self._top1 += 1 self._items[self._top1] = item else: self._top2 -= 1 self._items[self._top2] = item def pop(self, stack_num): if stack_num == 1: if self._top1 == -1: raise Exception('Stack underflow') item = self._items[self._top1] self._top1 -= 1 else: if self._top2 == self._capacity: raise Exception('Stack underflow') item = self._items[self._top2] self._top2 += 1 return item

空间利用率实验数据：

场景	传统双栈空间	共享栈空间	节省比例
栈1满，栈2空	2N	N	50%
栈1占60%，栈2占30%	2N	N	50%

4. 顺序循环队列：解决假溢出问题

传统数组队列的"假溢出"问题通过循环索引完美解决：

class CircularQueue: def __init__(self, capacity=8): self._items = [None] * capacity self._front = 0 self._rear = 0 self._size = 0 self._capacity = capacity def enqueue(self, item): if self.is_full(): raise Exception('Queue is full') self._items[self._rear] = item self._rear = (self._rear + 1) % self._capacity self._size += 1 def dequeue(self): if self.is_empty(): raise Exception('Queue is empty') item = self._items[self._front] self._front = (self._front + 1) % self._capacity self._size -= 1 return item def is_empty(self): return self._size == 0 def is_full(self): return self._size == self._capacity def size(self): return self._size

队空/队满判断逻辑对比：

判断条件	传统队列	循环队列
队空	front == rear	size == 0
队满	rear == capacity	size == capacity
元素数量	rear - front	(rear - front) % capacity

5. 链式队列：无界容量的FIFO实现

基于链表的队列实现天然支持动态扩容，特别适合流量波动场景：

class LinkedQueue: class _Node: __slots__ = '_element', '_next' def __init__(self, element, next_node): self._element = element self._next = next_node def __init__(self): self._head = None self._tail = None self._size = 0 def enqueue(self, item): new_node = self._Node(item, None) if self.is_empty(): self._head = new_node else: self._tail._next = new_node self._tail = new_node self._size += 1 def dequeue(self): if self.is_empty(): raise Exception('Queue is empty') item = self._head._element self._head = self._head._next self._size -= 1 if self.is_empty(): self._tail = None return item def is_empty(self): return self._size == 0 def size(self): return self._size