资源描述：
《数据结构第三章栈和队列.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第三章栈和队列【学习目标】1.掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。2.熟练掌握栈类型的两种实现方法。3.熟练掌握循环队列和链队列的基本操作实现算法。4.理解递归算法执行过程中栈的状态变化过程。【重点和难点】栈和队列是在程序设计中被广泛使用的两种线性数据结构，因此本章的学习重点在于掌握这两种结构的特点，以便能在应用问题中正确使用。【知识点】顺序栈、链栈、循环队列、链队列【学习指南】在这一章中，主要是学习如何在求解应用问题中适当地应用栈和队列，栈和队列在两种存储结构中的实现都不难，但应该对它们了如指掌，特别要注意它们的基本操作实现时的一
2、些特殊情况，如栈满和栈空、队满和队空的条件以及它们的描述方法。本章要求必须完成的算法设计题为：3.15，3.17，3.19，3.22，3.28，3.30，3.31，3.32。其中前4个主要是练习栈的应用，后4个主要是有关队列的实现方法的练习。【课前思考】1.什么是线性结构？简单地说，线性结构是一个数据元素的序列。2.你见过餐馆中一叠一叠的盘子吗？如果它们是按1,2,…,n的次序往上叠的，那么使用时候的次序应是什么样的？必然是依从上往下的次序，即n,…,2,1。它们遵循的是"后进先出"的规律，这正是本章要讨论的"栈"的结构特点。3.在日常生活中，为了维持正常的社会秩序而出
3、现的常见现象是什么？是"排队"。在计算机程序中，模拟排队的数据结构是"队列"。[引言]栈和队列是两种操作受限的线性表，是两种常用的数据类型通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。线性表栈队列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.1.1栈的类型定义栈（Stack）是限定只能在
4、表的一端进行插入和删除操作的线性表。在表中，允许插入和删除的一端称作"栈顶(top)"，不允许插入和删除的另一端称作"栈底(bottom)"。其类型定义如下：ADTStack{数据对象：D＝{ai
5、ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{
6、ai-1,ai∈D,i=2,...,n}约定an端为栈顶，a1端为栈底。基本操作：InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果：栈S被销毁。ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈。S
7、tackEmpty(S)初始条件：栈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已存在且非空，visit()为元素的访问函数。操作结果：从栈底
8、到栈顶依次对S的每个元素调用函数visit()，一旦visit()失败，则操作失败。}ADTStack3.1.2栈的存储表示和操作的实现和线性表类似，栈也有两种存储表示，其顺序存储结构简称为顺序栈。一、顺序栈类型的定义//结构定义：typedefstruct{ElemType*base;//存储空间基址inttop;//栈顶指针intstacksize;//允许的最大存储空间以元素为单位}Stack;和顺序表类似，对顺序栈也需要事先为它分配一个可以容纳最多元素的存储空间，base为这个存储空间的基地址，也即一维数组的地址。从名称来讲，"栈顶指针"意为指示栈顶元素在栈中的
9、位置，但它的值实际是栈中元素的个数，和顺序表中的length值的意义相同。为了应用方便，这个"最大空间的容量"应由使用这个顺序栈的程序员决定，它的默认值和顺序表的默认值相同。用图表示顺序栈如下：图中的顺序栈的最大容量为7，当前栈中元素个数为4，因此，我们也可认为栈顶指针总是指在栈顶元素的后面一个位置上。//基本操作接口(函数声明)： voidInitStack(Stack&S，intmaxsize); // 构造一个最大存储容量为maxsize的空栈S。 voidDestroyStack(Stack&S); // 销毁栈S，S不再存在。
