堆栈和队列ppt课件

1、第第3章章 限定性线性表限定性线性表堆栈和队列堆栈和队列3.1 3.1 堆栈堆栈3.2 3.2 堆栈运用堆栈运用3.43.4* * 优先级队列优先级队列 栈和队列是两种重要的笼统数据类型，是一类栈和队列是两种重要的笼统数据类型，是一类操作受限制的特殊线性表，其特殊性在于限制插入操作受限制的特殊线性表，其特殊性在于限制插入和删除等运算的位置。和删除等运算的位置。3.3 3.3 队列队列3.1 3.1 堆堆 栈栈3.1.1 3.1.1 堆栈的根本概念堆栈的根本概念 堆栈的定义：限定只能在固定一堆栈的定义：限定只能在固定一端进展插入和删除操作的线性表。端进展插入和删除操作的线性表。 通常将表中允许进

2、展插入、删除通常将表中允许进展插入、删除操作的一端称为栈顶操作的一端称为栈顶 (Top)，表的另，表的另一端被称为栈底一端被称为栈底 (Bottom)。 当栈中没有元素时称为空栈。栈当栈中没有元素时称为空栈。栈的插入操作被笼统地称为进栈或入栈，的插入操作被笼统地称为进栈或入栈，删除操作称为出栈或退栈。栈又称为删除操作称为出栈或退栈。栈又称为后进先出的线性表，即后进先出的线性表，即LIFO。 根据栈定义，每次进栈的元素都被放在原栈根据栈定义，每次进栈的元素都被放在原栈顶元素之上而成为新的栈顶，而每次出栈的总是顶元素之上而成为新的栈顶，而每次出栈的总是当前栈中当前栈中“最新的元素，即最后进栈的元素

3、。因最新的元素，即最后进栈的元素。因此，栈又称为后进先出的线性表。简称为此，栈又称为后进先出的线性表。简称为LIFO表。表。如以下图所示：如以下图所示： 进栈、出栈图例进栈、出栈图例进栈进栈出栈出栈ana2a1进栈进栈出栈出栈栈顶栈顶栈底栈底 例3-1 利用一个堆栈，假设输入系列由A、B、C组成，试给出全部能够的输出系列和不能够的输出系列。 输出系列有： ABC、ACB、BAC、BCA、CBA 不能够的输出系列为： CAB3.1.2 栈的笼统数据类型定义栈的笼统数据类型定义数据元素集合：描画为数据元素集合：描画为a0,a1,an-1，ai的数据类型为的数据类型为DataType。 关系：栈中数

4、据元素之间是线性关系。关系：栈中数据元素之间是线性关系。 根本操作：根本操作： (1)Initiate(S) 初始化堆栈初始化堆栈S (2)Push(S,x) 入栈入栈 (3)Pop(S,d) 出栈出栈 (4)GetTop(S) 取栈顶数据元素取栈顶数据元素 (5)NotEmpty(S) 堆栈堆栈S非空否非空否3.1.3 栈的表示和实现栈的表示和实现顺序堆栈类顺序堆栈类 栈在计算机中主要有两种根本的存储构造：栈在计算机中主要有两种根本的存储构造： 顺序存储构造和链式存储构造。顺序存储构造和链式存储构造。 顺序存储的栈为顺序栈；顺序存储的栈为顺序栈； 链式存储的栈为链栈。链式存储的栈为链栈。1.

5、1.顺序堆栈的存储构造顺序堆栈的存储构造 顺序栈是用顺序存储构造实现的栈，即利用顺序栈是用顺序存储构造实现的栈，即利用一组地址延续的存储单元依次存放自栈底到栈顶的一组地址延续的存储单元依次存放自栈底到栈顶的数据元素，同时由于栈的操作的特殊性，还必需附数据元素，同时由于栈的操作的特殊性，还必需附设一个位置指针设一个位置指针top栈顶指针来动态地指示栈栈顶指针来动态地指示栈顶元素在顺序栈中的位置。通常以顶元素在顺序栈中的位置。通常以top = 0表示空栈。表示空栈。其构造如下图：其构造如下图：a0 a1 a2 a3 a4stack栈底栈顶MaxStackSize-1012345=top 其中，其中

