使用 Python 实现堆栈结构

什么是堆栈？

堆栈是一种以后进/先出方式存储项目的数据结构。这通常称为 LIFO。这与队列相反，队列以先进先出 (FIFO) 方式存储项目。

使用list创建一个Python堆栈

list 你可能在程序中经常使用的内置结构可以用作堆栈。你可以使用 .append() 代替 .push() 将新元素添加到堆栈的顶部，而 .pop() 则以 LIFO 顺序删除元素：

>>> myStack = []
>>> myStack.append('a')
>>> myStack.append('b')
>>> myStack.append('c')
>>> myStack
['a', 'b', 'c']
>>> myStack.pop()
'c'
>>> myStack.pop()
'b'
>>> myStack.pop()
'a'
>>> myStack.pop()
Traceback (most recent call last):
  File "<console>", line 1, in <module>
IndexError: pop from empty list

你可以在最后一个命令中看到，如果你使用空堆栈调用 list，它将引发一个。 IndexError.pop()

list 的好处是熟悉。你知道它是如何工作的，并且可能已经在你的程序中使用它。

不幸的是，与其他数据结构相比，列表有一些缺点。问题是随着它的增长，它会遇到速度问题。列表存储项目的目的是提供对列表中随机元素的快速访问。在高层次上，这意味着项目在内存中彼此相邻存储。

如果你的栈比当前持有它的内存块大，那么 Python 需要做一些内存分配。这可能会导致某些 .append() 调用比其他调用花费更长的时间。

还有一个不太严重的问题。如果你使用 .insert() 将元素添加到堆栈的末尾以外的位置，则可能需要更长的时间。但是，这通常不是你想要对堆栈执行的操作。

下一个数据结构将帮助你解决你看到的重新分配问题列表。

使用collections.deque创建一个Python堆栈

collections 模块包含双端队列，这对于创建 Python 堆栈很有用。 deque 发音为“deck”，代表“双端队列”。

你可以使用同样的方法deque，你上面看到的list，.append()和.pop()：

>>> from collections import deque
>>> myStack = deque()
>>> myStack.append('a')
>>> myStack.append('b')
>>> myStack.append('c')
>>> myStack
deque(['a', 'b', 'c'])
>>> myStack.pop()
'c'
>>> myStack.pop()
'b'
>>> myStack.pop()
'a'
>>> myStack.pop()
Traceback (most recent call last):
  File "<console>", line 1, in <module>
IndexError: pop from an empty deque

这看起来与上面的示例列表几乎相同。此时，你可能想知道为什么 Python 核心开发人员创建了两个看起来相同的数据结构。