《堆栈和队列》PPT课件.ppt

第3章 限定性线性表堆栈和队列,3.1 堆栈,3.2 堆栈应用,3.4*优先级队列,栈和队列是两种重要的抽象数据类型，是一类操作受限制的特殊线性表，其特殊性在于限制插入和删除等运算的位置。,3.3 队列,第2页,3.1 堆 栈,3.1.1 堆栈的基本概念,堆栈的定义：限定只能在固定一端进行插入和删除操作的线性表。通常将表中允许进行插入、删除操作的一端称为栈顶(Top)，表的另一端被称为栈底(Bottom)。当栈中没有元素时称为空栈。栈的插入操作被形象地称为进栈或入栈，删除操作称为出栈或退栈。栈又称为后进先出的线性表，即LIFO。,第3页,根据栈定义，每次进栈的元素都被放在原栈顶元素之上而成为新的栈顶，而每次出栈的总是当前栈中“最新”的元素，即最后进栈的元素。因此，栈又称为后进先出的线性表。简称为LIFO表。如下图所示：,进栈、出栈图例,第4页,例3-1 利用一个堆栈，如果输入系列由A、B、C组成，试给出全部可能的输出系列和不可能的输出系列。输出系列有：ABC、ACB、BAC、BCA、CBA 不可能的输出系列为：CAB,第5页,3.1.2 栈的抽象数据类型定义,数据元素集合：描述为a0,a1,an-1，ai的数据类型为DataType。关系：栈中数据元素之间是线性关系。基本操作：(1)Initiate(S)初始化堆栈S(2)Push(S,x)入栈(3)Pop(S,d)出栈(4)GetTop(S)取栈顶数据元素(5)NotEmpty(S)堆栈S非空否,第6页,3.1.3 栈的表示和实现顺序堆栈类,栈在计算机中主要有两种基本的存储结构：顺序存储结构和链式存储结构。顺序存储的栈为顺序栈；链式存储的栈为链栈。,第7页,1.顺序堆栈的存储结构,顺序栈是用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时由于栈的操作的特殊性，还必须附设一个位置指针top（栈顶指针）来动态地指示栈顶元素在顺序栈中的位置。通常以top=0表示空栈。其结构如图所示：,其中，a0,a1,a2,a3,a4表示顺序堆栈中已存储的数据元素，stack表示存放数据元素的数组，MaxStackSize-1表示最大存储单元个数，top表示当前栈顶存储下标。,第8页,class SeqStackprivate:DataType dataMaxStackSize;/顺序堆栈数组int top;/栈顶位置指示器 public:SeqStack(void)top=0;/构造函数SeqStack(void)/析构函数void Push(const DataType item);/入栈DataType Pop(void);/出栈DataType GetTop(void)const;/取栈顶数据元素int NotEmpty(void)const/堆栈非空否return(top!=0);,2.顺序堆栈类的定义和实现,第9页,void SeqStack:Push(const DataType item)/入栈/把元素item入栈;堆栈满时出错退出if(top=MaxStackSize)cout堆栈已满!endl;exit(0);datatop=item;/先存储itemtop+;/然后top加1,第10页,DataType SeqStack:Pop()/出栈/出栈并返回栈顶元素;堆栈空时出错退出if(top=0)cout堆栈已空!endl;exit(0);top-;/top先减1return datatop;/然后取元素返回,第11页,DataType SeqStack:GetTop(void)const/取栈顶数据元素/取当前栈顶数据元素并返回if(top=0)cout堆栈空!endl;exit(0);return datatop-1;/返回当前栈顶元素,第12页,测试主程序如下：#include#include const int MaxStackSize=100;/定义问题要求的元素数目的最大值typedef int DataType;/定义具体问题元素的数据类型#include seqstack.h,3.顺序堆栈类的测试,void main(void)SeqStack myStack;/构造函数无参数时，定义的对象后不带括号DataType test=1,3,5,7,9;int n=5;for(int i=0;in;i+)myStack.Push(testi);while(myStack.NotEmpty()coutmyStack.Pop();程序运行输出结果为：9 7 5 3 1,第13页,3.1.4 链式堆栈类,1.链式堆栈 链式存储结构的堆栈。2.链式栈的存储结构 它是以头指针为栈顶，在头指针处插入或删除，其结构如图所示：,链栈中每个结点由两个域构成：data域和next域，其结点类和类定义分别如下：,template class LinStack;/前视定义，否则友元无法定义,第14页,/结点类 template/模板类型为T class StackNode friend class LinStack;/定义类LinStack为友元 private:T data;/数据元素 StackNode*next;/指针 public:/构造函数1，用语构造头结点StackNode(StackNode*ptrNext=NULL)next=ptrNext;/构造函数2，用于构造其他结点StackNode(const T,第15页,/链式堆栈类的定义template class LinStack private:StackNode*head;/头指针 int size;public:/数据元素个数public:LinStack(void);/构造函数LinStack(void);/析构函数void Push(const T,第16页,template LinStack:LinStack()/构造函数 head=new StackNode;/头指针指向头结点 size=0;/size的初值为0,template LinStack:LinStack(void)/析构函数/释放所有动态申请的结点空间 StackNode*p,*q;p=head;/p指向头结点while(p!=NULL)/循环释放结点空间 q=p;p=p-next;delete q;,第17页,template int LinStack:NotEmpty(void)const/堆栈非空否if(size!=0)return 1;else return 0;,template void LinStack:Push(const T/元素个数加1,第18页,template T LinStack:Pop(void)/出栈 if(size=0)cout*p=head-next;/p指向栈顶元素结点T data=p-data;head-next=head-next-next;/原栈顶元素结点脱链delete p;/释放原栈顶结点空间size-;/结点个数减1return data;/返回原栈顶结点的data域值,第19页,template T LinStack:GetTop(void)const/取栈顶元素return head-next-data;,说明：1)在链栈中的头结点对操作的实现影响不大，栈顶（表头）操作频繁，可不设头结点链栈。2)一般不会出现栈满情况；除非没有空间导致malloc分配失败。3)链栈的入栈、出栈操作就是栈顶的插入与删除操作，修改指针即可完成。4)采用链栈存储方式的优点是，可使多个栈共享空间；当栈中元素个数变化较大，且存在多个栈的情况下，链栈是栈的首选存储方式。,第20页,3.2 堆栈应用,1、括号匹配问题,例：假设一个算法表达式中包含圆括号、方括号和花括号三种类型的括号，编写一个判别表达式中括号是否正确配对的函数。设计思路：用栈暂存左括号,第21页,void ExpIsCorrect(char exp,int n)/判断有n个字符的字符串exp左右括号是否配对正确 SeqStack myStack;/定义顺序堆栈类对象myStack int i;for(i=0;in;i+)if(expi=()|(expi=)|(expi=)myStack.Push(expi);/入栈else if(expi=)/出栈,第22页,else if(expi=),第23页,else if(expi=,第24页,else if(expi=)|(expi=)|(expi=),第25页,2、表达式计算问题,表达式计算是编译系统中的基本问题，其实现方法是堆栈的一个典型应用。在编译系统中，要把便于人理解的表达式翻译成能正确求值的机器指令序列，通常需要先把表达式变换成机器便于理解的形式，这就要变换表达式的表示序列。,假设计算机高级语言中的一个算术表达式为 A+(B-C/D)*E,这种表达式称为中缀表达式，写成满足四则运算规则的相应的后缀表达式即为 ABCD/-E*+,第26页,表达式的三种标识方法：,设 Exp=S1+OP+S2,则称 OP+S1+S2 为前缀表示法,S1+OP+S2 为中缀表示法,S1+S2+OP 为后缀表示法,第27页,编译系统中表达式的计算分为两个步骤：（1）把中缀表达式变换成相应的后缀表达式；（2）根据后缀表达式计算表达式的值。后缀表达式的两个特点：（P72 6、7行）中缀表达式变换为后缀表达式的算法步骤可以总结为：(1)设置一个堆栈，初始时将栈顶元素置为“”。(2)顺序读入中缀表达式，当读到的单词为操作数时就将其输出，并接着读下一个单词。(3)令x1为当前栈顶运算符的变量，x2为当前扫描读到运算符的变量，当顺序从中缀表达式中读入的单词为运算符时就赋予x2，然后比较x1的优先级与x2的优先级。x1x2,x1退栈，写入后缀表达式中；x1=x2=#,算法结束。,第28页,利用堆栈计算后缀表达式值的函数编写如下：void PostExp(LinStack/x入栈,第29页,elsex2=s.Pop();/退栈得操作数x1=s.Pop();/退栈得被操作数switch(ch)case+:x1+=x2;break;case-:x1-=x2;break;case*:x1*=x2;break;case/:if(x2=0.0)cout除数为0错!;exit(0);,第30页,else x1/=x2;break;s.Push(x1);/运算结果入栈 cout s;PostExp(s);,第31页,3.3 队 列,1、队列的基本概念,(1)定义:只能在表的一端进行插入操作，在表的另一端进行删除操作的线性表。一个队列的示意图如下：,队列的特点：先进先出（FIFO）队列中允许进行插入操作的一端称为队尾；允许进行删除操作的一端称为队头。队头和队尾分别设定队头指示器和队尾指示器。队列的插入操作通常称为入队列；队列的删除操作通常称做出队列。,队尾插入,队头删除,第32页,2、队列抽象数据类型,数据集合:a0,a1,an-1，ai的数据类型为DataType。操作集合：(1)Initiate(Q)初始化队列Q(2)Append(Q,x)入队列(3)Delete(Q)出队列(4)GetFront(Q)取队头数据元素(5)NotEmpty(Q)队列Q非空否,第33页,3、顺序队列,(1)顺序队列 顺序存储结构的队列。(2)顺序队列的存储结构 下图是一个有6个存储空间的顺序队列的动态示意图,rear=,第34页,(3)顺序队列的“假溢出”问题,假溢出顺序队列因多次入队列和出队列操作后出现的有存储空间但不能进行入队列操作的溢出。如何解决顺序队列的假溢出问题？可采取四种方法：1)采用循环队列；2)按最大可能的进队操作次数设置顺序队列的最大元素个数；3)修改出队算法，使每次出队列后都把队列中剩余数据元素向队头方向移动一个位置；)修改入队算法，增加判断条件，当假溢出时，把队列中的数据元素向队头移动，然后方完成入队操作。,第35页,(4)顺序循环队列的基本原理 把顺序队列所使用的存储空间构造成一个逻辑上首尾相连的循环队列。当rear和front达到MaxQueueSize-1后，再前进一个位置就自动到。,第36页,(5)顺序循环队列的队空和队满判断问题（见P77图3-9）,第37页,新问题：在循环队列中，空队特征是front=rear；队满时也会有front=rear；判决条件将出现二义性！解决方案有三：使用一个计数器记录队列中元素个数（即队列长度）；判队满：count0&rear=front 判队空：count=0加设标志位，出队时置,入队时置,则可识别当前front=rear属于何种情况判队满：tag=1&rear=front 判队空：tag=0&rear=front 少用一个存储单元判队满：front=(rear+1)%MaxQueueSize 判队空：rear=front,第38页,4、顺序循环队列类,采用设置计数器方法来判断队空状态和队满状态，类定义如下:class SeqQueue private:DataType dataMaxQueueSize;/顺序队列数组 int front;/队头指示器 int rear;/队尾指示器 int count;/元素个数计数器 public:SeqQueue(void)/构造函数front=rear=0;count=0;SeqQueue(void)/析构函数 void Append(const DataType,第39页,void SeqQueue:Append(const DataType/计数器加1,第40页,DataType SeqQueue:Delete(void)/出队列/把队头元素出队列，出队列元素由函数返回if(count=0)cout队列已空!endl;exit(0);DataType temp=datafront;/保存原队头元素front=(front+1)%MaxQueueSize;/队头指示器加1count-;/计数器减1return temp;/返回原队头元素,第41页,DataType SeqQueue:GetFront(void)const/取队头数据元素/取队头元素并由函数返回if(count=0)cout队列已空!endl;exit(0);return dataFront;/返回队头元素,第42页,5、链式队列类,(1)链式队列 链式存储结构的队列。(2)链式队列的存储结构 链式队列的队头指针指向队列的当前队头结点;队尾指针指在队列的当前队尾结点,下图是一个不带头结点的链式队列的结构：,第43页,(3)链式队列类的定义及实现,结点类的定义和实现如下：template class LinQueue;/前视定义，否则友元无法定义template class QueueNode friend class LinQueue;/定义类LinQueue为友元private:QueueNode*next;/指针 T data;/数据元素 public:/构造函数QueueNode(const T,第44页,为了方便设计，增加了一个count域用来计算当前的元素个数 链式队列类的定义如下：template class LinQueue pprivate:QueueNode*front;/队头指针QueueNode*rear;/队尾指针 int count;/计数器 public:LinQueue(void);/构造函数LinQueue(void);/析构函数void Append(const T,第45页,链式队列类的实现如下：,template LinQueue:LinQueue()/构造函数front=rear=NULL;/链式队列无头结点count=0;/count的初值为0,第46页,template LinQueue:LinQueue(void)/析构函数QueueNode*p,*q;p=front;/p指向第一个结点while(p!=NULL)/循环直至全部结点空间释放q=p;p=p-next;delete q;count=0;/置为初始化值0front=rear=NULL;,第47页,template void LinQueue:Append(const T/计数器加1,第48页,template T LinQueue:Delete(void)/出队列/把队头结点删除并由函数返回 if(count=0)cout*p=front-next;/p指向新的队头结点T data=front-data;/保存原队头结点的data域值delete front;/释放原队头结点空间front=p;/front指向新的对头结点count-;/计数器减1return data;/返回原队头结点的data域值,第49页,template T LinQueue:GetFront(void)const/取队头数据元素if(count=0)coutdata;,第50页,6、队列的应用,例：编写判断一个字符序列是否是回文的函数。编程思想：设字符数组str中存放了要判断的字符串。把字符数组中的字符逐个分别存入队列和堆栈，然后逐个出队列和退栈并比较出队列的字符和退栈的字符是否相等，若全部相等则该字符序列是回文，否则就不是回文。设计函数如下：,第51页,void HuiWen(char str)LinStack myStack;LinQueue myQueue;int n=strlen(str);/求字符串长度for(int i=0;in;i+)myQueue.Append(stri);myStack.Push(stri);while(myQueue.NotEmpty(),第52页,3.4 优先级队列,、优先级队列带有优先级的队列。、顺序优先级队列用顺序存储结构存储的优先级队列。、优先级队列和一般队列的主要区别优先级队列的出队列操作不是把队头元素出队列，而是把队列中优先级最高的元素出队列。它的数据元素定义为如下结构体：struct DataType ElemType elem;/数据元素int priority;/优先级;注：顺序优先级队列除出队列操作外的其他操作的实现方法与前边讨论的顺序队列操作的实现方法相同。,第53页,出队列操作(把优先级最高的元素出队列并由函数返回,优先级相同时按先进先出的原则出队列),核心语句如下：DataType min=data0;/初始选data0为优先级最高的元素int minIndex=0;/minIndex为优先级最高元素的下标for(int i=1;icount;i+)/寻找优先级最高的元素及对应下标if(datai.prioritymin.priority)min=datai;minIndex=i;,第54页,例:设计一个程序模仿操作系统的进程管理进程。进程服务按优先级高的先服务、优先级相同的先到先服务的原则管理。模仿数据包括两部分:进程编号和优先级。一个模仿数据集合如下，其中第一列表示进程编号，第二列表示进程优先级:1 302 203 404 205 0,第55页,用顺序优先级队列可直接完成，核心语句如下：for(int i=0;in;i+)myQueue.Append(testi);cout任务号 优先级endl;for(i=0;in;i+)if(myQueue.NotEmpty()temp=myQueue.Delete();couttemp.elem;couttemp.priorityendl;,第56页,3.3 总结与提高,(1)基本概念 堆栈具有LIFO的特性，限定元素的运算位置只在表尾(栈顶)端进行；队列具有FIFO的特性，限定元素的运算位置分别在表的两端进行(2)顺序和链式两种存储方式(3)栈与队列的应用,第57页,1.设循环队列的容量为70（序号为1到70），现经过一系列的入队与出队运算后，有（1）front=14,rear=21;(2)front=23,rear=12请问在这两种情况下，循环队列中各有多少个元素？2.设栈s和队列q的初始状态为空，元素e1,e2,e3,e4,e5,e6依次通过栈s，一个元素出栈后即进入队列q，若出队的顺序为e2,e4,e3,e6,e5,e1，则栈s的容量至少应该是多少？课后作业：102页 3，4，12(1),(3),课堂练习：,