Python 实现栈的几种方式及其优劣

Python实现栈的几种方式及其优缺点1.栈的概念栈是由一系列对象组织起来的集合。这些对象的增删操作遵循“后进先出”（LastInFirstOut，LIFO）原则。任何时候只能向栈中插入一个对象，但只能在栈顶进行get或delete操作。例如，在一摞书中，只有最上面的那本书的封面露出来。要想拿到其他的书，只能把最上面的书拿掉，如图：栈的实际应用其实很多应用都会用到。堆栈，例如：Web浏览器将最近浏览的URL存储在堆栈中。每当用户访问者访问一个新网站时，新网站的URL就会被推到堆栈的顶部。这样，每当我们点击浏览器中的“后退”按钮（或者按键盘快捷键CTRL+Z，撤销快捷键居多），我们就可以弹出最近一次访问的URL，回到之前的浏览器状态.文本编辑器通常提供一种“撤消”机制来取消最近的编辑操作并返回到以前的状态。这种撤消操作也是通过将文本的更改状态保存在堆栈中来实现的。一些高级语言的内存管理，JVM栈，Python栈也用于内存管理，嵌套语言特性的运行环境等Hanoi，树遍历，直方图问题，也用于拓扑排序等图形算法语法处理：参数和局部变量的空间是在内部用堆栈创建的。编译器对花括号匹配的语法检查支持递归编译器中的后缀或前缀等表达式2.栈的抽象数据类型任何数据结构都离不开数据的保存和获取方式，上面说了栈是一个有序的元素的集合，加法、运算、移除都发生在它的栈顶（stacktop），那么它的抽象数据类型包括：Stack()：创建一个空栈，不需要参数，返回一个空栈。push(e)：将一个元素e添加到栈顶S，它有一个参数e并且没有返回值。pop()：移除栈顶元素。它不需要参数，但返回顶部的元素并修改堆栈的内容。top()：返回栈顶元素，但不移除栈顶元素；如果堆栈为空，则执行此操作。is_empty()：如果堆栈不包含任何元素，则返回布尔值True。size()：返回栈中元素的数据。它不接受任何参数并返回一个整数。在Python中，这可以通过特殊方法__len__来实现。Python堆栈的大小可能是固定的，或者可能有一个允许大小变化的动态实现。在固定大小堆栈的情况下，尝试向已经满的堆栈添加元素将导致堆栈溢出异常。同样，尝试使用pop()操作从已经为空的堆栈中删除元素称为下溢。3.用Python列表实现栈学习Python的时候，一定学过Python列表list，它可以通过一些内置的方法实现栈的功能：append方法用于在列表的末尾添加一个元素列表，这样就可以模拟push()操作了。pop()方法用于模拟出栈操作。通过L[-1]模拟top()操作。通过判断len(L)==0来模拟isEmpty()操作。size()函数由len()函数实现。代码如下：classArrayStack:"""通过Python列表实现后进先出栈"""def__init__(self):self._data=[]defsize(self):"""返回栈中元素的个数"""returnlen(self._data)defis_empty(self):"""如果堆栈为空则返回True"""returnlen(self._data)==0defpush(self,e):"""添加元素e到栈顶"""self._data.append(e)defpop(self):"""从栈顶移除并返回元素"""ifself.is_empty():raiseException('Stackisempty')returnself._data.pop()deftop(self):"""returntopofthestackRaiseEmptyexceptionifthestackisempty"""ifself.is_empty():raiseException('Stackisempty')returnself._data[-1]#listarrayStack=ArrayStack()arrayStack.push("Python")arrayStack.push("Learning")arrayStack.push("Hello")print("堆栈顶部元素：",arrayStack.top())print("堆栈长度：",arrayStack.size())print("堆栈弹出项：%s"%arrayStack.pop())print("Stackisempty?",arrayStack.is_empty())arrayStack.pop()arrayStack.pop()print("Stackisempty?",arrayStack.is_empty())#arrayStack.pop()运行程序，得到result:栈顶元素:HelloStack长度:3Stack出栈项:HelloStack为空?FalseStack为空?True除了使用链表的尾部作为栈顶，还可以使用链表的头部作为栈顶堆栈的但是，在这种情况下，不能直接使用pop()和append()方法，而是可以通过pop()和insert()方法显式访问下标为0的元素，也就是列表的第一个元素，代码如下：classArrayStack:"""通过Pythonlist实现后进先出栈"""def__init__(self):self._data=[]defsize(self):"""返回数组中的元素个数stack"""returnlen(self._data)defis_empty(self):"""如果堆栈为空则返回True"""returnlen(self._data)==0defpush(self,e):"""添加元素e到栈顶"""self._data.insert(0,e)defpop(self):"""从栈顶移除并返回元素"""ifself.is_empty():raiseException('Stackisempty')returnself._data.pop(0)deftop(self):"""如果堆栈为空则返回栈顶RaiseEmptyexception"""ifself.is_empty():raiseException('Stackisempty')returnself._data[0]#列表中的最后一项，尽管我们改变了abstra数据类型然而，该方法的实现保留了它的逻辑特性。这种能力体现了抽象的思想。虽然两种方法都实现了栈，但是两者的表现方式不同：append()和pop()方法的时间复杂度都是*O(1)，*constantlevel操作的第二次实现的表现是受栈中元素个数限制，因为insert(0)和pop(0)的时间复杂度为O(n)，元素越多越慢。4.使用collections.deque实现stack在Python中，collections模块有一个双端队列数据结构deque，同样实现了append()和pop()方法：>>>fromcollectionsimportdeque>>>myStack=deque()>>>myStack.append('苹果')>>>myStack.append('香蕉')>>>myStack.append('橙色')>>>>>>myStackdeque(['苹果','香蕉','橙色'])>>>myStack.pop()'橙色'>>>myStack.pop()'香蕉'>>>>>>len(myStack)1>>>myStack[0]'苹果'>>>myStack.pop()'苹果'>>>>>>myStack.pop()Traceback（最近调用最后）：文件“”，第1行，在myStack中。pop()IndexError:popfromanemptydeque>>>当你有一个列表时，为什么你需要一个双端队列？可能你看到了deque和list列表对元素的操作类似，那为什么Python要有一个list，还要加一个deque数据结构呢？这是因为Python中的列表构建在连续的内存块中，这意味着列表的元素彼此相邻存储。这对于某些操作非常有效，例如索引列表。获取myList[3]的速度很快，因为Python确切地知道在内存中的何处查找它。这种内存布局还允许切片在列表上很好地工作。list的连续内存布局可能需要更多时间来.append()某些对象。如果连续的内存块已经满了，就需要再获取一个内存块，先把整个复制过去。此操作可能比一般的.append()操作花费更多时间。双端队列deque基于双链表。在链表结构中，每个条目都存储在自己的内存块中，并引用列表中的下一个条目。双向链表也是如此，除了每个条目都引用列表中的前一个和后一个条目。这使您可以轻松地在列表的两端添加节点。要向链表结构添加新条目，只需将新条目的引用设置为指向当前栈顶，然后将栈顶设置为指向新条目。然而，不断在堆栈中添加和删除条目所花费的时间是有代价的。获取myDeque[3]比列表慢，因为Python需要遍历列表的每个节点才能获取第三个元素。幸运的是，您很少希望随机索引堆栈上的元素或执行列表切片操作。堆栈上的大多数操作都是压入或弹出。如果您的代码不使用线程，恒定时间的.append()和.pop()操作使双端队列成为实现Python堆栈的更好选择。5、使用queue.LifoQueue实现栈Python栈在多线程程序中也很有用。我们学习了list和deque两种方式。对于任何可以被多线程访问的数据结构，在多线程编程中，我们不应该使用list，因为list不是线程安全的。双端队列的.append()和.pop()方法是原子的，这意味着它们不会受到不同线程的干扰。因此，虽然使用双端队列可以构建线程安全的Python堆栈，但这样做会导致将来因创建竞争条件而被滥用。好吧，如果你是多线程的，你不能将列表用于堆栈，你可能不想将双端队列用于堆栈，那么你如何为线程程序构建Python堆栈？答案就在队列模块：queue.LifoQueue。还记得您是如何了解到堆栈按照后进先出(LIFO)原则运行的吗？嗯，这就是LifoQueue的“Lifo”部分所代表的意思。虽然list和deque的接口相似，但LifoQueue使用.put()和.get()在堆栈中添加和删除数据。>>>从队列导入LifoQueue>>>stack=LifoQueue()>>>stack。放（'H'）>>>堆栈。放（'E'）>>>堆栈。put('L')>>>stack.put('L')>>>stack.put('O')>>>stack>>>>>>>>stack.get()'O'>>>stack.get()'L'>>>stack.empty()False>>>stack.qsize()3>>>stack.get()'L'>>>堆栈。get()'E'>>>stack.qsize()1>>>stack.get()'H'>>>stack.get_nowait()Traceback（最近调用最后）：文件“”,line1,instack.get_nowait()_queue.Empty>>>>>>stack.put('Apple')>>>stack.get_nowait()'Apple'不像deque，LifoQueue被设计成完全线程安全的。它的所有方法都可以在线程环境中安全使用。它还为其操作添加了可选的超时，这在线程程序中通常是必须的。然而，这种完全的线程安全是有代价的。为了实现这种线程安全，LifoQueue必须在每个操作上做一些额外的工作，这意味着它会花费更长的时间。通常，这种轻微的减速对您的整体程序速度并不重要，但如果您测量了您的性能并发现您的堆栈操作是瓶颈，那么可能值得谨慎切换到双端队列。6.选择哪种实现作为栈一般来说，如果不使用多线程，应该使用deque。如果您正在使用多线程，那么您应该使用LifoQueue，除非您已经测量了您的性能并发现推送和弹出速度的小幅增加会产生足够的差异以保证维护风险。您可能对列表很熟悉，但您需要谨慎使用它，因为它可能会出现内存重新分配问题。deque和list的接口是一样的，deque没有线程不安全。七。小结本文介绍了栈的数据结构以及在实际程序中的使用方法。在文章中，我介绍了在Python中实现堆栈的三种不同方式。我知道双端队列是非多线程程序的更好选择。如果你想在多线程编程环境中使用栈，你可以使用LifoQueue。了解更多开源知识，请访问：开源基础软件社区https://ost.51cto.com。