6、，a0, a1, a2, a3, a4表示顺序堆栈中已存储的数据元表示顺序堆栈中已存储的数据元素，素，stack表示存放数据元素的数组，表示存放数据元素的数组，MaxStackSize-1表示最表示最大存储单元个数，大存储单元个数，top表示当前栈顶存储下标。表示当前栈顶存储下标。class SeqStackprivate:DataType dataMaxStackSize; /顺序堆栈数组顺序堆栈数组int top; /栈顶位置指示器栈顶位置指示器 public:SeqStack(void) top=0; /构造函数构造函数SeqStack(void) /析构函数析构函数void Push(

7、const DataType item); /入栈入栈DataType Pop(void); /出栈出栈DataType GetTop(void)const; /取栈顶数据元素取栈顶数据元素int NotEmpty(void)const /堆栈非空否堆栈非空否return(top!=0);2.2.顺序堆栈类的定义和实现顺序堆栈类的定义和实现void SeqStack:Push(const DataType item) /入栈入栈/把元素把元素item入栈入栈;堆栈满时出错退出堆栈满时出错退出if(top=MaxStackSize)cout堆栈已满堆栈已满!endl;exit(0);datato

8、p=item; /先存储先存储itemtop+; /然后然后top加加1DataType SeqStack:Pop() /出栈出栈/出栈并前往栈顶元素出栈并前往栈顶元素;堆栈空时出错退出堆栈空时出错退出if(top=0)cout堆栈已空堆栈已空!endl;exit(0);top-; /top先减先减1return datatop; /然后取元素前往然后取元素前往DataType SeqStack:GetTop(void)const /取栈顶数据元素取栈顶数据元素/取当前栈顶数据元素并前往取当前栈顶数据元素并前往if(top=0)cout堆栈空堆栈空!endl;exit(0);return da

9、tatop-1; /前往当前栈顶元素前往当前栈顶元素测试主程序如下：测试主程序如下：#include #include const int MaxStackSize=100; /定义问题要求的元素数目的最大值定义问题要求的元素数目的最大值typedef int DataType; /定义详细问题元素的数据类型定义详细问题元素的数据类型#include seqstack.h3. 3. 顺序堆栈类的测试顺序堆栈类的测试void main(void) SeqStack myStack; /构造函数无参数时，定义的对象后不带括号构造函数无参数时，定义的对象后不带括号DataType test=1,3,

10、5,7,9;int n=5;for(int i=0;in;i+)myStack.Push(testi);while(myStack.NotEmpty()coutmyStack.Pop() ;程序运转输出结果为：程序运转输出结果为：9 7 5 3 13.1.4 3.1.4 链式堆栈类链式堆栈类1.1.链式堆栈链式堆栈 链式存储构造的堆栈。链式存储构造的堆栈。2.2.链式栈的存储构造链式栈的存储构造 它是以头指针为栈顶，在头指针处插入或删除，其构造它是以头指针为栈顶，在头指针处插入或删除，其构造如下图：如下图：头结点an-1an-2a0h栈底栈顶链栈中每个结点由两个域构成：链栈中每个结点由两个域构

11、成：datadata域和域和nextnext域，其结点域，其结点类和类定义分别如下：类和类定义分别如下：template class LinStack; /前视定义，否那么友元无法定义前视定义，否那么友元无法定义/结点类结点类 template /模板类型为模板类型为T class StackNode friend class LinStack ; /定义类定义类LinStack为友元为友元 private: T data; /数据元素数据元素 StackNode *next; /指针指针 public:/构造函数构造函数1，用语构造头结点，用语构造头结点StackNode(StackNode

12、 *ptrNext=NULL) next=ptrNext;/构造函数构造函数2，用于构造其他结点，用于构造其他结点StackNode(const T& item,StackNode *ptrNext=NULL) data=item;next=ptrNext;StackNode();/链式堆栈类的定义链式堆栈类的定义template class LinStack private: StackNode *head; /头指针头指针 int size; public: /数据元素个数数据元素个数public: LinStack(void); /构造函数构造函数LinStack(void) ;

13、 /析构函数析构函数void Push(const T& item); /入栈入栈T Pop(void); /出栈出栈T GetTop(void) const; /取栈顶元素取栈顶元素int NotEmpty(void) const; /堆栈非空否堆栈非空否;template LinStack :LinStack() /构造函数构造函数 head=new StackNode ; /头指针指向头结点头指针指向头结点 size=0; /size的初值为的初值为0 template LinStack :LinStack(void) /析构函数析构函数/释放一切动态恳求的结点空间释放一切动态恳

14、求的结点空间 StackNode *p,*q;p=head; /p指向头结点指向头结点while(p!=NULL) /循环释放结点空间循环释放结点空间 q=p; p=p-next; delete q;template int LinStack :NotEmpty(void) const /堆栈非空否堆栈非空否if(size!=0) return 1;else return 0;template void LinStack :Push(const T& item) /入栈入栈/新结点新结点newNode的的data域值为域值为item,next域值为域值为head-nextStackNo

15、de *newNode=new StackNode (item,head-next);head-next=newNode; /新结点插入栈顶新结点插入栈顶size+; /元素个数加元素个数加1template T LinStack :Pop(void) /出栈出栈 if(size=0) cout堆栈已空无元素可删堆栈已空无元素可删!endl; exit(0); StackNode *p=head-next; /p指向栈顶元素结点指向栈顶元素结点T data=p-data;head-next=head-next-next; /原栈顶元素结点脱链原栈顶元素结点脱链delete p; /释放原栈顶结

16、点空间释放原栈顶结点空间size-; /结点个数减结点个数减1return data; /前往原栈顶结点的前往原栈顶结点的data域值域值template T LinStack :GetTop(void) const /取栈顶元素取栈顶元素return head-next-data;阐明：阐明：1)在链栈中的头结点对操作的实现影响不大，栈顶表头在链栈中的头结点对操作的实现影响不大，栈顶表头操作频繁，可不设头结点链栈。操作频繁，可不设头结点链栈。2)普通不会出现栈满情况；除非没有空间导致普通不会出现栈满情况；除非没有空间导致malloc分配分配失败。失败。3)链栈的入栈、出栈操作就是栈顶的插入与

