作者：18级潘愽浩

栈Stack

定义

一种有次序的数据项集合，在栈中，数据项的加入和移除都仅发生在同一端。这一端叫做栈“顶top”，另一端叫栈“底base”。

日常生活中有很多栈的应用，盘子、托盘、书堆等等都属于栈。

性质

1．后进先出

距离栈底越近的数据项，留在栈中的时间就越长，而最新加入栈的数据项会被最先移除。

这种次序通常称为“后进先出LIFO”：Lats in First out
这是一种基于数据项保存时间的次序，时间越短的离栈顶越近，而时间越长的离栈底越近。

2．反转次序

我们观察一个有混合的python原生数据对象形成的栈

可以发现，进栈和出栈的次序正好相反。

其实，这种形式的数据存储结构我们每天都在计算机上接触。例如：浏览器的“后退back”按钮，最先back的是最近访问的网页，打开历史记录页面，它们的排列方式也是栈的形式；word的“Undo”按钮，最先撤销的也是最近操作。

概述

抽象数据类型“栈”是一个有次序的数据集，每个数据项仅从“栈顶”一端加入到数据集中、从数据集中移除，占据有后进先出LIFO的特性。

常规操作

定义抽象数据类型栈的各种操作：
Stack（）:创建一个空栈，不包含任何数据项
push（item）：将item加入栈顶，无返回值
pop（）：将栈顶数据项移除，并返回所移除的值，栈被修改
peek（）：“窥视”栈顶数据项，返回栈顶的数据项但不移除，栈不被修改
isEmpty（）：返回栈是否为空栈
size（）：返回栈中有多少个数据项

操作实例：

用python实现ADT Stack

大致思路

在清楚地定义了抽象数据类型Stack之后，根据python良好的面向对象机制，可以用来实现用户自定义类型。

将ADT Stack实现为python的一个class
由于Stack是一个数据集，所以可以采用python的原生数据集来实现，我们选用最常用的数据集List来实现。

Stack的两端对应的list设置

可以将List的任意一端（index = 0或者-1）设置为栈顶，不过，我们一般选用List的末端（index = -1）作为栈顶。这样的话栈的操作可以通过对list的append（添加元素）和pop（删除元素）来实现，使用起来相当方便。

对应代码

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)

使用操作：

另一种实现代码

我们知道，栈有两种实现形式——将list首段设为栈顶和将list末端设为栈顶。栈顶首段的版本（左边）push/pop的复杂度为O（n），而栈顶尾端的实现（右边），其push/pop的复杂度为O（1）。