ter栈和队列.ppt

算法与数据结构 2012.9-2013.1 主讲教师：张翠肖 联系方式：zhangcx@stdu.edu.cn 线性结构特点 概念：线性表，表长，空表，位序 线性表的顺序存储和链式存储 3.1 栈 3.2 栈的应用 3.3 栈与递归 3.4 队列 3.5 队列的应用 教学内容 第3章　栈和队列 掌握栈和队列的特点，并能在相应的应用问题中正确选用 熟练掌握栈的两种存储结构的基本操作实现算法，特别应注意栈满和栈空的条件 熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的条件 理解递归算法执行过程中栈的状态变化过程 教学目标 栈（Stack） 1. 定义 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式 队列（Queue） 1. 定义 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式 3.1 　栈 1. 定义 只能在表的一端（栈顶）进行插入和删除运算的线性表 只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则 4.运算规则 栈是一种特殊的线性表，它只能在表的一端（栈顶）进行插入和删除运算 栈与一般线性表的区别：仅在于运算规则不同 “进” ＝压入=PUSH（) “出” ＝弹出=POP( ) 栈与一般线性表的区别 “进” ＝压入=PUSH（) “出” ＝弹出=POP( ) 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) DestroyStack(S) ClearStack(S) StackEmpty(s) StackLength(S) GetTop(S, e) Push(S, e) Pop(S, e) StackTravers(S, visit()) } ADT Stack 基本操作： InitStack(S) 操作结果：构造一个空栈 S。DestroyStack(S) 初始条件：栈 S 已存在。 操作结果：栈 S 被销毁。 StackEmpty(S)初始条件：栈 S 已存在。操作结果：若栈 S 为空栈，则返回 TRUE，否则 FALSE。 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 … … 写入：v[i]= ai 读出： x= v[i] 压入：PUSH (an+1) 弹出： POP (x) 前提：一定要预设栈顶指针top！ an+1 顺序栈与顺序表 顺序栈的表示 空栈 base == top 是栈空标志 stacksize = 4 top 指示真正的栈顶元素之上的下标地址 栈满时的处理方法： 1、报错,返回操作系统。 2、分配更大的空间，作为栈的存储空间,将原栈的内容移入新栈。 #define MAXSIZE 100 typedef struct { SElemType *base; SElemType *top; int stacksize; }SqStack; 顺序栈的表示 构造一个空栈 步骤： (1)分配空间并检查空间是否分配失败，若失败则返回错误 顺序栈初始化 s (2)设置栈底和栈顶指针 S.top = S.base; (3)设置栈大小 Status InitStack( SqStack S ) { S.base =new SElemType[MAXSIZE]； if( !S.base ) return OVERFLOW; S.top = S.base; S.stackSize = MAXSIZE; return OK; } 顺序栈初始化 判断顺序栈是否为空 bool StackEmpty( SqStack S ) { if(S.top ==