Python 实现栈的几种方式及其优劣( 二 ) _Python

运行该程序，结果：
Stack top element:HelloStack length:3Stack popped item: HelloStack is empty? FalseStack is empty? True除了将列表的队尾作为栈顶，也可以通过将列表的头部作为栈的顶端。不过在这种情况下，便无法直接使用方法和方法，但是可以通过和方法显式地访问下标为 0 的元素，即列表的第一个元素，代码如下：pop()append()pop()insert()
class ArrayStack:""" 通过 Python 列表实现 LIFO 栈"""def __init__(self):self._data = https://www.isolves.com/it/cxkf/yy/Python/2023-05-08/[]def size(self):""" return the number of elements in the stack"""return len(self._data)def is_empty(self):""" return True if the stack is empty"""return len(self._data) == 0def push(self, e):""" add element e to the top of the stack"""self._data.insert(0, e)def pop(self):""" remove and return the element from the top of the stack"""if self.is_empty():raise Exception('Stack is empty')return self._data.pop(0)def top(self):"""return the top of the stackRaise Empty exception if the stack is empty"""if self.is_empty():raise Exception('Stack is empty')return self._data[0]# the last item in the list虽然我们改变了抽象数据类型的实现，却保留了其逻辑特征，这种能力体现了抽象思想。不管，虽然两种方法都实现了栈，但两者的性能方法有差异：

append() 和方法的时间复杂度都是 _**O(1)**，_常数级别操作pop()
第二种实现的性能则受制于栈中的元素个数，这是因为和的时间复杂度都是 O(n)，元素越多就越慢。insert(0)pop(0)

4 用 collections.deque 实现栈在 Python 中，模块有一个双端队列数据结构 deque，这个数据结构同样实现了和方法：collectionsappend()pop()

>>> from collections import deque>>> myStack = deque()>>> myStack.append('Apple')>>> myStack.append('Banana')>>> myStack.append('Orange')>>> >>> myStackdeque(['Apple', 'Banana', 'Orange'])>>> myStack.pop()'Orange'>>> myStack.pop()'Banana'>>>>>> len(myStack)1>>> myStack[0]'Apple'>>> myStack.pop()'Apple'>>>>>> myStack.pop()Traceback (most recent call last):File "<pyshell#13>", line 1, in <module>myStack.pop()IndexError: pop from an empty deque>>>

为什么有了 list 还需要 deque？可能你可以看到 deque 和列表 list 对元素的操作差不多，那么为什么 Python 中有列表还增加了 deque 这一个数据结构呢？
那是因为，Python 中的列表建立在连续的内存块中，意味着列表的元素是紧挨着存储的。

文章插图
这对一些操作来说非常有效，比如对列表进行索引。获取的速度很快，因为 Python 确切地知道在内存中寻找它的位置。这种内存布局也允许切片在列表上很好地工作。myList[3]
毗连的内存布局是 list 可能需要花费更多时间来一些对象。如果连续的内存块已经满了，那么它将需要获得另一个内存块，先将整体 copy 过去，这个动作可能比一般的操作花费更多的时间。.append().append()

文章插图
而双端队列是建立在一个双链表的基础上。在一个链接列表结构中，每个条目都存储在它自己的内存块中，并有一个对列表中下一个条目的引用。deque
双链表也是如此，只是每个条目都有对列表中前一个和后一个条目的引用。这使得你可以很容易地在列表的两端添加节点。
在一个链接列表结构中添加一个新的条目，只需要设置新条目的引用指向当前堆栈的顶部，然后将堆栈的顶部指向新条目。

文章插图
Memory structure of a deque pushing a new element
然而，这种在栈上不断增加和删除条目的时间是有代价的。获取的速度要比列表慢，因为 Python 需要走过列表的每个节点来获取第三个元素。myDeque[3]
幸运的是，你很少想在栈上做随机索引元素或进行列表切片操作。栈上的大多数操作都是或。pushpop
如果你的代码不使用线程，常数时间的和操作使 deque 成为实现 Python 栈的一个更好的选择。.append().pop()
5 用 queue.LifoQueue 实现栈Python 栈在多线程程序中也很有用，我们已经学习了和两种方式。对于任何可以被多个线程访问的数据结构，在多线程编程中，我们不应该使用，因为列表不是线程安全的。deque 的和方法是原子性的，意味着它们不会被不同的线程干扰。listdequelist.append().pop()