数据结构课件C++版=

2023/2/1mayan第三章栈和队列栈栈的应用队列队列的应用优先级队列定义：栈限定只能在表的一端进行插入和删除运算的线性表。递归函数的实现

在递归函数的执行中，

需多次自己调用自己，递归函数是如何执行的？先看一般函数的调用机制如何实现的。A(){…B();…}C(){……}B(){…C();…}调用调用返回返回函数调用顺序ABC函数返回顺序CBA后调用的函数先返回

函数调用机制可通过栈来实现计算机正是利用栈来实现函数的调用和返回的n=3阶乘函数fact(n)的执行过程Main(){intn=3,y;Ly=fact(n);}调用调用调用intfact(n){

If（n=1）

return（1）；

ElseL1return（n*fact(n-1)）；}n=3intfact(intn){

If（n=1）

return（1）；

Else

L1return（n*fact(n-1)）；}n=2intfact(intn){

If（n=1）

return（1）；

ElseL1return（n*fact(n-1)）；}//factn=1L3L11L12返回1返回2返回61n*fact(n-1)n*fact(n-1)fact(n)返回地址实参

递归调用中栈的变化将十进制整数转换成二至九之间的任一进制数输出

将一个十进制数4327转换成八进制数(10347)8：abc32111213121YXZ2023/2/1mayan第三章栈和队列--栈的定义

栈和队列称为运算受限的线性表。栈（stack）是指只允许在表的末端进行插入和删除的线性表。栈又叫做后进先出（LIFO）的线性表。栈的基本概念栈是一种“特殊”的线性表，这种线性表上的插入和删除运算限定在表的某一端进行。栈顶：允许进行插入和删除的这一端。栈底：反之为栈底。栈顶元素：处于栈顶位置的数据元素称为～。栈顶元素的位置由栈顶指针变量记录；空栈:当栈中不含任何数据元素时称为～2023/2/1mayan第三章栈和队列--顺序栈基于数组的存储表示实现的栈称为顺序栈。当前栈顶位置由数组下标指针top指示，即top指示最后加入的元素的存储位置，当top=-1时栈空，当top=maxSize-1时栈满。顺序栈的类定义2023/2/1mayan第三章栈和队列--顺序栈的类定义template<classT>classSeqStack{//顺序栈类定义private:

T*elements; //栈元素存放数组

inttop; //栈顶指针

intmaxSize;//栈最大容量public:

SeqStack(intsz=50); //构造函数

~SeqStack(){delete[]elements;}//析构函数2023/2/1mayan第三章栈和队列--顺序栈的类定义

voidPush(constT&x);//进栈

boolPop(T&x);

//出栈

boolgetTop(T&x);

//取栈顶内容

boolIsEmpty()const{returntop=-1;}

boolIsFull()const{returntop=maxSize-1;}intgetSize()const{returntop+1;}//返回栈中元素个数

voidmakeEmpty(){top=-1}//清空栈的内容};2023/2/1mayan第三章栈和队列--顺序栈的函数实现//顺序栈的构造函数template<classT>SeqStack<T>::SeqStack(intsz):top(-1),maxSize(sz){ elements=newT[maxSize];

}2023/2/1mayan第三章栈和队列--顺序栈的函数实现//若栈不满,则将元素x插入该栈栈顶,否则溢出处理template<classT>voidSeqStack<T>::Push(constT&x){

if(IsFull()==true)printf(“栈满，不能入栈”);return;//栈满

elements[++top]=x;

//栈顶指针先加1,再进栈}

2023/2/1mayan第三章栈和队列--顺序栈的函数实现//函数退出栈顶元素并返回栈顶元素的值template<classT>boolSeqStack<T>::Pop(T&x){

if(IsEmpty()==true)returnfalse; x=elements[top--];//栈顶指针退1

returntrue;//退栈成功}

2023/2/1mayan第三章栈和队列--顺序栈的函数实现//若栈不空则函数返回该栈栈顶元素template<classT>boolSeqstack<T>::getTop(T&x){

