|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
栈是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构。栈的修改是按先进后出的原则进行的。因此，栈又称为先进后出（FILO，或后进先出）的线性表。栈进行插入和删除操作的一端称为栈顶，另一端称为栈底。不含数据元素的栈称为空栈。
|
|
|
|
|
|
.置空栈InitStack(S)：创建一个空栈S。
|
|
|
|
.判栈空Empty(S)：当栈S为空栈时返回真值；否则返回假值。
|
|
|
|
.入栈Push(S,x)：将元素x加入栈顶，并更新栈顶指针。
|
|
|
|
.出栈Pop(S)：将栈顶元素从栈中删除，并更新栈顶指针。若需要得到栈顶元素的值，可将Pop(S)定义为一个函数，它返回栈顶元素的值。
|
|
|
|
.读栈顶元素Top(S)：返回栈顶元素的值，但不修改栈顶指针。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
栈（Stack）是限定仅在表尾进行插入或删除操作的线性表。表尾端称为栈顶（Top），表头端称为栈底（Bottom）。故栈是后进先出（LIFO）的线性表。
|
|
|
|
若有桟S=（S0, S1, …, Sn-1），则S0称为栈底节点，Sn-1称为栈顶节点。通常称桟的节点的插入为进栈（Push），栈的节点的删除为出栈（Pop）。
|
|
|
|
|
|
|
|
.顺序栈即栈的顺序存储结构，是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时设指针top指示栈顶元素的当前位置。
|
|
|
|
.链栈即栈的链式存储结构，链表的第一个元素是栈顶元素，链表的末尾是栈底节点，链表的头指针就是栈顶指针，栈顶指针为空则是空栈。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
栈是只能在表的一端进行插入、删除的线性表。栈中允许插入、删除的一端称为栈顶，相反，栈中不允许插入、删除的一端称为栈底。处于栈顶位置的数据元素称为栈顶元素，不含任何数据元素的栈称为空栈。栈的特点为后进先出（Last In First Out, LIFO）。
|
|
|
|
下图是一个栈的示意图，通常用指针top指示栈顶的位置，用指针bottom指向桟底。栈顶指针top动态反映栈的当前位置。
|
|
|
|
|
|
|
|
|
|
|
|
.InitStack（&S）：初始化操作，构造一个空栈S。
|
|
|
|
.StackEmpty（S）：若栈S为空栈，返回1，否则返回0。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
栈的顺序存储用向量作为栈的存储结构，向量S表示栈，m表示栈的大小，用一栈指针top指向栈顶位置，S[top]表示栈顶元素，当在栈中进行插入、删除操作时，都要移动栈指针；而当top=m-1时，则栈满，当top=-1时，则栈空。同时为了避免浪费空间可以采用双栈机制，即向量的两端为栈底。
|
|
|
|
|
|
|
|
|
|
.由于C语言数组下标的范围是从0至StackSize-1，初始化设置为sq.top=-1。
|
|
|
|
.栈空条件为sq.top==-1，栈满条件为sq.top==StackSize-1。
|
|
|
|
|
|
.元素压栈的规则为：在栈不满时，先改变栈顶指针（top=top+1），再压栈。出栈时，在栈非空时，先取栈顶元素的值，再修改栈顶指针（top=top-1）。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