17、删除操作，修链栈的入栈、出栈操作就是栈顶的插入与删除操作，修正指针即可完成。正指针即可完成。4)采用链栈存储方式的优点是，可使多个栈共享空间；当采用链栈存储方式的优点是，可使多个栈共享空间；当栈中元素个数变化较大，且存在多个栈的情况下，链栈中元素个数变化较大，且存在多个栈的情况下，链栈是栈的首选存储方式。栈是栈的首选存储方式。3.2 3.2 堆栈运用堆栈运用1、括号匹配问题、括号匹配问题例：假设一个算法表达式中包含圆括号、方括号和花例：假设一个算法表达式中包含圆括号、方括号和花括号三种类型的括号，编写一个判别表达式中括号能括号三种类型的括号，编写一个判别表达式中括号能否正确配对的函数。否正确配

18、对的函数。设计思绪：用栈暂存左括号设计思绪：用栈暂存左括号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 = ) &myStack.NotEmpty()&myStack.GetTop()=()myStack.P

19、op(); /出栈出栈else if(expi=)&myStack.NotEmpty()&myStack.GetTop()!=() cout左、右括号配对次序不正确左、右括号配对次序不正确!endl; return;else if(expi = &myStack.NotEmpty()&myStack.GetTop()=)myStack.Pop(); /出栈出栈else if(expi=&myStack.NotEmpty()&myStack.GetTop()!=)cout左、右括号配对次序不正确左、右括号配对次序不正确!endl;return;el

