使用列表实现栈高效，因append和pop操作均为O(1)；但用列表实现队列时，pop(0)为O(n)，性能差。应使用collections.deque实现队列，因其popleft为O(1)。封装类可提供更清晰接口和错误处理，适用于复杂场景。频繁出队或大数据量时优选deque，简单栈操作可选list。
在Python中实现栈（Stack）和队列（Queue）有几种常见且有效的方法，最直接的方式是利用Python内置的列表（list）或
collections
模块中的
deque
（双端队列）。这两种数据结构本身就具备了实现栈和队列所需的基本操作，只是在性能表现上各有侧重。
解决方案
实现栈（LIFO，后进先出）和队列（FIFO，先进先出）的核心在于控制元素的添加和移除顺序。
1. 使用Python列表实现栈
Python的
list
天生就非常适合作为栈。
append()
方法可以将元素添加到列表的末尾，而
pop()
方法则默认从列表末尾移除元素。这完美符合栈的LIFO特性。
立即学习“Python免费学习笔记（深入）”；
# 栈的实现示例stack = []# 入栈 (Push)stack.append('A')stack.append('B')stack.append('C')print(f"入栈后: {stack}") # 输出: ['A', 'B', 'C']# 出栈 (Pop)item_c = stack.pop()print(f"出栈 {item_c} 后: {stack}") # 输出: ['A', 'B']item_b = stack.pop()print(f"出栈 {item_b} 后: {stack}") # 输出: ['A']# 查看栈顶元素 (Peek)if stack: print(f"栈顶元素: {stack[-1]}") # 输出: 'A'# 检查栈是否为空print(f"栈是否为空: {not stack}") # 输出: False
2. 使用
collections.deque
实现队列
虽然列表也可以实现队列，但它在从列表头部移除元素时效率较低（
list.pop(0)
是O(n)操作）。这时，
collections.deque
（双端队列）就显得尤为出色了。
deque
支持在两端高效地添加和移除元素，其性能是O(1)。
from collections import deque# 队列的实现示例queue = deque()# 入队 (Enqueue)queue.append('Task1')queue.append('Task2')queue.append('Task3')print(f"入队后: {queue}") # 输出: deque(['Task1', 'Task2', 'Task3'])# 出队 (Dequeue)task1 = queue.popleft() # 从左端移除print(f"出队 {task1} 后: {queue}") # 输出: deque(['Task2', 'Task3'])task2 = queue.popleft()print(f"出队 {task2} 后: {queue}") # 输出: deque(['Task3'])# 查看队首元素 (Peek)if queue: print(f"队首元素: {queue[0]}") # 输出: 'Task3'# 检查队列是否为空print(f"队列是否为空: {not queue}") # 输出: False
Python内置列表作为栈和队列的性能瓶颈是什么？
说实话，用Python的内置
list
来模拟栈，也就是只用
append()
和
pop()
操作，效率是相当高的，这两种操作的时间复杂度都是O(1)。这意味着无论栈里有多少元素，添加或移除一个元素所需的时间基本是恒定的。所以，对于栈来说，
list
几乎没有性能瓶颈，非常适合。
但当
list
被用作队列时，情况就有点不一样了。队列的特性是先进先出，这意味着我们需要从列表的“头部”移除元素。如果你用
list.pop(0)
来模拟出队操作，那问题就来了。
pop(0)
这个操作，每次都会把列表中所有剩余的元素向前移动一位，以填补被移除元素留下的空位。想象一下，如果你的列表里有几百万个元素，每次出队都要移动几百万个元素，这无疑是个巨大的开销。它的时间复杂度是O(n)，n是列表中元素的数量。随着队列的增长，性能会急剧下降，这在处理大量数据或高并发场景下是完全不可接受的。我个人就遇到过一些老项目，为了方便直接用
list.pop(0)
做队列，结果在生产环境跑起来就发现CPU占用居高不下，一查才发现是这里出了问题。所以，对于队列操作，尤其是频繁出队的情况，我强烈建议避免使用
list.pop(0)
。
除了内置类型，如何用类封装栈和队列，实现更清晰的接口和错误处理？
虽然直接使用
list
或
deque
很方便，但在更复杂的应用场景中，我们往往希望拥有更清晰、更具表达力的接口，并且能够处理一些边界情况，比如从空栈或空队列中取出元素。这时候，将栈和队列封装成独立的类就显得很有必要了。这样做不仅能提供更语义化的方法名（比如
push
、
pop
、
enqueue
、
dequeue
），还能在内部隐藏实现细节，并加入自定义的错误处理逻辑。
下面是两个简单的类封装示例：
class MyStack: def __init__(self): # 内部使用列表存储栈元素 self._items = [] def push(self, item): """元素入栈""" self._items.append(item) def pop(self): """元素出栈，如果栈为空则抛出错误""" if not self._items: raise IndexError("pop from empty stack") return self._items.pop() def peek(self): """查看栈顶元素，不移除""" if not self._items: raise IndexError("peek from empty stack") return self._items[-1] def is_empty(self): """判断栈是否为空""" return not self._items def size(self): """返回栈中元素数量""" return len(self._items) def __str__(self): return f"Stack({self._items})" def __repr__(self): return self.__str__()# 使用自定义栈s = MyStack()s.push(10)s.push(20)print(f"我的栈: {s}")print(f"栈顶元素: {s.peek()}")print(f"出栈: {s.pop()}")print(f"栈是否为空: {s.is_empty()}")print(f"栈大小: {s.size()}")# s.pop()# s.pop() # 再次pop会引发IndexErrorfrom collections import dequeclass MyQueue: def __init__(self): # 内部使用collections.deque存储队列元素，保证高效性 self._items = deque() def enqueue(self, item): """元素入队""" self._items.append(item) def dequeue(self): """元素出队，如果队列为空则抛出错误""" if not self._items: raise IndexError("dequeue from empty queue") return self._items.popleft() def peek(self): """查看队首元素，不移除""" if not self._items: raise IndexError("peek from empty queue") return self._items[0] def is_empty(self): """判断队列是否为空""" return not self._items def size(self): """返回队列中元素数量""" return len(self._items) def __str__(self): return f"Queue({list(self._items)})" # 转换为列表方便打印 def __repr__(self): return self.__str__()# 使用自定义队列q = MyQueue()q.enqueue('JobA')q.enqueue('JobB')print(f"我的队列: {q}")print(f"队首元素: {q.peek()}")print(f"出队: {q.dequeue()}")print(f"队列是否为空: {q.is_empty()}")print(f"队列大小: {q.size()}")# q.dequeue()# q.dequeue() # 再次dequeue会引发IndexError
通过类封装，我们不仅拥有了更直观的API，还可以在方法内部加入各种逻辑，比如在
pop()
或
dequeue()
之前检查是否为空，从而避免运行时错误，或者记录操作日志，甚至可以扩展成线程安全的版本。这让代码更健壮，也更易于维护和理解。
什么时候应该选择
collections.deque
collections.deque
而不是普通列表来模拟栈和队列？
这是一个很实际的问题，选择哪种数据结构确实需要根据具体场景来定。在我看来，
collections.deque
和普通列表各有其最佳使用场景，没有绝对的优劣，关键在于“合适”。
选择
collections.deque
的场景：
作为队列使用时，特别是需要频繁从头部移除元素： 这是
deque
最主要的优势。正如前面提到的，
list.pop(0)
的O(n)性能在处理大量数据时会成为瓶颈，而
deque.popleft()
是O(1)。如果你在实现广度优先搜索（BFS）、任务调度器、日志处理队列等需要频繁“出队”的场景，那么
deque
几乎是唯一的选择。作为双端队列使用时： 如果你的需求不仅是栈或队列，而是需要在两端都进行高效的添加和移除操作，比如实现一个历史记录功能，既能添加新记录，又能回溯旧记录，
deque
的
append()
,
appendleft()
,
pop()
,
popleft()
都能提供O(1)的性能。对性能有严格要求，且数据量可能很大： 当你的程序需要处理大量数据，并且对响应时间有较高要求时，
deque
的恒定时间复杂度优势就非常明显了。它避免了列表在中间或头部操作时可能出现的元素复制和移动开销。需要固定大小的循环缓冲区：
deque
有一个
maxlen
参数，可以创建一个固定大小的双端队列。当队列满时，再添加新元素会自动从另一端移除最老的元素。这对于实现滑动窗口、最近访问列表等功能非常方便，省去了手动管理大小的麻烦。
选择普通列表（
list
）的场景：
作为栈使用时： 如果你仅仅是需要一个栈，只在列表的末尾进行
append()
和
pop()
操作，那么普通列表完全够用，而且其实现也更简洁直观。在这种情况下，
list
和
deque
的性能差异可以忽略不计。数据量较小，且对性能要求不那么极致： 对于小规模数据，即使偶尔有
list.pop(0)
这样的O(n)操作，其影响也可能微乎其微。代码的简洁性和可读性有时比极致性能更重要。需要频繁随机访问元素： 列表支持通过索引进行O(1)的随机访问（
my_list[index]
），而
deque
虽然也支持索引访问，但在内部实现上，它的随机访问效率不如列表。如果你除了栈/队列操作外，还需要频繁地根据索引访问中间元素，那么列表可能更合适。
总的来说，当涉及到队列操作，尤其是需要从头部移除元素时，
collections.deque
是Pythonic且高效的选择。而如果只是简单的栈操作，或者数据量不大且需要随机访问，那么列表的简洁性也很有吸引力。理解它们底层的工作原理和时间复杂度，能帮助我们做出更明智的技术决策。
以上就是如何用Python实现栈和队列？的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1370244.html
微信扫一扫 
支付宝扫一扫 
