三章栈和队列.pptVIP

第三章 栈和队列 栈 栈的应用举例 队列 栈 ㈠栈： 在表的某一端进行插入和删除操作的 线性表。 特点： 后进先出 抽象数据数据类型的定义： ADT Stack { 数据对象:D={ai|ai∈ElemSet,i=1,2,…,n, n=0} 数据关系:R1={ai-1,ai|ai-1,ai∈D,i=2,…,n} 约定an端为栈顶，a1端为栈底 栈的示意图： 基本操作： InitStack (s) 操作结果：构造一个空栈S DestroyStack( s) 初始条件：栈S已存在 操作结果：栈S被销毁 ClearStack( s) 初始条件：栈S已存在 操作结果：将S清为空栈 StackEmpty(s ) 初始条件：栈S已存在 操作结果：若栈为空栈，则返回TRUE，否则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()失败，则操作失败 }ADT Stack 二：栈的表示与实现 栈的存储结构（两种） ⑴顺序存储结构 ⑵链式存储结构 1.顺序存储结构：利用一组地址连续的存储单元 依次存放自栈底到栈顶的数据 元素 结构描述：typedef struct { SElemType *base; SElemType *top; int stacksize; }SqStack; 图示： 规定：top指针指向下一个元素进栈的位置 空栈条件：S.top=S.base 栈满条件：S.top-S.base=S.stacksize 入栈： top指针增加1 出栈： top指针减1 栈的顺序存储表示： #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 StacjEmpty(SqStack s); //若栈S为空栈，则返回TRUE,否则返回FALSE Int StackLength(SqStack s); 返回S的元素个数，即栈的长度 StatusGetTop(SqStack s,SElemType e); //若栈 不为空，则用e返回S的栈顶元素，并返回OK;否则返回ERROR Status PUSH(SqStack s,SElemType e); //插入元素e为新的栈顶元素 Status POP(SqStack s,SE