if(IsEmpty()==true)returnfalse; x=elements[top];returntrue;}2023/2/1mayan第三章栈和队列--双栈共享一个栈空间为了既能减少由于栈满而引起的溢出，又能有效的利用存储空间，提出一种双栈共享一个栈空间的策略。2023/2/1mayan第三章栈和队列--双栈共享一个栈空间两个栈共享一个数组空间V[maxSize]设立栈顶指针数组t[2]和栈底指针数组b[2]t[i]和b[i]分别指示第i个栈的栈顶与栈底初始t[0]=b[0]=-1,t[1]=b[1]=maxSize满条件：t[0]+1==t[1]//栈顶指针相遇栈空条件：t[0]=b[0]或t[1]=b[1]//退到栈底2023/2/1mayan第三章栈和队列--双栈共享一个栈空间//双栈的插入算法boolpush(DualStack&DS,Tx,intd){if(DS.t[0]+1==DS.t[1])returnfalse;

if(d==0)DS.t[0]++;elseDS.t[1]--;DS.Vector[DS.t[d]]=x;returntrue;}2023/2/1mayan第三章栈和队列--双栈共享一个栈空间//双栈的删除算法boolPop(DualStack&DS,T&x,intd){if(DS.t[d]==DS.b[d])returnfalse;x=DS.Vector[DS.t[d]];if(d==0)DS.t[0]--;elseDS.t[1]++;returntrue;}

2023/2/1mayan第三章栈和队列--链式栈链式栈是栈的链接存储表示。链式栈的栈顶在链表的表头。因此，新结点的插入和栈顶结点的删除都在链表的表头，即栈顶进行。2023/2/1mayan第三章栈和队列--链式栈的类定义template<classT>classLinkedStack:publicStack<T>{//链式栈类定义private: LinkNode<T>*top;

//栈顶指针public:LinkedStack():top(NULL){}

//构造函数2023/2/1mayan第三章栈和队列--链式栈的类定义

~LinkedStack(){makeEmpty();

}//析构函数

voidPush(constT&x);

//进栈

boolPop(T&x);

//退栈

boolgetTop(T&x)const;//取栈顶

boolIsEmpty()const{returntop==NULL;} intgetSize()const;//求栈中元素个数

voidmakeEmpty();

//清空栈的内容

friendostream&operator<<(ostream&os, LinkedStack<T>&s);};2023/2/1mayan第三章栈和队列--链式栈的函数实现//逐次删去链式栈中的元素直至栈顶指针为空。template<classT>LinkedStack<T>::makeEmpty(){

LinkNode<T>*p; while(top!=NULL) //逐个结点释放

{p=top;top=top->link;

deletep;}}2023/2/1mayan第三章栈和队列--链式栈的函数实现//将元素值x插入到链式栈的栈顶,即链头。template<classT>voidLinkedStack<T>::Push(constT&x){top=newLinkNode<T>(x,top);

//创建新结点

assert(top!=NULL);

//创建失败退出}2023/2/1mayan第三章栈和队列--链式栈的函数实现//删除栈顶结点,返回被删栈顶元素的值。template<classT>boolLinkedStack<T>::Pop(T&x){

if(IsTmpty()==true)returnfalse;//栈空返回

LinkNode<T>*p=top;

//暂存栈顶元素

top=top->link;

//退栈顶指针

x=p->data;deletep;

//释放结点

returntrue; }2023/2/1mayan第三章栈和队列--链式栈的函数实现//返回栈顶元素的值template<classT>boolLinkedStack<T>::getTop(T&x)const{

if(IsEmpty()==true)returnfalse;//栈空返回

x=top->data;returntrue;}2023/2/1mayan第三章栈和队列--链式栈的函数实现//返回栈中元素个数template<classT>intLinkedStack<T>::getSizeconst{

LinkNode<T>*p=top;intk=0;

while(top!=NULL){top=top->link;k++;}

returnk;}2023/2/1mayan第三章栈和队列--链式栈的函数实现//输出栈中元素template<classT>ostream&operator<<(ostream&os,LinkedStack<T>&s){ os<<”栈中元素个数：”<<s.getSize()<<endl; LinkNode<T>*p=s.top;inti=0;

