如何用Python实现栈和队列？-Python教程-PHP中文网

使用列表实现栈高效，因append和pop操作均为O(1)；但用列表实现队列时，pop(0)为O(n)，性能差。应使用collections.deque实现队列，因其popleft为O(1)。封装类可提供更清晰接口和错误处理，适用于复杂场景。频繁出队或大数据量时优选deque，简单栈操作可选list。

如何用python实现栈和队列？

在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)

登录后复制

。

ViiTor实时翻译

AI实时多语言翻译专家！强大的语音识别、AR翻译功能。

116

查看详情

除了内置类型，如何用类封装栈和队列，实现更清晰的接口和错误处理？

虽然直接使用

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
```
登录后复制
虽然也支持索引访问，但在内部实现上，它的随机访问效率不如列表。如果你除了栈/队列操作外，还需要频繁地根据索引访问中间元素，那么列表可能更合适。