20、se if(expi = &myStack.NotEmpty()&myStack.GetTop()=)myStack.Pop(); /出栈出栈else if(expi=&myStack.NotEmpty()&myStack.GetTop()!=) cout左、右括号配对次序不正确左、右括号配对次序不正确!endl; return;else if(expi=)|(expi=)|(expi=)&!myStack.NotEmpty()cout右括号多于左括号右括号多于左括号!endl;return;if(myStack.NotEmpty()cout左括号多于右

21、括号左括号多于右括号!endl;elsecout左、右括号匹配正确左、右括号匹配正确!endl;2、表达式计算问题、表达式计算问题 表达式计算是编译系统中的根本问题，其实现方法是堆表达式计算是编译系统中的根本问题，其实现方法是堆栈的一个典型运用。在编译系统中，要把便于人了解的表达栈的一个典型运用。在编译系统中，要把便于人了解的表达式翻译成能正确求值的机器指令序列，通常需求先把表达式式翻译成能正确求值的机器指令序列，通常需求先把表达式变换成机器便于了解的方式，这就要变换表达式的表示序列。变换成机器便于了解的方式，这就要变换表达式的表示序列。假设计算机高级言语中的一个算术表达式为假设计算机高级言语

22、中的一个算术表达式为 A+(B-C/D)A+(B-C/D)* *E E这种表达式称为中缀表达式，写成满足四那么运算规那么的相应这种表达式称为中缀表达式，写成满足四那么运算规那么的相应的后缀表达式即为的后缀表达式即为 ABCD/-E*+ 表达式的三种标识方法：设设 Exp = S1 + OP + S2那么称那么称 OP + S1 + S2 为前缀表示法为前缀表示法 S1 + OP + S2 为中缀表示法 S1 + S2 + OP 为后缀表示法 编译系统中表达式的计算分为两个步骤：编译系统中表达式的计算分为两个步骤： 1 1把中缀表达式变换成相应的后缀表达式；把中缀表达式变换成相应的后缀表达式；

23、2 2根据后缀表达式计算表达式的值。根据后缀表达式计算表达式的值。后缀表达式的两个特点：后缀表达式的两个特点： P72 6P72 6、7 7行行中缀表达式变换为后缀表达式的算法步骤可以总结为：中缀表达式变换为后缀表达式的算法步骤可以总结为： (1) (1)设置一个堆栈，初始时将栈顶元素置为设置一个堆栈，初始时将栈顶元素置为“。 (2) (2)顺序读入中缀表达式，当读到的单词为操作数时就将其输出，顺序读入中缀表达式，当读到的单词为操作数时就将其输出，并接着读下一个单词。并接着读下一个单词。 (3) (3)令令x1x1为当前栈顶运算符的变量，为当前栈顶运算符的变量，x2x2为当前扫描读到运算符的为

24、当前扫描读到运算符的变量，当顺序从中缀表达式中读入的单词为运算符时就赋予变量，当顺序从中缀表达式中读入的单词为运算符时就赋予x2x2，然，然后比较后比较x1x1的优先级与的优先级与x2x2的优先级。的优先级。x1x2,x2x1x2,x1x1x2,x1退栈，退栈，写入后缀表达式中；写入后缀表达式中；x1=x2=#,x1=x2=#,算法终了。算法终了。 利用堆栈计算后缀表达式值的函数编写如下：利用堆栈计算后缀表达式值的函数编写如下：void PostExp(LinStack &s)char ch; /ch为为char类型变量类型变量T x,x1,x2;coutch&ch!=#) /

25、循环直到输入为循环直到输入为#if(isdigit(ch) /ch为数字类型为数字类型 cin.putback(ch); /回退一位回退一位cinx; /按数值类型重新输入按数值类型重新输入s.Push(x); /x入栈入栈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);else x1/=x2; break; s.P

26、ush(x1); /运算结果入栈运算结果入栈 cout后缀表达式计算结果为后缀表达式计算结果为:s.Pop()endl;void main() LinStack s; PostExp(s);3.3 3.3 队队 列列1、队列的根本概念、队列的根本概念(1)(1)定义定义: :只能在表的一端进展插入操作，在表的另一端进展只能在表的一端进展插入操作，在表的另一端进展删除操作的线性表。一个队列的表示图如下：删除操作的线性表。一个队列的表示图如下：队列的特点：先进先出队列的特点：先进先出FIFO队列中允许进展插入操作的一端称为队尾；队列中允许进展插入操作的一端称为队尾； 允许进展删除操作的一端称为队头

27、。允许进展删除操作的一端称为队头。队头和队尾分别设定队头指示器和队尾指示器。队头和队尾分别设定队头指示器和队尾指示器。队列的插入操作通常称为入队列；队列的插入操作通常称为入队列；队列的删除操作通常称做出队列。队列的删除操作通常称做出队列。队尾插队尾插入入队头删队头删除除a0a1a2an-1队头队头队尾队尾2、队列笼统数据类型、队列笼统数据类型数据集合数据集合:a0,a1,an-1，ai的数据类型为的数据类型为DataType。操作集合：操作集合：(1)Initiate(Q) 初始化队列初始化队列Q (2)Append(Q,x) 入队列入队列 (3)Delete(Q) 出队列出队列 (4)Get

28、Front(Q) 取队头数据元素取队头数据元素 (5)NotEmpty(Q) 队列队列Q非空否非空否3 3、顺序队列、顺序队列(1)(1)顺序队列顺序队列 顺序存储构造的队列。顺序存储构造的队列。(2)(2)顺序队列的存储构造顺序队列的存储构造 以下图是一个有以下图是一个有6 6个存储空间的顺序队列的动态表示图个存储空间的顺序队列的动态表示图(a)空队列空队列front rear=012345CBA(b)入队列入队列A、B、C后的形状后的形状front =012345C(c)出队列出队列A、B后的形状后的形状front=012345rear =EDC(d)入队列入队列D、E后的形状后的形状fr

29、ont=012345rear =rear =(3)(3)顺序队列的顺序队列的“假溢出问题假溢出问题假溢出假溢出顺序队列因多次入队列和出队列操作后出现的有顺序队列因多次入队列和出队列操作后出现的有存储空间但不能进展入队列操作的溢出。存储空间但不能进展入队列操作的溢出。如何处理顺序队列的假溢出问题？如何处理顺序队列的假溢出问题？可采取四种方法：可采取四种方法：1)1)采用循环队列；采用循环队列； 2) 2)按最大能够的进队操作次数设置顺序队列的最大按最大能够的进队操作次数设置顺序队列的最大元素个数；元素个数； 3) 3)修正出队算法，使每次出队列后都把队列中剩余修正出队算法，使每次出队列后都把队列