while(p!=NULL) {os<<++i<<”:”<<p->data<<endl;p=p->link;}

returnos;}2023/2/1mayan第三章栈和队列例1：一个栈的入栈序列是a、b、c、d、e，则栈的不可能的输出序列是（C）。

A．edcbaB．decbaC．dceabD．abcde例2：对于一个栈，给出输入项a、b、c。如果输入序列由a、b、c组成，试给出全部可能的输出序列。

abcacbbacbcacba2023/2/1mayan第三章栈和队列--栈的应用之括号匹配观察：每个右括号将与最近遇到的那个未匹配的左括号相匹配。

(a×(b+c)-d)(a+b))((((没有与右括号匹配的左括号没有与左括号匹配的右括号(2023/2/1mayan第三章栈和队列--栈的应用之表达式求值一个表达式由操作数（亦称运算对象）、操作符（亦称运算符）和分界符组成。算术表达式有三种表示：中缀(infix)表示

<操作数><操作符><操作数>，如A+B；前缀(prefix)表示

<操作符><操作数><操作数>，如+AB；后缀(postfix)表示

<操作数><操作数><操作符>，如AB+；2023/2/1mayan第三章栈和队列--栈的应用之表达式求值表达式示例中缀表达式A+B*(C-D)-E/F后缀表达式ABCD-*+EF/-前缀表达式-+A*B-CD/EF表达式中相邻两个操作符的计算次序为：优先级高的先计算；优先级相同的自左向右计算；当使用括号时从最内层括号开始计算。2023/2/1mayan第三章栈和队列--栈的应用之表达式求值应用后缀表示计算表达式的值说明：这里只考虑双目运算的情形。从左向右顺序地扫描表达式，并用一个栈暂存扫描到的操作数或计算结果。在后缀表达式的计算顺序中已隐含了加括号的优先次序，括号在后缀表达式中不出现。计算例ABCD－×+EF/－2023/2/1mayan第三章栈和队列--栈的应用之表达式求值通过后缀表示计算表达式值的过程：顺序扫描表达式的每一项，如果该项是操作数，则将其入栈；如果该项是操作符<op>，则连续从栈中退出两个操作数X和Y，形成运算指令X<op>Y，并将计算结果重新压入栈中。当表达式的所有项都扫描并处理完后，栈顶存放的就是最后的计算结果。2023/2/1mayan第三章栈和队列--栈的应用之表达式求值ABCD－×+EF/－步扫描项项类型动作栈中内容1置空栈空2A操作数进栈A3B操作数进栈AB4C操作数进栈ABC5D操作数进栈ABCD6－操作符D、C退栈，计算C－D，结果R1进栈ABR17×操作符R1、B退栈，计算B×R1，结果R2进栈AR22023/2/1mayan第三章栈和队列--栈的应用之表达式求值8+操作符R2、A退栈，计算A+R2，结果R3进栈R39E操作数进栈R3EF10F操作数进栈R3EF11/操作符E、F退栈，计算E/F，结果R4进栈R3R412－操作符R3、R4退栈，计算R3－R4，结果R5进栈R5步扫描项项类型动作栈中内容ABCD－×+EF/－2023/2/1mayan第三章栈和队列--栈的应用之表达式求值中缀表示→转后缀表示先对中缀表达式按运算优先次序加上括号；再把操作符后移到右括号的后面并以就近移动为原则；最后将所有括号消去。

例：中缀表示(A+B)*D-E/(F+A*D)+C，转换为后缀表示(

(

((A+B)*D)

–(E/(F+(A*D)

)

)

)+C)后缀表示

AB+D*EFAD*+/-C+2023/2/1mayan第三章栈和队列--栈的应用之表达式求值中缀表示→转前缀表示先对中缀表达式按运算优先次序通统加上括号再把操作符前移到左括号前并以就近移动为原则最后将所有括号消去。 例：中缀表示(A+B)*D-E/(F+A*D)+C，转换为前缀表示(

(

((A+B)*D)

–(E/(F+(A*D)

)

)

)+C)前缀表示

+-*+ABD/E+F*ADC2023/2/1mayan第三章栈和队列--栈的应用之表达式求值利用栈将中缀表示转换为后缀表示 使用栈可将表达式的中缀表示转换成它的前缀表示和后缀表示。操作符优先级 为了实现这种转换，需要考虑各操作符的优先级。优先级操作符1单目－，！2×，／，%3＋，－4<，<=，>，>=5==，！=6&&7||2023/2/1mayan第三章栈和队列--栈的应用之表达式求值各个算术操作符的优先级isp叫做栈内(instackpriority)优先数icp叫做栈外(incomingpriority)优先数。操作符优先数相等的情况只出现在括号配对或栈底的“#”号与输入流最后的“#”号配对时。操作符ch#(×,／,%＋,－)isp01536icp064212023/2/1mayan第三章栈和队列--栈的应用之表达式求值中缀表达式转换为后缀表达式的算法操作符栈初始化，将结束符‘#’进栈。然后读入中缀表达式字符流的首字符ch。重复执行以下步骤，直到ch=‘#’，同时栈顶的操作符也是‘#’，停止循环。若ch是操作数直接输出，读入下一个字符ch。若ch是操作符，判断ch的优先级icp和位于栈顶的操作符op的优先级isp：2023/2/1mayan第三章栈和队列--栈的应用之表达式求值若icp(ch)>isp(op)，令ch进栈，读入下一个字符ch。若icp(ch)<isp(op)，退栈并输出。若icp(ch)==isp(op)，退栈但不输出，若退出的是“(”号读入下一个字符ch。算法结束，输出序列即为所需的后缀表达式。2023/2/1mayan第三章栈和队列--栈的应用之表达式求值例：给定中缀表达式A+B*(C-D)-E/F，按上述算法转换为后缀表达式。步扫描项项类型动作栈中内容输出0‘#’

进栈#1A操作数#A2＋操作符isp(‘#’)<icp(‘＋’)进栈#＋A3B操作数

#＋AB4×操作符isp(‘＋’)<icp(‘×’)进栈#＋×AB2023/2/1mayan第三章栈和队列--栈的应用之表达式求值步扫描项项类型动作栈中内容输出5(操作符isp(‘×’)<icp(‘(’)进栈#＋×(AB6C操作数#＋×(ABC7－操作符isp(‘(’)<icp(‘－’)进栈#＋×(－ABC8D操作数#＋×(－ABCD9)操作符isp(‘－’)>icp(‘)’)退栈#＋×(ABCD－isp(‘(’)==icp(‘)’)退栈#＋×ABCD－10－操作符isp(‘×’)>icp(‘－’)退栈#＋ABCD－×isp(‘＋’)>icp(‘－’)退栈#ABCD－×＋isp(‘#’)<icp(‘－’)进栈#－ABCD－×＋A+B*(C-D)-E/F2023/2/1mayan第三章栈和队列--栈的应用之表达式求值步扫描项项类型动作栈中内容输出11E操作数#－ABCD－×＋E12／操作符isp(‘－’)<icp(‘/’)进栈#－／ABCD－×＋E13F操作数#－／ABCD－×＋EF14#操作符isp(‘/’)>icp(‘#’)退栈#－ABCD－×＋EF/isp(‘－’)>icp(‘#’)退栈#ABCD－×＋EF/－A+B*(C-D)-E/F2023/2/1mayan第三章栈和队列--栈的应用之栈与递归递归的定义 若一个对象部分地包含它自己，或用它自己给自己定义,则称这个对象是递归的；若一个过程直接地或间接地调用自己,则称这个过程是递归的过程。以下三种情况常常用到递归方法。定义是递归的数据结构是递归的问题的解法是递归的2023/2/1mayan第三章栈和队列--栈的应用之栈与递归定义是递归的例如：求解阶乘函数的递归算法longFactorial(longn){if(n==0)return1;

elsereturnn*Factorial(n-1);}分解过程求值过程2023/2/1mayan第三章栈和队列--栈的应用之栈与递归数据结构是递归的例如，单链表结构 一个结点，它的指针域为NULL，是一个单链表;

一个结点，它的指针域指向单链表，仍是一个单链表。f

f

2023/2/1mayan第三章栈和队列--栈的应用之栈与递归搜索链表最后一个结点并打印其数值template<classT>

voidPrint(ListNode<T>*f){if(f->link==NULL)

cout<<f->data<<

endl;elsePrint(f->link);}fffffabcde递归找链尾123452023/2/1mayan第三章栈和队列--栈的应用之栈与递归问题的解法是递归的例如汉诺塔(TowerofHanoi)问题 问题描述： 有A,B,C三个塔座，A上套有n个直径不同的圆盘，按直径从小到大叠放，形如宝塔,编号1,2,3……n。要求将n个圆盘从A移到C，叠放顺序不变，移动过程中遵循下列原则：每次只能移一个圆盘圆盘可在三个塔座上任意移动任何时刻，每个塔座上不能将大盘压到小盘上2023/2/1mayan第三章栈和队列--栈的应用之栈与递归解决方法： 如果n=1，则将这一个盘子直接从A柱移到C柱上。否则，执行以下三步： 用C柱做过渡，将A柱上的(n-1)个盘子移到B柱上： 将A柱上最后一个盘子直接移到C柱上； 用A柱做过渡，将B柱上的(n-1)个盘子移到C柱上。2023/2/1mayan第三章栈和队列--栈的应用之栈与递归解决汉诺塔问题的算法#include<iostream.h>void

Hanoi(intn,

charA,

charB,

charC){if(n==1)cout<<"move"<<A<<"to"<<C<<endl;

else{Hanoi(n-1,A,C,B);

cout<<"move"<<A<<"to"<<C<<endl; Hanoi(n-1,B,A,C);

}}2023/2/1mayan第三章栈和队列--栈的应用之栈与递归递归过程改为非递归过程递归过程简洁、易编、易懂递归过程效率低，重复计算多改为非递归过程的目的是提高效率单向递归和尾递归可直接用迭代实现其非递归过程其他情形必须借助栈实现非递归过程2023/2/1mayan第三章栈和队列--栈的应用之栈与递归Ackerman函数定义如下：学生课下学习部分2023/2/1mayan第三章栈和队列--栈的应用之栈与递归递归算法：unsignedakm(unsignedm,unsignedn){

if(m==0)returnn+1;//m==0

elseif(n==0)returnakm(m-1,1);//m>0,n==0 elsereturnakm(m-1,akm(m,n-1));//m>0,n>0}2023/2/1mayan第三章栈和队列--栈的应用之栈与递归非递归算法：#include<iostream.h>#include”stack.h”#definemaxSize3500;unsignedakm(unsignedm,unsignedn){

structnode{unsignedvm,vn;} stack<node>st(maxSize);nodew;unsignedv; w.vm=m;w.vn=n;st.Push(w);2023/2/1mayan第三章栈和队列--栈的应用之栈与递归do{

while(st.GetTop().vm>0){

while(st.GetTop().vn>0){w.vn--;st.Push(w);} w=st.GetTop();st.Pop();w.vm--;w.vn=1;st.Push(w);} w=st.GetTop();st.Pop();v=w.vn++;

if(st.IsEmpty()==0) {w=st.GetTop();st.Pop();w.vm--;w.vn=v;st.Push(w);}}while(st.IsEmpty()==0);returnv;}2023/2/1mayan第三章栈和队列--队列的定义队列（Queue）是只允许在表的一端插入，在另一端删除的线性表。队列又叫先进先出（FIFO）的线性表。2023/2/1mayan第三章栈和队列--队列的类定义template<classT>classQueue{public:Queue(){};

//构造函数

～Queue(){};

//析构函数voidEnQueue(T&x);//进队列boolDeQueue();//出队列boolgetFront();//取队头boolIsEmpty();//判队列空boolIsFull(); //判队列满intgetSize();//求队列元素个数};2023/2/1mayan第三章栈和队列--循环队列顺序队列的概念 队列的基于数组的存储表示称为顺序队列。利用一个一维数组elements[maxSize]作为队列元素的存储结构。设置两个指针(下标变量)front和rear，分别指示对头和队尾位置。初始化时令front=rear=0。队尾指针rear指示了实际队尾位置的后一位置，队头指针front则指示真正队头元素所在位置。当front==rear，队列为空；当rear==maxSize，队列满。2023/2/1mayan第三章栈和队列--循环队列循环队列的概念 解决假溢出的办法之一：将队列元素存放数组首尾相接，形成循环（环形）队列。队列存放数组被当作首尾相接的表处理。队头、队尾指针加1时从maxSize-1直接进到0，可用语言的取模(余数)运算实现。队头指针进1:front=(front+1)%maxSize;队尾指针进1:rear=(rear+1)%maxSize;2023/2/1mayan第三章栈和队列--循环队列队列初始化：front=rear=0;队空条件：front==rear;队满条件：(rear+1)%maxSize==front;注意，在循环队列中，最多只能存放maxSize-1个元素。2023/2/1mayan第三章栈和队列--循环队列的类定义template<classT>classSeqQueue{ //队列类定义protected:intrear,front; //队尾与队头指针

T*elements; //队列存放数组

intmaxSize; //队列最大容量2023/2/1mayan第三章栈和队列--循环队列的类定义public:

SeqQueue(intsz=10);//构造函数

~SeqQueue(){

delete[]elements;}//析构函数

boolEnQueue(constT&x);//新元素进队列

boolDeQueue();//退出队头元素

boolgetFront();

//取队头元素值

voidmakeEmpty(){front=rear=0;}//队列做空

2023/2/1mayan第三章栈和队列--循环队列的类定义 boolIsEmpty()const{returnfront==rear;} //判断队空

boolIsFull()const//判断队满

{return((rear+1)%maxSize==front);}

intgetSize()const//队中元素个数{return(rear-front+maxSize)%maxSize;} voiddisplay()const;//输出队中元素

};2023/2/1mayan第三章栈和队列--循环队列的函数实现//构造函数template<classT>SeqQueue<T>::SeqQueue(intsz):front(0),rear(0),maxSize(sz){elements=newT[maxSize];

}2023/2/1mayan第三章栈和队列--循环队列的函数实现//若队列不满,则将x插入到该队列队尾,否则返回template<classT>boolSeqQueue<T>::EnQueue(constT&x){if(IsFull()==true)returnfalse;elements[rear]=x;//先存入

rear=(rear+1)%maxSize;//尾指针加一

returntrue; }2023/2/1mayan第三章栈和队列--循环队列的函数实现//若队列不空则函数退队头元素并返回其值template<classT>boolSeqQueue<T>::DeQueue(){intx;if(IsEmpty()==true)returnfalse;

x=elements[front];//先取队头

front=(front+1)%maxSize;

//再队头指针加一

returntrue;}2023/2/1mayan第三章栈和队列--循环队列的函数实现//若队列不空则函数返回该队列队头元素的值template<classT>boolSeqQueue<T>::getFront()const{intx;if(IsEmpty()==true)returnfalse;//队列空

x=elements[front]; //返回队头元素

returntrue;}2023/2/1mayan第三章栈和队列--循环队列的函数实现//输出队列中的元素template<classT>voidSeqQueue<T>::display()const{ inti; if(IsEmpty()==true)return;//队列空

