1、栈 队列 递归第三章栈和队列1栈 ( Stack )定义 :是限定仅在表尾进行插入或删除操作的线性表。允许插入和删除的一端称为栈顶 (top)，另一端称为栈底 (bottom)特点： 后进先出 (LIFO)a1topbottoman.进栈 出栈2栈的抽象数据类型定义为： ADT Stack 数据对象： D ai|aiElemSet,i=1,2,.,n, n0 数据关系： R1 | ai-1 , ai D, i=2,.,n 约定 an端为栈顶 ,a1端为栈底。基本操作：. ADT Stack 栈的抽象数据类型栈的抽象数据类型 （ C语言）语言）template class Stack publi
2、c:Stack ( int sz = 10 ); /构造函数void Push ( Type /进栈Type Pop ( ); /出栈Type GetTop ( ); /取栈顶元素void MakeEmpty ( ); /置空栈int IsEmpty ( ) const; /判栈空否int IsFull ( ) const; /判栈满否栈的抽象数据类型栈的抽象数据类型 （ C+）栈的表示和实现顺序栈： 栈的顺序存储结构，利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，指针 top指向栈顶元素在顺序栈中的下一个位置，base为栈底指针，指向栈底的位置。base空栈 a 进栈 b 进栈a
3、 abtop basetopbasetop5top topabcdee 进栈abcdef 进栈溢出abde 出 栈cbase basebasetop6顺序栈的定义及存储表示#define STACK_INIT_SIZE 100/栈存储空间的初始分配量#define STACKINCREMENT 10/ 栈存储空间的分配增量typedef structSElemType *base;/栈空间基址称为栈底指针，指向栈底位置SElemType *top /栈顶指针 ,约定栈顶指针指向栈顶元素的 /下（后面）一个位置； int stacksize; /当前分配的栈空间大小/（以 sizeof(SEle
4、mType)为单位）SqStack;/ SqStack:： 结构类型名7初始化操作参数： S是存放栈的结构变量功能：建立一个空栈 SStatus InitStack_Sq(SqStack /为顺序栈动态分配存储空间if (! S. base) exit(OVERFLOW); /存储分配失败S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK; /InitStack_Sq8取栈顶操作功能：取栈顶元素，并用 e返回Status GetTop_Sq(SqStack S, SelemType /若栈为空e = * (S.top-1);return OK;/GetTop_Sq9进栈操作 Push功能：元素 e进栈Status Push(SqStack if (! S. base) exit(OVERFLOW); /存储分配失败S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT; *S.top+=e; /元素 e 插入栈顶，修改栈顶指针return OK; /Push10
