1、* 栈* 栈的应用* 队列* 队列的应用3.1 栈栈3.1.1 栈的定义及基本运算栈 (Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶 (Top)，另一端为栈底 (Bottom)。当表中没有元素时称为空栈。假设栈 S=(a1， a2， a3， an)，则 a1称为栈底元素， an为栈顶元素。栈中元素按 a1， a2， a3， an的次序进栈，退栈的第一个元素应为栈顶元素。即，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（ LIFO） 。3.1.2 顺序栈由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。栈的顺序存储结构简称为顺序栈，它
2、是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量 top来指示当前栈顶的位置，通常称 top为栈顶指针。因此，顺序栈的类型定义只需将顺序表的类型定义中的长度属性改为 top即可 。顺序栈的类型定义如下：# define StackSize 100typedef char datatype;typedef struct datatype datastacksize;int top;seqstack; top6 5 4 3 2 1 0-1例、 一叠书或一叠盘子。栈的抽
3、象数据类型的定义如下：a na n-1a2a1栈顶栈底栈 s=(a1,a2, ,an)设 S是 SeqStack类型的指针变量。若栈底位置在向量的低端，即 sdata0是栈底元素，那么栈顶指针 stop是正向增加的，即进栈时需将 stop加 1，退栈时需将 stop 减 1。因此， stoptop =stacksize-1表示栈满。当栈满时再做进栈运算必定产生空间溢出，简称 “上溢 ”;当栈空时再做退栈运算也将产生溢出，简称 “下溢 ”。上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。1、置空栈、置空栈void initstack ( seqstack *s )s top = 0;2、判断栈空、判断栈空int stackempty ( seqstack *s )return ( s top = 0 );3、判断栈满、判断栈满int stackfull ( seqstack *s )return ( s top = stacksize - 1 );