cout<<"队列中的元素为："<<endl; for(i=front;i!=rear;i=(i+1)%maxSize) cout<<elements[i]<<""; cout<<endl;}2023/2/1mayan第三章栈和队列--链式队列链式队列是基于单链表的一种存储表示。队列的队头指针指向单链表的第一个结点，队尾指针指向单链表的最后一个结点。队空条件为front==NULL;2023/2/1mayan第三章栈和队列--链式队列的类定义#include<iostream.h>#include“LinkedList.h”#include“Queue.h”template<classT>classLinkedQueue:publicQueue<T>{

private:

LinkNode<T>*front,*rear;//队头、队尾指针public: LinkedQueue():rear(NULL),front(NULL){}

~LinkedQueue(){makeEmpty();}

2023/2/1mayan第三章栈和队列--链式队列的类定义

boolEnQueue(constT&x);boolDeQueue(T&x);

boolgetFront(T&x)const;

voidmakeEmpty();boolIsEmpty()const

{returnfront==NULL;

}intgetSize()const;friendostream&operator<<(ostream&os,LinkedQueue<T>&Q);};

2023/2/1mayan第三章栈和队列--链式队列的函数实现//置空队列template<classT>boolLinkedQueue<T>::makeEmpty(){ LinkNode<T>*p;

