Python实现栈的三种方法：List、Deque与LifoQueue详解

Aria

发布时间：2026-10-14| 2人浏览过

原创

本文详细介绍Python中实现栈数据结构的三种主要方式：内置列表list、collections.deque双端队列以及queue模块的LifoQueue。文章对比了各方法在时间复杂度、内存管理及适用场景上的差异，重点解析deque在O(1)操作效率上的优势，并提供完整的代码示例，帮助开发者根据实际需求选择最优方案。

栈（Stack）是一种基础的线性数据结构，其核心特征遵循“先进后出”（First In Last Out, FILO）或“后进先出”（Last In First Out, LIFO）的原则。在栈结构中，所有的数据插入和删除操作均严格限制在栈顶（Top）进行，这一特性使得栈在函数调用、表达式求值及回溯算法等场景中具有广泛应用。

empty()：用于检测栈是否为空状态，该操作的时间复杂度为 O(1)。
size()：用于获取当前栈中元素的数量，该操作的时间复杂度为 O(1)。
top()：用于访问栈顶元素但不移除它，该操作的时间复杂度为 O(1)。
push(g)：用于将元素 g 压入栈顶，该操作的时间复杂度为 O(1)。
pop()：用于移除并返回栈顶元素，该操作的时间复杂度为 O(1)。

在 Python 编程语言中，开发者可以通过以下三种不同的内置数据结构或模块来实现栈的功能：

第一种方法：使用内置列表（list）

第二种方法：使用 collections.deque 双端队列

第三种方法：使用 queue 模块中的 LifoQueue

### 方法一：使用列表（List）实现栈

Python 的内置数据结构 list 可以直观地用于模拟栈的行为。具体而言，利用 list 的 append() 方法可以向栈顶添加新元素，而使用 pop() 方法则能够按照后进先出的顺序移除并返回栈顶元素。这种实现方式代码简洁，易于理解。

然而，使用列表实现栈存在潜在的性能瓶颈。由于 list 是动态数组，当栈内元素数量增长导致当前内存空间不足时，Python 会自动重新分配更大的内存块，并将原有元素复制到新内存中。这一过程会导致部分 append() 操作的时间复杂度退化为 O(n)，从而在执行大规模数据压栈时出现速度瓶颈。


>>> stack = []
>>> #append() fuction to push
... #element in list
... 
>>> stack.append('hello')
>>> stack.append('world')
>>> stack.append('!')
>>> print('Initial stack')
Initial stack
>>> print(stack)
['hello', 'world', '!']
>>> #pop() function to pop element
... #from stack in LIFO order
... 
>>> print('\nElement poped from stack')

Element poped from stack

>>> print(stack.pop())
!
>>> print(stack.pop())
world
>>> print(stack.pop())
hello
>>> print('\nStack after all elements are poped')

Stack after all elements are poped
>>> print(stack)
[]

### 方法二：使用 collections.deque 实现栈

Python 标准库中的 collections.deque 类提供了更高效的栈实现方案。deque（双端队列）专为在容器两端进行快速插入和删除操作而设计。与 list 不同，deque 在执行 append() 和 pop() 操作时均能保持 O(1) 的时间复杂度，无需进行内存重分配和数据复制，因此在处理大量元素或高频操作场景下，其性能显著优于 list。


>>> from collections import deque
>>> stack = deque()
>>> # append() fuction to push
... #element in list
... 
>>> stack.append('hello')
>>> stack.append('world')
>>> stack.append('!')
>>> print('Initial stack')
Initial stack
>>> print(stack)
deque(['hello', 'world', '!'])
>>> #pop() function to pop element
... #from stack in LIFO order
... 
>>> print('\nElement poped from stack')

Element poped from stack
>>> print(stack.pop())
!
>>> print(stack.pop())
world
>>> print(stack.pop())
hello
>>> print('\nStack after all elements are poped')

Stack after all elements are poped
>>> print(stack)deque([])

### 方法三：使用 queue 模块实现栈

Python 的 queue 模块提供了线程安全的 LifoQueue（后进先出队列）类，可用于实现栈结构。通过调用 put() 方法可以向栈中添加元素，使用 get() 方法可以移除并获取栈顶元素。LifoQueue 适用于多线程环境下的栈操作，提供了必要的同步机制。


>>> from queue import LifoQueue
>>> stack = LifoQueue(maxsize = 3)
>>> print(stack.qsize())
0
>>> stack.put('hello')
>>> stack.put('world')
>>> stack.put('!')
>>> print('\nElement poped from stack')

Element poped from stack
>>> print(stack.get())
!
>>> print(stack.get())
world
>>> print(stack.get())
hello
>>> print('\nEmpty:', stack.empty())

Empty: True

以上即为在 Python 中实现栈的三种主要方法的详细解析。如需了解更多关于 Python 数据结构的高级应用，建议查阅本站其他相关技术文章。