python中栈的标准实现方法,数据结构栈的基本运算
本文主要详细介绍Python中的堆栈。本文中的示例代码非常详细，具有一定的参考价值。感兴趣的朋友可以参考一下，希望能帮到你。
00-1010什么是堆栈构建堆栈摘要
目录
栈有时被称为“下推堆栈”。它是一个有序集合，添加和删除操作总是发生在同一端，即堆栈的“顶端”，堆栈的另一端称为“底端”.因此，最新添加的元素将被最先移除,和堆栈中的元素越靠近底部，它在堆栈中停留的时间越长。
这种排序原则被称为后进先出(LIFO)，即后进先出.它提供了一种基于在集合中的时间来排序的方式。最近增加的元素靠近顶部，而旧的元素靠近底部。
堆栈的例子在日常生活中比比皆是。几乎所有的咖啡馆都有一堆托盘或盘子。你可以从上面拿一个，下一个顾客会拿下面的托盘或盘子。
考虑到堆栈的反演性质，我们可以在使用计算机时想到一些例子。比如每个浏览器都有后退按钮。当我们从一个网页跳转到另一个网页时，这些网页——实际上是URL，并且都存储在一个堆栈中。当前浏览的网页在栈顶，最旧的网页在栈底。如果您单击后退按钮，您将开始反向浏览这些页面。
什么是栈
如前所述，堆栈是元素的有序集合，添加操作与移除操作都发生在其顶端.堆栈的操作顺序是LIFO，它支持以下操作：
向堆栈顶部添加一个元素，移除堆栈顶部的元素，返回堆栈顶部的元素，并返回堆栈中元素的数量。在我们知道了栈的基本特征之后，我们开始用代码来构建它。在面向对象编程语言中(以Python为例)，每当需要在Python中实现stack这样的抽象数据类型时，都可以通过创建类来实现，数据类型的特性和操作方法也可以通过在类中定义方法来实现。
我们来明确一下这个类的具体方法：
创建一个空栈.它不带参数，将返回一个空堆栈。堆栈()将一个元素添加到栈的顶端.它需要一个参数item，没有返回值。推(项)将栈顶端的元素移除.它不需要参数，但是它将返回顶部元素并修改堆栈的内容。pop()返回栈顶端的元素,但是这个元素没有被删除。它不需要参数，也不修改堆栈的内容。皮克(返回栈中元素的数目).它不带参数，返回一个整数。尺寸()检查栈是否为空.它不带参数，返回一个布尔值。isepty()打印这个栈/列表,它不需要参数，将输出堆栈的内容。Look()可以通过使用Python提供的强大而简单的原生集合来实现，因为栈是元素的集合.在这里，我们将使用列表。列表的最左端将用来表示栈底，最右边将用来表示栈顶：
类别堆栈：
#定义一个列表/构建一个堆栈
def __init__(self):
self.items=[]
打印(“你创建了一个堆栈！”)
def isEmpty(self):
return self.items==[]
def look(自身):
打印(自己的项目)
定义推送(自身，项目):
self.items.append(项目)
打印(您在堆栈顶部添加了一个%s%项目
def pop(自身):
返回self.items.pop()
def peek(自身):
return self . items[len(self . items)-1]
定义尺寸(自身):
归还贷款(自有项目)
以下展示了栈的操作及其返回结果：
值得注意的是，你也可以选择使用列表头(左)作为栈顶。但是，在这种情况下，不能直接使用列表的pop方法和append方法，而必须通过使用列表的pop方法和insert方法显式访问下标为0的元素，即列表中的第一个元素。以下代码显示了这种方式：
类别堆栈：
def __init__(self):
self.items=[]
def isEmpty(self):
return self.items==[]
def look(自身):
打印(自己的项目)
定义推送(自身，项目):
self.items.insert(0，item)
def pop(自身):
返回self.items.pop(0)
def peek(自身):
返回self.items[0]
定义尺寸(自身):
归还贷款(自有项目)
虽然以上两种实现都是可行的，但是在性能上肯定是有区别的。append方法和pop方法的时间复杂度是o (1) o(1) o(1)，也就是说第一个实现中的push操作和pop操作，无论栈中有多少个元素，都会在一个常数时间内完成。第二种实现的性能受到栈中元素数量的限制，因为insert(0)和pop(0)的时间复杂度是o (n) o(n) o(n)，元素越多，速度越慢。
显然，尽管这两种实现在逻辑上是相等的，但是在基准测试上花费的时间会有很大的不同。
构建一个栈
本文到此为止。希望能帮到你，也希望你能多关注更多热门IT软件开发工作室的内容！
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。