while(front!=NULL){ p=front;front=front->link;deletep;}}

2023/2/1mayan第三章栈和队列--链式队列的函数实现template<classT>//将新元素x插入到队列的队尾boolLinkedQueue<T>::EnQueue(constT&x){if(front==NULL){

//创建第一个结点

front=rear=newLinkNode<T>(x);if(front==NULL)returnfalse;} //分配失败

else{ //队列不空,插入

rear->link=newLinkNode<T>(x);if(rear->link==NULL)returnfalse;rear=rear->link;}returntrue;}

2023/2/1mayan第三章栈和队列--链式队列的函数实现//如果队列不空，将队头结点从链式队列中删去template<classT>boolLinkedQueue<T>::DeQueue(T&x){

if(IsEmpty()==true)returnfalse;//判队空

LinkNode<T>*p=front; x=front->data;front=front->link;

deletep;

returntrue; }

2023/2/1mayan第三章栈和队列--链式队列的函数实现//若队列不空，则函数返回队头元素的值template<classT>boolLinkedQueue<T>::GetFront(T&x){ if(IsEmpty()==true)returnfalse; x=front->data; returntrue;}

2023/2/1mayan第三章栈和队列--链式队列的函数实现//求队列元素个数template<classT>intLinkedQueue<T>::getSize()const{ LinkNode<T>*p=front;intk=0;

