文档介绍：? 栈? 抽象数据类型栈的定义? 栈的表示与实现? 栈的应用举例? 数制转换? 迷宫求解? 表达式求值?* 栈和递归的实现? 队列? 抽象数据类型队列的定义? 链队列-- 队列的链式表示与实现? 循环队列-- 队列的顺序表示与实现栈和队列-操作受限的线性表 ADT ADT 栈的概念栈的概念??栈的定义:栈栈的定义:栈(Stack) (Stack) 是限制是限制在表的一端进行插入和删除运在表的一端进行插入和删除运算的线性表,通常称插入、删算的线性表,通常称插入、删除的这一端为栈顶除的这一端为栈顶 Top Top ,另一,另一端为栈底端为栈底 Bottom Bottom 。当表中没有。当表中没有元素时称为空栈。假设栈元素时称为空栈。假设栈 S=(a S=(a 1 1, ,a a 2 2, ,a a 3 3, ,……a a n n) ),则,则 a a 1 1称称为栈底元素, 为栈底元素, a a n n为栈顶元素。为栈顶元素。栈中元素按栈中元素按 a a 1 1,a ,a 2 2, ,a a 3 3, ,……a a n n的的次序进栈,退栈的第一个元素次序进栈,退栈的第一个元素应为栈顶元素应为栈顶元素, , 即栈的修改是即栈的修改是按后进先出的原则进行的。因按后进先出的原则进行的。因此栈又称为后进先出表此栈又称为后进先出表(LIFO) (LIFO) 。。栈的抽象数据类型 ADT Stack { 数据对象: D = { a i | a i属于 Elemset , (i=1,2, …,n, n ≥0)} 数据关系: R 1 = { <a i-1,a i>|a i-1,a i属于 D,(i=2,3, …,n)} 约定 a n为栈顶, a 1为栈底。基本操作: InitStack(&S ); DestroyStack(&S ); ClearStack(&S ); StackEmpty(S ); StackLength(S ) ; GetTop(S,&e ); Push(&S,e); Pop(&S,&e); StackTraverse(S,visit ()) }ADT Stack 栈的基本操作(之一) ?InitStack(&S ) ?操作结果:构造一个空的栈 S。?DestroyStack(&S ) ?初始条件: 栈S已经存在。?操作结果: 销毁栈 S。?ClearStack(&S ) ?初始条件: 栈S已经存在。?操作结果: 将栈 S重置为空栈。栈的基本操作(之二) ?StackEmpty(S ) ?初始条件: 栈S已经存在。?操作结果: 若栈 S 为空栈,则返回 TURE; 否则返回 FALSE 。?StackLength(S ) ?初始条件: 栈S已经存在。?操作结果: 返回栈 S中的数据元素个数。?GetTop(S,&e ) ?初始条件: 栈S已经存在且非空。?操作结果: 用e返回栈 S中栈顶元素的值。栈的基本操作(之三) ?Push(&S,e) ?初始条件: 栈S已经存在。?操作结果: 插入元素 e为新的栈顶元素。?Pop(&S,&e) ?初始条件: 栈S已经存在且非空。?操作结果: 删除 S的栈顶元素并用 e返回其值。?StackTraverse(S,visit ()) ?初始条件: 栈S已经存在且非空。?操作结果: 从栈底到栈顶依次对 S 的每个元素调用函数 visit () 。一旦 visit () 失败,则操作失败。 栈的顺序表示与实现---( 顺序栈) typedef struct { SElemType *base; /*在栈构造之前和销毁之后, base 的值为 NULL */ SElemType *top; /*栈顶指针*/int stacksize ; /*当前已分配的存储空间,以元素为单位*/ }SqStack ;#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define OK 1 #define OVERFLOW -1 #define ERROR 0 顺序栈示意图* base * top stacksize ...... a 1...a ia n * base * top stacksize 初始空栈* top = * base; stacksize = STACK_INIT_SIZE 顺序栈?空栈的栈顶指针指向栈底?非空栈中的