如何用Python实现栈和队列？

夜晨

发布时间：2025-09-05 18:19:02

383人浏览过

来源于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)

。

bee餐饮点餐外卖小程序

bee餐饮点餐外卖小程序是针对餐饮行业推出的一套完整的餐饮解决方案，实现了用户在线点餐下单、外卖、叫号排队、支付、配送等功能，完美的使餐饮行业更高效便捷！功能演示：1、桌号管理登录后台，左侧菜单 “桌号管理”，添加并管理你的桌号信息，添加以后在列表你将可以看到 ID 和密钥，这两个数据用来生成桌子的二维码2、生成桌子二维码例如上面的ID为 308，密钥为 d3PiIY，那么现在去左侧菜单微信设置

下载

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

虽然直接使用

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