文档介绍：Chap 3 2017 年1月20日星期五 1 1 Chap 3 2017 年1月20日星期五 2 2 从数据结构上看, 栈和队列也是线性表,不过是两种特殊的线性表。栈只允许在表的一端进行插入或删除操作,而队列只允许在表的一端进行插入操作、而在另一端进行删除操作。因而, 栈和队列也可以被称作为操作受限的线性表。通过本章的学****读者应能掌握栈和队列的逻辑结逻辑结构和存储结构构和存储结构,以及栈和队列的基本运算以及实基本运算以及实现算法。现算法。本章学****导读本章学****导读 Chap 3 2017 年1月20日星期五 3 3 栈抽象数据类型栈的定义栈的表示和实现顺序栈定义及基本操作链式栈定义及基本操作两个栈共享数组空间栈的应用举例数制转换括号匹配的检验行编辑程序表达式求值队列抽象数据类型队列的定义链队列-队列的顺序表示和实现循环队列-队列的顺序表示和实现本章重点内容本章重点内容 Chap 3 2017 年1月20日星期五 4 4 栈的逻辑结构空栈: 不含任何数据元素的栈。(a 1, a 2, ……, a n) 栈: (Stack )是限制仅在表的一端进行插入和删除运算的线性表。栈顶栈底允许插入和删除的一端称为栈顶(top) ,另一端称为栈底(bottom) 。 栈的定义及其运算 Chap 3 2017 年1月20日星期五 5 5a 1a 2a 3 入栈(push) 出栈(pop) 栈底栈顶插入:入栈、进栈、压栈删除:出栈、弹栈栈顶栈顶栈的示意图 栈的定义及其运算 Chap 3 2017 年1月20日星期五 6 6?栈的操作特性: 后进先出(LIFO) 修改原则:退栈者总是最近入栈者服务原则:后来者先服务(LIFO 表) a 1a 2a 3 入栈出栈栈底栈顶插入:入栈、进栈、压栈删除:出栈、弹栈栈顶栈的示意图 栈的定义及其运算 Chap 3 2017 年1月20日星期五 7 7 a 0a 1a n-1 入栈出栈栈顶 top 栈底 bottom 图3-3 栈的示意图图3-3 是一个栈的示意图,通常用指针 top 指示栈顶的位置,用指针 bottom 指向栈底。栈顶指针 top 动态反映栈的当前位置。 Chap 3 2017 年1月20日星期五 8 8 ADT Stack {数据对象: D= { a i | a i ∈ ElemSet, i=1,2,...,n, n≥0 } 数据关系: R1 = { <a i-1, a i >| a i-1, a i∈ D, i=2,...,n }约定 a n端为栈顶, a 1 端为栈底。基本操作: } ADT Stack 基本操作 InitStack(&S) DestroyStack(&S) StackLength(S) StackEmpty(s) GetTop(S, &e) ClearStack(&S) Push(&S, e) Pop(&S, &e) StackTravers(S, visit()) Chap 3 2017 年1月20日星期五 9 9 顺序栈:栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。①顺序栈中元素用数组存放; ②栈底位置是固定不变的,可设置在数组两端的任意一个端点;例如设在下标值大的一端; ③栈顶位置是随着进栈和退栈操作而变化的,用一个整型量 top (通常称 top 为栈顶指针)来指示当前栈顶位置;④“上溢”现象:栈已满还要执行 Push() 操作或 top 指向超过数组的最大值;⑤“下溢”现象:没有栈元素时还要执行 Pop() 或 getTop() 操作; 栈的表示和实现? 1、顺序存储 Chap 3 2017 年1月20日星期五 10 10 类似于线性表的顺序映象实现, 顺序栈的类型定义只需将顺序表的类型定义中的长度属性(length) 改为 top 即可。//----- 栈的顺序存储表示----- #define STACK_INIT_SIZE 100; #define STACKINCREMENT 10; typedef struct { ElemType elem[ STACK_INIT_SIZE ] int top ; //存放指向栈顶的指针} SqStack ; 栈的表示和实现? 1、顺序存储