30、中剩余数据元素向队头方向挪动一个位置；数据元素向队头方向挪动一个位置；) )修正入队算法，添加判别条件，当假溢出时，把修正入队算法，添加判别条件，当假溢出时，把队列中的数据元素向队头挪动，然后方完成入队操队列中的数据元素向队头挪动，然后方完成入队操作。作。(4)(4)顺序循环队列的根本原理顺序循环队列的根本原理 把顺序队列所运用的存储空间构呵斥一个逻辑上首尾相连把顺序队列所运用的存储空间构呵斥一个逻辑上首尾相连的循环队列。当的循环队列。当rearrear和和frontfront到达到达MaxQueueSize-1MaxQueueSize-1后，再前后，再前进一个位置就自动到。进一个位置就自动到

31、。a3a2a1frontrear 0 1 2 3 . .N-1a3a2a10123N-1rearfront(5)顺序循环队列的队空和队满判别问题见顺序循环队列的队空和队满判别问题见P77图图3-91 14 40 02 23 35 5frontrear(a)(a)入队前入队前空队列空队列1 14 40 02 23 35 5e6e6e7e7e8e8e4e4e3e3e5e5frontrear(b) (b) 队列满队列满时时1 14 40 02 23 35 5e4e4e3e3e5e5frontrear(c) (c) 普通情况普通情况思索出对后思索出对后情况情况新问题：在循环队列中，空队特征是新问题：在

32、循环队列中，空队特征是front=rear；队；队满时也会有满时也会有front=rear；判决条件将出现二义性！；判决条件将出现二义性！处理方案有三：处理方案有三：运用一个计数器记录队列中元素个数即队列长运用一个计数器记录队列中元素个数即队列长度；度；判队满：判队满：count0 & rear=front 判队空：判队空：count=0加设标志位，出队时置加设标志位，出队时置,入队时置入队时置,那么可识别那么可识别当前当前front=rear属于何种情况属于何种情况判队满：判队满：tag=1 & rear=front 判队空：判队空：tag=0 & rear=fron

33、t 少用一个存储单元少用一个存储单元判队满：判队满： front=(rear+1)%MaxQueueSize 判队空：判队空： rear=front4 4、顺序循环队列类、顺序循环队列类采用设置计数器方法来判别队空形状和队满形状，类定义如下采用设置计数器方法来判别队空形状和队满形状，类定义如下: :class SeqQueue class SeqQueue private: private: DataType dataMaxQueueSize; /DataType dataMaxQueueSize; /顺序队列数组顺序队列数组 int front; /int front; /队头指示器队头指示

