栈Stack：什么是栈？
一种有次序的数据项集合，在栈中，数据项的加入和移除都仅发生在同一端
这一端叫栈“顶top”，另一端叫栈“底base”
日常生活中有很多栈的应用
装羽毛球的盒子
距离栈底越近的数据项，留在栈中的时间就越长
而最新加入栈的数据项会被最先移除
这种次数通常称为“后进先出LIFO”：Last in First out
这是一种基于数据项保存时间的次序，时间最短的离栈顶越近，而时间越长的离栈底越近
栈的特性：反转次序
我们观察一个由混合的python原生数据对象形成的栈
进栈和出栈的次序正好相反
这种访问次序反转的特性，我们在某些计算机操作上碰到过
浏览器的“后退back”按钮，最先back的是最近访问的网页，Word的“Undo”按钮，最先撤销的是最近操作
抽象数据类型“栈”是一个有次序的数据集，每个数据项仅从“栈顶”一端加入到数据集中、从数据集中移除，栈具有后进先出LIFO的特性
抽象数据类型“栈”定义为如下的操作
- Stack()：创建一个空栈，不包含任何数据项
- push(item)：item加入栈顶，无返回值
- pop()：将栈顶数据项移除，并返回，栈被修改
- peek()：“窥视”栈顶数据项，返回栈顶的数据项但不移除，栈不被修改
- isEmpty()：返回栈是否为空栈
- size()：返回栈中有多少个数据项
抽象数据类型Stack：操作样例
用Python实现ADT Stack
在清楚地定义了抽象数据类型Stack之后， 我们看看如何用Python来实现它
Python的面向对象机制， 可以用来实现用户自定义类型
将ADT Stack实现为Python的一个Class将ADT Stack的操作实现为Class的方法由于Stack是一个数据集，所以可以采用Python的原生数据集来实现，我们选用最常用的数据集List来实现
一个细节： Stack的两端对应list设置
可以将List的任意一端（index=0或者-1）设置为栈顶我们选用List的末端（index=-1）作为栈顶这样栈的操作就可以通过对list的append和pop来实现，很简单！
用Python实现ADT Stack
class Stack:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[-1]
def size(self):
return len(self.items)
Stack测试代码
s = Stack()
print(s.isEmpty())
s.push(4)
s.push('dog')
print(s.peek())
s.push(True)
print(s.size())
print(s.isEmpty())
s.push(8.4)
print(s.pop())
print(s.pop())
print(s.size())
输出结果：
ADT Stack的另一个实现
如果我们把List的另一端（首端index=0） 作为Stack的栈顶， 同样也可以实现Stack
不同的实现方案保持了ADT接口的稳定性
但性能有所不同，栈顶首端的版本（左），其push/pop的复杂度为O(n)，而栈顶尾端的实现（右），其push/pop的复杂度为O(1)
版权声明：本文不是「本站」原创文章，版权归原作者所有 | 原文地址: