栈
栈的特征
栈的区别特征是,添加或删除项发生在同一末端。这一端通常被称为“顶部”。它的反面被称为“底部”。调用堆栈排序的原理后进先出(简称以后出).在我们的一堆书中,最后一本书必须当我们取下一本书时,它就会掉下来。
有时,堆栈被实现为具有最大容量。在这些情况下,如果为堆栈分配的空间已被完全使用,则不能再推入任何元素,任何这样做的尝试都会导致堆栈溢出错误。这是编程世界中最常见的错误之一,Q&A网站也因此得名stackoverflow.com.相反的情况也可能发生,当堆栈为空时尝试弹出时:这会导致栈下溢错误。
最小所需功能
有两个与堆栈相关的基本操作。
函数名* 提供的功能 push ()
插入元素我在堆栈的顶部。 pop ()
移除堆栈顶部的元素。 栈通常使用以下函数实现。
函数名* 提供的功能 尺寸()
返回堆栈的当前大小。 peek ()
返回堆栈顶部的元素不改变堆栈 *不需要精确的名字。事实上,某些功能可以通过特定的语法直接由特定的语言提供。
栈的问题
栈的问题
考虑一堆从0到10编号的盒子,按升序排列,一个在另一个上面,这样数字10就在上面。
我们怎么把11号盒子塞进这一堆?
我们怎么从这堆东西里取出一个盒子?
如果房间的高度只够放11个箱子,当我们试着推第12个箱子时会发生什么?
如果我们从堆栈中取出所有的盒子然后尝试从堆栈中取出一个盒子会发生什么?
A1。盒子11放在盒子10的上面。
A2。去掉最上面的盒子(盒子10)。
A3。由于没有更多的空间,这类似于堆栈溢出错误。
A4。由于我们在堆栈中已经没有盒子了,这类似于堆栈底流错误。
可视化堆栈
堆栈及其操作通常被看作是一堆卡片或书。考虑下面的空堆栈。
推
本质上是将给定项与特定值堆叠在堆栈顶部。例如,如果运行下面的代码块,
1 2 3 |
|
得到的堆栈看起来如下所示:
流行
通过反向操作并踢出堆栈的顶部元素来工作。对于上面的堆栈,执行操作块会使它看起来像
1 2 3 |
|
在执行下面的操作块之后,空堆栈是什么样子的?
1 2 3推(6)推(5)推(流行()*2)
答案是D.最后一行只是取出最后一个元素,将它翻倍,然后放回去。
在一个空堆栈上执行下面的操作块之后,它会是什么样子?
1 2 3 4 5 5推(5)推(3.)推(7)推(流行()+1)偷看()
这个堆栈看起来像这样:
1 2 3 4(5) (5,3) (5,3,7) (5,3,8)
因此 将输出。
使用列表实现堆栈的Python示例
为了实现堆栈数据结构,我们通常需要:
- 存储数据项的存储器区域
- 指向堆栈顶部的指针
- 一组定义良好的操作:
推
,流行
,偷看
和大小
在这个实现中,堆栈的顶部位于数组的右侧。
注意:如你所见,栈已经在Python中实现了下面.这是一个重新实现。
12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
|
现在我们已经完全描述了堆栈ADT的行为,我们可以很容易地实现它,如上所示。尽管有几种实现堆栈ADT的方法,但这里我们将使用基于数组的实现。因为我们将使用python,所以不必调整列表的大小,因为它们是动态调整大小的。我们的实现将非常简单,将在列表的末尾添加和删除新项目。
编写一个反转堆栈内容的方法
解决方案
如果这个方法不是栈ADT的实例方法,我们可以写
反向
作为
1 2 3 4 5 5def反向(堆栈):new_stack=堆栈()而堆栈.大小()! =0:new_stack.推(堆栈.流行())返回new_stack
内置Python堆栈功能
列表在Python中已经有附加
和流行
方法,使它们可以作为堆栈使用。
使用列表作为堆栈
1>>>mystack=[]
现在堆栈是空的,让我们用一些元素填充它。
1 2 3 4 5 6>>>myStack.附加(1)>>>myStack.附加(2)>>>myStack.附加(3.)>>>myStack[1,2,3.]
现在我们来做第二个重要的操作,那就是从它里面取出一个元素。
1 2 3 4 5 5>>>myStack.流行()3.>>>myStack.流行()2
正如预期的那样,它的行为像一个堆栈,这就是我们需要从这个数据类型。你可能会因为它能做的事情有限而气馁,但当你试图解决更复杂的问题时,你会为它的力量而兴奋不已。使用堆栈可以简化事情,您可能会对此印象深刻。
让我们有更多的乐趣。
1 2 3 4 5 6 7>>>myStack.附加(7)>>>myStack.附加(8)>>>myStack[1,7,8]>>>myStack.流行()8
时间复杂度
栈的时间复杂度取决于所使用的数据结构的类型和所构建的具体实现。下面是链表和数组在复杂性方面的区别:
链表 | 数组 | |
推 | ||
流行 |
堆栈,不像队列,只执行在列表的一端.这个不变量使这个过程更容易。在我们的书堆中,添加一本书非常容易,因为我们已经知道最上面的书在哪里。同样,去掉最上面的书也很容易,因为我们知道它在哪里。不需要遍历剩下的一堆因为所有的操作都发生在一个点上。