34、器 int rear; /int rear; /队尾指示器队尾指示器 int count; /int count; /元素个数计数器元素个数计数器 public: public: SeqQueue(void) /SeqQueue(void) /构造函数构造函数front=rear=0;count=0; front=rear=0;count=0; SeqQueue(void) /SeqQueue(void) /析构函数析构函数 void Append(const DataType& item); /void Append(const DataType& item); /入队列入队

35、列 DataType Delete(void); /DataType Delete(void); /出队列出队列 DataType GetFront(void)const; /DataType GetFront(void)const; /取队头数据元素取队头数据元素 int NotEmpty(void)const /int NotEmpty(void)const /非空否非空否 return count!=0;return count!=0;void SeqQueue:Append(const DataType& item) /入队列入队列/把数据元素把数据元素item插入队列作为当前

36、的新队尾插入队列作为当前的新队尾if(count0&front=rear)cout队列已满队列已满!endl;exit(0);datarear=item; /把元素把元素item加在队尾加在队尾rear=(rear+1) % MaxQueueSize; /队尾指示器加队尾指示器加1cout+; /计数器加计数器加1DataType SeqQueue:Delete(void) /出队列出队列/把队头元素出队列，出队列元素由函数前往把队头元素出队列，出队列元素由函数前往if(count=0)cout队列已空队列已空!endl;exit(0);DataType temp=datafront;

37、 /保管原队头元素保管原队头元素front=(front+1) % MaxQueueSize; /队头指示器加队头指示器加1count-; /计数器减计数器减1return temp; /前往原队头元素前往原队头元素DataType SeqQueue:GetFront(void)const /取队头数据元素取队头数据元素/取队头元素并由函数前往取队头元素并由函数前往if(count=0)cout队列已空队列已空!endl;exit(0);return dataFront; /前往队头元素前往队头元素5 5、链式队列类、链式队列类(1)(1)链式队列链式队列 链式存储构造的队列。链式存储构造的队

38、列。(2)(2)链式队列的存储构造链式队列的存储构造 链式队列的队头指针指向队列的当前队头结链式队列的队头指针指向队列的当前队头结点点; ;队尾指针指在队列的当前队尾结点队尾指针指在队列的当前队尾结点, ,以下图以下图是一个不带头结点的链式队列的构造：是一个不带头结点的链式队列的构造：a0a1an-1an-1frontrear(3)(3)链式队列类的定义及实现链式队列类的定义及实现结点类的定义和实现如下：结点类的定义和实现如下：template template class LinQueue;/class LinQueue;/前视定义，否那么友元无法定义前视定义，否那么友元无法定义templa

39、te template class QueueNodeclass QueueNode friend class LinQueue ; /friend class LinQueue ; /定义类定义类LinQueueLinQueue为友元为友元private: private: QueueNode QueueNode * *next; /next; /指针指针 T data; /T data; /数据元素数据元素 public: public: / /构造函数构造函数QueueNode(const T& item,QueueNode QueueNode(const T& item

40、,QueueNode * *ptrNext=NULL)ptrNext=NULL):data(item),next(ptrNext):data(item),next(ptrNext)QueueNode(); /QueueNode(); /析构函数析构函数;为了方便设计，添加了一个为了方便设计，添加了一个countcount域用来计算当前的元素个数域用来计算当前的元素个数 链式队列类的定义如下：链式队列类的定义如下：template template class LinQueue class LinQueue pprivate: pprivate: QueueNode QueueNode * *f

41、ront; /front; /队头指针队头指针QueueNode QueueNode * *rear; /rear; /队尾指针队尾指针 int count; /int count; /计数器计数器 public: public: LinQueue(void); /LinQueue(void); /构造函数构造函数LinQueue(void); /LinQueue(void); /析构函数析构函数void Append(const T& item); /void Append(const T& item); /入队列入队列 T Delete(void); /T Delete(v

42、oid); /出队列出队列 T GetFront(void)const; /T GetFront(void)const; /取队头数据元素取队头数据元素int NotEmpty(void)const /int NotEmpty(void)const /非空否非空否return count!=0;return count!=0;链式队列类的实现如下：链式队列类的实现如下：template LinQueue :LinQueue() /构造函数构造函数front=rear=NULL; /链式队列无头结点链式队列无头结点count=0; /count的初值为的初值为0template LinQueue

