Q.rearQ.frontQ.rearQ.frontQ.rearQ.frontQ.rearQ.front.ppt

第三章栈与队列￡ 栈￡ 栈的定义￡ 栈的顺序存储结构￡ 栈的链式存储结构￡ 栈的应用举例￡ 表达式求值￡ 迷宫求解￡ 数制转换￡ 括号匹配检验￡ 行编辑程序￡ 队列的顺序存储结构￡ 队列￡ 队列的定义￡ 队列的链式存储结构￡ 栈的定义￡ 栈栈( stack ):是限定仅在表尾进行插入和删除操作的线性表。又称为后进先出( last in first out )的线性表(简称 LIFO 结构)。栈顶( top ):栈表尾端。栈底( bottom ):栈表头端。),,,( 21naaaS?? naaa,,, 21? 1a na 例:假设栈,则称为栈底元素, 为栈顶元素。栈中元素按的次序进栈,退栈的第一个元素应为栈顶元素。如图 所示。出栈进栈栈顶 a n...a 2栈底 a 栈的示意图￡ 栈的顺序存储结构(1)定义顺序栈(即栈的顺序存储结构):是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针 top 指示栈顶元素在顺序栈中的位置。(2)C语言描述 typedef struct { SElemType * base; //栈底指针 SElemType * top; //栈顶指针 int stacksize ; //栈当前可使用的最大容量。} SqStack ;(3)图形表示 top base top base top base A A B C D E 图 栈的顺序存储结构示意图(4) ADT Stack 的表示和实现#define STACK_INIT_SIZE 100; //存储空间初始分配量#define STACKINCREMENT 10; //存储空间分配增量 typedef struct { SElemType * base; //在构造之前和销毁之后, //base 的值为 NULL SElemType * top; //栈顶指针 int stacksize ; //栈当前可使用的最大容量。} SqStack ; //----------------- 基本操作的函数原型说明------------------ Status InitStack ( SqStack &S); //构造一个空栈 S Status DestroyStack ( SqStack &S); //销毁栈 S,栈 S不再存在 Status ClearStack ( SqStack &S); //把S置为空栈 Status StackEmpty ( SqStack S); //若S为空栈,则返回 TRUE ,否则返回 FALSE Status StackLength ( SqStack S); //返回 S的元素个数,即栈的长度 Status GetTop ( SqStack S, SElemType &e); // 若栈不空,则用 e返回 S的栈顶元素,并返回 OK ;否则返回 ERROR Status Push ( SqStack &S, SElemType e); // 插入元素 e为新的栈顶元素 Status Pop ( SqStack &S, SElemType &e); // 若栈不空,则删除 S的栈顶元素,用 e返回其值,并返回 OK ;否则返回 ERROR Status StackTraverse ( SqStack S, Status ( * visit) () ); // 从栈底到栈顶依次对栈中每个元素调用函数 visit() 。一旦 visit() 失败,则操作失败 //----------------- 基本操作的算法描述(部分) ------------------ Status InitStack ( SqStack &S) { //构造一个空栈 S = ( SElemType *) malloc(STACK_INIT_SIZE * sizeof(ElemType )); if (! ) exit (OVERFLOW); //存储分配失败 = ; = STACK_INIT_SIZE; return OK; } // InitStack Status GetTop ( SqSta