数据结构（3）：栈（上）

栈（Stack）是一种只允许在一端进行插入或删除操作的线性表。首先栈是一种线性表，但限定这种线性表只能在某一端进行插入和删除操作。

栈顶（Top）。线性表允许进行插入删除的那一端。

栈底（Bottom）。固定的，不允许进行插入和删除的另一端。

空栈。不含任何元素的空表。

假设某个栈 S=(a[1], a[2], a[3], a[4], a[5])，如图所示，则 a[1] 为栈底元素，a[5] 为栈顶元素。由于栈只能在栈顶进行插入和删除操作，进栈次序依次为 a[1]，a[2]，a[3]，a[4]，a[5]，而出栈次序为 a[5]，a[4]，a[3]，a[2]，a[1]。由此可见，栈的操作特性可以明显地概括为后进先出（Last In First Out，LIFO）。

注意：我们每接触到一种新的数据结构类型，都应该分别从其逻辑结构、存储结构和对数据的运算三个方面着手，以加深对定义的理解。

栈的数学性质：n 个不同元素进栈，出栈元素不同排列的个数为

上述公式称为卡特兰（Catalan）数，可采用数学归纳法证明。

栈的基本操作

__init__(self)：初始化一个空栈 self。

stack_empty(self)：判断一个栈是否为空，若栈 self 为空则返回 True，否则返回 False。

push(self, x)：进栈，若栈 self 未满，则将 x 加入使之成为新栈顶。

pop(self)：出栈，若栈 self 非空，则弹出栈顶元素，并返回。

get_top(self)：读栈顶元素，若栈 self 非空，则返回栈顶元素。

栈的顺序存储结构

栈是一种操作受限的线性表，类似于线性表，它也有对应的两种存储方式。

顺序栈的实现

采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针（top）指示当前栈顶元素的位置。

栈的顺序存储类型可描述为：

class Stack:    def __init__(self, max_size=50):        self.max_size = max_size  # 定义栈中最大元素个数        self.data = [None]*max_size  # 存放栈中元素        self.top = -1  # 栈顶指针

栈顶指针：self.top，初始时设置 self.top=-1；栈顶元素：self.data[self.top]。

进栈操作：栈不满时，栈顶指针先加 1，再送值到栈顶元素。

出栈操作：栈非空时，先取栈顶元素值，再将栈顶指针减 1。

栈空条件：self.top==-1；栈满条件：self.top==self.max_size-1；栈长：self.top+1。

由于顺序栈的入栈操作受数组上界的约束，当对栈的最大使用空间估计不足时，有可能发生栈上溢，此时应及时向用户报告消息，以便及时处理，避免出错。

注意：栈和队列的判空、判满条件，会因实际给的条件不同而变化，上面提到的方法以及下面的代码实现只是在栈顶指针设定的条件下的相应方法，而其他情况则需具体问题具体分析。

顺序栈的基本运算

下面是顺序栈上常用的基本运算的实现。

（1）初始化

class Stack:    def __init__(self, max_size=50):  # 初始化        self.max_size = max_size  # 定义栈中最大元素个数        self.data = [None]*max_size  # 存放栈中元素        self.top = -1  # 栈顶指针

（2）判栈空

    def stack_empty(self):  # 判栈空        if self.top == -1:  # 栈空            return True        else:  # 不空            return False

（3）进栈

    def push(self, x):  # 进栈        if self.top == self.max_size-1:  # 栈满，报错            return        self.top += 1  # 指针先加 1，再入栈        self.data[self.top] = x

（4）出栈

    def pop(self):  # 出栈        if self.top == -1:  # 栈空，报错            return        x = self.data[self.top]  # 先出栈，指针再减 1        self.top -= 1        return x

（5）读栈顶元素

    def get_top(self):  # 读栈顶元素        if self.top == -1:  # 栈空，报错            return        return self.data[self.top]

仅为读取栈顶元素，并没有出栈操作，因此原栈顶元素依然保存在栈中。

共享栈

利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。

两个栈的栈顶指针都指向栈顶元素，top0=-1 时 0 号栈为空，top1=max_size-1 时 1 号栈为空；仅当两个栈顶指针相邻（top1-top0=1）时，判断为栈满。当 0 号栈进栈时 top0 先加 1 再赋值，1 号栈进栈时 top1 先减 1 再赋值；出栈时则刚好相反。

共享栈是为了更有效地利用存储空间，两个栈的空间相互调节，只有在整个存储空间被占满时才发生上溢。其存取数据的时间复杂度均为 O(1)，所以对存取效率没有什么影响。

栈的链式存储结构

采用链式存储的栈称为链栈，链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。通常采用单链表实现，并规定所有操作都是在单链表的表头进行的。这里规定链栈没有头结点。

栈的链式存储类型可描述为：

class LiStack:  # 栈类型定义    def __init__(self, data):        self.data = data  # 数据域        self.next = None  # 指针域

采用链式存储，便于结点的插入与删除。链栈的操作与链表类似，入栈和出栈的操作都在链表的表头进行。需要注意的是，对于带头结点和不带头结点的链栈，具体的实现会有所不同。

总结

关于栈的定义以及基本操作的实现就介绍到这里，非常简单！下回我们看到栈的应用。