43、 :LinQueue(void) /析构函数析构函数QueueNode *p,*q;p=front; /p指向第一个结点指向第一个结点while(p!=NULL) /循环直至全部结点空间释放循环直至全部结点空间释放q=p;p=p-next;delete q;count=0; /置为初始化值置为初始化值0front=rear=NULL;template void LinQueue :Append(const T& item) /入队列入队列/把数据元素把数据元素item插入队列作为新队尾结点插入队列作为新队尾结点/构造新结点构造新结点newNode，newNode的的data域值为域值为

44、item，next域值为域值为NULLQueueNode *newNode=new QueueNode (item,NULL);if(rear!=NULL) rear-next=newNode; /新结点链入新结点链入rear=newNode; /队尾指针指向新队尾结点队尾指针指向新队尾结点/假设队头指针原先为空那么置为指向新结点假设队头指针原先为空那么置为指向新结点if(front=NULL) front=newNode;count+; /计数器加计数器加1template template T LinQueue :Delete(void) /T LinQueue :Delete(void)

45、 /出队列出队列 /把队头结点删除并由函数前往把队头结点删除并由函数前往 if(count=0) if(count=0) coutcout队列已空队列已空!endl; !endl; exit(0); exit(0); QueueNode QueueNode * *p=front-next; /pp=front-next; /p指向新的队头结点指向新的队头结点T data=front-data; /T data=front-data; /保管原队头结点的保管原队头结点的datadata域值域值delete front; /delete front; /释放原队头结点空间释放原队头结点空间fron

46、t=p; /frontfront=p; /front指向新的对头结点指向新的对头结点count-; /count-; /计数器减计数器减1 1return data; /return data; /前往原队头结点的前往原队头结点的datadata域值域值 template T LinQueue :GetFront(void)const /取队头数据元素取队头数据元素if(count=0)cout队列已空队列已空!data;6 6、队列的运用、队列的运用例：编写判别一个字符序列能否是回文的函数。例：编写判别一个字符序列能否是回文的函数。编程思想：编程思想：设字符数组设字符数组strstr中存放了

47、要判别的字符串。把字符数组中的中存放了要判别的字符串。把字符数组中的字符逐个分别存入队列和堆栈，然后逐个出队列和退栈并比较字符逐个分别存入队列和堆栈，然后逐个出队列和退栈并比较出队列的字符和退栈的字符能否相等，假设全部相等那么该字出队列的字符和退栈的字符能否相等，假设全部相等那么该字符序列是回文，否那么就不是回文。符序列是回文，否那么就不是回文。设计函数如下：设计函数如下：void HuiWen(char str) void HuiWen(char str) LinStack myStack; LinStack myStack; LinQueue myQueue; LinQueue myQue

48、ue; int n=strlen(str); /int n=strlen(str); /求字符串长度求字符串长度for(int i=0;in;i+) for(int i=0;in;i+) myQueue.Append(stri); myQueue.Append(stri); myStack.Push(stri); myStack.Push(stri); while(myQueue.NotEmpty()&myStack.NotEmpty() while(myQueue.NotEmpty()&myStack.NotEmpty() if(myQueue.Delete()!=mySta

49、ck.Pop() if(myQueue.Delete()!=myStack.Pop() cout cout不是回文不是回文!endl; !endl; return; return; coutcout是回文是回文!endl;!endl; 3.4 3.4 优先级队列优先级队列、优先级队列带有优先级的队列。、优先级队列带有优先级的队列。、顺序优先级队列用顺序存储构造存储的优先级队列。、顺序优先级队列用顺序存储构造存储的优先级队列。、优先级队列和普通队列的主要区别、优先级队列和普通队列的主要区别优先级队列的出队列操作不是把队头元素出队列，而是把优先级队列的出队列操作不是把队头元素出队列，而是把队列中优先级最高的元素出队列。队列中优先级最高的元素出队列。它的数据元素定义为如下构造体：它的数据元素定义为如下构造体：struct DataType ElemType elem; /数据元素数据元素int priority; /优先级优先级;注：顺序优先级队列除出队列操作外的其他操作的实现方法与注：顺序优先级队列除出队列操作外的其他操作的实现方法与前边讨论的顺序队列操作的实现方法一样。前边讨论的顺序队列操作的实现方法一样。出队列操作出队列操作( (把优先级最高的元素出队列并由函数前