3.1 栈
视频二维码（扫码观看）
一、抽象数据类型栈的定义
1栈的概念
栈（Stack）：是限定仅在表的一端进行插入和删除操作的线性表。又称为后进先出LIFO（Last In First Out）或先进后出FILO（First In Last Out）线性表。
栈顶（Top）：允许进行插入、删除操作的一端，又称为表尾。用栈顶指针（top）来指示栈顶元素。
栈底（Bottom）：是固定端，又称为表头。
空栈：当栈中没有元素时称为空栈。
设栈S＝（a1，a2，…，an），则a1称为栈底元素，an为栈顶元素，如图3-1所示。
栈中元素按a1，a2，…，an的次序进栈，退栈的第一个元素应为栈顶元素。即栈的修改是按后进先出的原则进行的。
图3-1 顺序栈示意图
2栈的抽象数据类型定义
二、栈的表示和实现
栈的顺序存储结构简称为顺序栈，和顺序表相类似，用一维数组来存储栈。根据数组容量是否可以按需变化，又可分为静态顺序栈和动态顺序栈。
①静态顺序栈实现简单，但不能根据需要增大栈的存储空间；
②动态顺序栈可以根据需要增大栈的存储空间，但实现稍为复杂。
1栈的动态顺序存储表示
采用动态一维数组来存储栈。所谓动态，指的是栈的大小可以根据需要增加。
①用bottom表示栈底指针，栈底固定不变的；用top表示栈顶指针，栈顶则随着进栈和退栈操作而变化。
②用top＝bottom作为栈空的标记，每次top指向栈顶数组中的下一个存储位置。
③结点进栈：首先将数据元素保存到栈顶（top所指的当前位置），然后执行top加1，使top指向栈顶的下一个存储位置；
④结点出栈：首先执行top减1，使top指向栈顶元素的存储位置，然后将栈顶元素取出。
动态堆栈变化示意图如图3-2所示。
图3-2 （动态）堆栈变化示意图
视频二维码（扫码观看）
基本操作的实现：
①栈的类型定义
②栈的初始化
③压栈（元素进栈）
④弹栈（元素出栈）
2栈的静态顺序存储表示
采用静态一维数组来存储栈。
栈底固定不变的；栈顶则随着进栈和退栈操作而变化。
用top＝0表示栈空的初始状态，每次top指向栈顶在数组中的存储位置。
结点进栈：首先执行top加1，使top指向新的栈顶位置，然后将数据元素保存到栈顶（top所指的当前位置）。
结点出栈：首先把top指向的栈顶元素取出，然后执行top减1，使top指向新的栈顶位置。
若栈的最大容量为Maxsize，则top＝Maxsize－1时栈满。图3-3是一个大小为5的栈的变化示意图。
图3-3 静态堆栈变化示意图
基本操作的实现：
①栈的类型定义
②栈的初始化
③压栈（元素进栈）
④弹栈（元素出栈）
当栈满时做进栈运算必定产生空间溢出，简称“上溢”。上溢是一种出错状态，应设法避免。
当栈空时做出栈运算也将产生溢出，简称“下溢”。下溢则可能是正常现象，因为栈在使用时，其初态或终态都是空栈，所以下溢常用来作为控制转移的条件。
三、栈的链式存储表示
1栈的链式表示
栈的链式存储结构称为链栈，是运算受限的单链表。其插入和删除操作只能在表头位置上进行。因此，链栈没有必要像单链表那样附加头结点，栈顶指针top就是链表的头指针。图3-4是栈的链式存储表示形式。
图3-4 链栈存储形式
链栈的结点类型说明如下：
2链栈基本操作的实现
①栈的初始化
②压栈（元素进栈）
③弹栈（元素出栈）
