数据结构课件ppt第三章.ppt

第三章栈和队列 栈和队列是操作受限的线性表 它们的基本操作是线性表操作的子集 栈是限定仅在表尾进行插入或删除操作的线性表 表尾端成为栈顶 表头端成为栈底 栈的修改是按后进先出的原则进行 栈又称为后进先出的线性表 栈和队列的示意图 栈只能在栈顶进行插入删除等操作 按照后进先出的原则 a1 a2 an 栈顶 栈底 进栈 出栈 a1 a2 a3 an 出队列 入队列 队头 队尾 队列 队尾进行插入操作 队头进行删除操作 线性表栈队列Insert L i x Insert S n 1 x Insert Q n 1 x 1 i n 1Delete L i Delete S n Delete Q 1 1 i n 栈和队列是两种常用的数据类型 栈 队列与线性表的插入 删除操作对比 3 1栈的类型定义 3 3栈的应用举例 3 2栈的表示与实现 3 4队列的类型定义 3 5队列类型的实现 3 1栈的类型定义 ADTStack 数据对象 D ai ai ElemSet i 1 2 n n 0 数据关系 R1 ai 1 ai D i 2 n 约定an端为栈顶 a1端为栈底 基本操作 ADTStack InitStack S DestroyStack S ClearStack S StackEmpty s StackLength S GetTop S e Push S e Pop S e StackTravers S visit InitStack S 操作结果 构造一个空栈S DestroyStack S 初始条件 栈S已存在 操作结果 栈S被销毁 StackEmpty S 初始条件 栈S已存在 操作结果 若栈S为空栈 则返回TRUE 否则FALE StackLength S 初始条件 栈S已存在 操作结果 返回S的元素个数 即栈的长度 GetTop S e 初始条件 栈S已存在且非空 操作结果 用e返回S的栈顶元素 a1 a2 an ClearStack S 初始条件 栈S已存在 操作结果 将S清为空栈 Push S e 初始条件 栈S已存在 操作结果 插入元素e为新的栈顶元素 a1 a2 an e Pop S e 初始条件 栈S已存在且非空 操作结果 删除S的栈顶元素 并用e返回其值 a1 a2 an an 1 栈的存储方法 顺序栈 利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素 同时附设指针top指示栈顶元素在顺序栈中的位置 链栈 头指针指向栈顶元素 每个结点的指针域指向前一个结点 顺序栈 top 栈顶指针 始终指向栈顶元素的下一个位置 base 栈底指针 始终指向栈底的位置 base NULL 栈不存在 base top 栈空 base top base top A B C D E F 链栈 注意 链栈中指针的方向 top a1 an an 1 链栈是动态分配元素存储空间 元素的插入删除操作都是在表的同一端进行 头指针就是栈顶指针 栈顶 栈底 3 2栈的表示和实现 栈的定义栈的几个基本操作的实现StatusInitStack SqStack S StatusPush SqStack S SElemTypee StatusPop SqStack S SElemType e 栈的顺序存储表示 defineSTACK INIT SIZE100 defineSTACKINCREMENT10typedefstruct SElemType base 构造栈之前和销毁栈之后 base值为NULLSElemType top 栈顶指针intstacksize 当前已分配的存储空间 以元素为单位 SqStack 类似于线性表的顺序映象实现 指向表尾的指针可以作为栈顶指针 StatusInitStack SqStack Statu