while(p!=NULL){p=p->link;k++;}

returnk;}

2023/2/1mayan第三章栈和队列--链式队列的函数实现//输出队列中的元素template<classT>ostream&operator<<(ostream&os,LinkedQueue<T>&Q){ os<<”队列中元素个数有”<<Q.getSize()<<endl; LinkNode<T>*p=Q.front;inti=0;

while(p!=NULL){ os<<++i<<”:”<<p->data<<endl; p=p->link;}

returnos;}2023/2/1mayan第三章栈和队列

--队列的应用之打印杨辉三角形将二项式展开，其系数构成杨辉三角形。2023/2/1mayan第三章栈和队列

--队列的应用之打印杨辉三角形2023/2/1mayan第三章栈和队列

--队列的应用之打印杨辉三角形#include

<stdio.h>#include

<iostream.h>#include"queue.h"voidYANGVI(intn){ Queueq(n+2);

//队列初始化

inti=1,j,s=k=0,t,u; q.EnQueue(i);q.EnQueue(i);2023/2/1mayan第三章栈和队列

--队列的应用之打印杨辉三角形for(int

i=1;i<=n;i++){//逐行计算

cout<<endl; q.EnQueue(k);

for(intj=1;j<=i+2;j++){//下一行

q.DeQueue(t); u=s+t;q.EnQueue(u); s=t;

if(j!=i+2)cout<<s<<'';//第j+2个是0

}}}2023/2/1mayan第三章栈和队列--优先级队列的概念每次从队列中取出的是具有最高优先权的元素，这种队列就是优先级队列（PriorityQueue）。最小优先级队列（minPriorityQueue）：数字越小优先权越高最大优先级队列（maxPriorityQueue）：数字越大优先权越高优先权相同时先来先服务。任务编号12345优先权200403010执行顺序315422023/2/1mayan第三章栈和队列

--优先级队列的存储表示与实现优先级队列的数组存储表示#include<assert.h>#include<iostream.h>#include<stdlib.h>template<classT>classPQueue{private:

T

*pqelements;

//存放数组

intco