使用列表实现栈高效，因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}") # 输出: False2. 使用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}") # 输出: FalsePython内置列表作为栈和队列的性能瓶颈是什么？
说实话，用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会引发IndexError
from collections import deque
class 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
的场景：
-
作为队列使用时，特别是需要频繁从头部移除元素： 这是
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且高效的选择。而如果只是简单的栈操作，或者数据量不大且需要随机访问，那么列表的简洁性也很有吸引力。理解它们底层的工作原理和时间复杂度，能帮助我们做出更明智的技术决策。
