數(shù)據(jù)結構課件C++版=

2023/8/16mayan第三章棧和隊列棧棧的應用隊列隊列的應用優(yōu)先級隊列2023/8/5mayan第三章棧和隊列棧定義：棧限定只能在表的一端進行插入和刪除運算的線性表。定義：棧限定只能在表的一端進行插入和刪除運算的線性表。遞歸函數(shù)的實現(xiàn)

在遞歸函數(shù)的執(zhí)行中，

需多次自己調(diào)用自己，遞歸函數(shù)是如何執(zhí)行的？先看一般函數(shù)的調(diào)用機制如何實現(xiàn)的。A(){…B();…}C(){……}B(){…C();…}調(diào)用調(diào)用返回返回函數(shù)調(diào)用順序ABC函數(shù)返回順序CBA后調(diào)用的函數(shù)先返回

函數(shù)調(diào)用機制可通過棧來實現(xiàn)計算機正是利用棧來實現(xiàn)函數(shù)的調(diào)用和返回的遞歸函數(shù)的實現(xiàn)A(){C(){B(){調(diào)用調(diào)用返回返回n=3階乘函數(shù)fact(n)的執(zhí)行過程Main(){intn=3,y;Ly=fact(n);}調(diào)用調(diào)用調(diào)用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)返回地址實參

遞歸調(diào)用中棧的變化n=3階乘函數(shù)fact(n)的執(zhí)行過程Main(){調(diào)將十進制整數(shù)轉換成二至九之間的任一進制數(shù)輸出

將一個十進制數(shù)4327轉換成八進制數(shù)(10347)8：將十進制整數(shù)轉換成二至九之間的任一進制數(shù)輸出將一個十進制數(shù)abc32111213121YXZabc32111213121YXZ數(shù)據(jù)結構ppt課件C++版=2023/8/16mayan第三章棧和隊列--棧的定義

棧和隊列稱為運算受限的線性表。棧（stack）是指只允許在表的末端進行插入和刪除的線性表。棧又叫做后進先出（LIFO）的線性表。2023/8/5mayan第三章棧和隊列-棧的基本概念棧是一種“特殊”的線性表，這種線性表上的插入和刪除運算限定在表的某一端進行。棧頂：允許進行插入和刪除的這一端。棧底：反之為棧底。棧頂元素：處于棧頂位置的數(shù)據(jù)元素稱為～。棧頂元素的位置由棧頂指針變量記錄；空棧:當棧中不含任何數(shù)據(jù)元素時稱為～棧的基本概念棧是一種“特殊”的線性表，這種線性表上的插入和刪2023/8/16mayan第三章棧和隊列--順序棧基于數(shù)組的存儲表示實現(xiàn)的棧稱為順序棧。當前棧頂位置由數(shù)組下標指針top指示，即top指示最后加入的元素的存儲位置，當top=-1時?？眨攖op=maxSize-1時棧滿。順序棧的類定義2023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--順序棧的類定義template<classT>classSeqStack{//順序棧類定義private:

T*elements; //棧元素存放數(shù)組

inttop; //棧頂指針

intmaxSize;//棧最大容量public:

SeqStack(intsz=50); //構造函數(shù)

~SeqStack(){delete[]elements;}//析構函數(shù)2023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--順序棧的類定義

voidPush(constT&x);//進棧

boolPop(T&x);

//出棧

boolgetTop(T&x);

//取棧頂內(nèi)容

boolIsEmpty()const{returntop=-1;}

boolIsFull()const{returntop=maxSize-1;}intgetSize()const{returntop+1;}//返回棧中元素個數(shù)

voidmakeEmpty(){top=-1}//清空棧的內(nèi)容};2023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--順序棧的函數(shù)實現(xiàn)//順序棧的構造函數(shù)template<classT>SeqStack<T>::SeqStack(intsz):top(-1),maxSize(sz){ elements=newT[maxSize];

}2023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--順序棧的函數(shù)實現(xiàn)//若棧不滿,則將元素x插入該棧棧頂,否則溢出處理template<classT>voidSeqStack<T>::Push(constT&x){

if(IsFull()==true)printf(“棧滿，不能入?！?;return;//棧滿

elements[++top]=x;

//棧頂指針先加1,再進棧}

2023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--順序棧的函數(shù)實現(xiàn)//函數(shù)退出棧頂元素并返回棧頂元素的值template<classT>boolSeqStack<T>::Pop(T&x){

if(IsEmpty()==true)returnfalse; x=elements[top--];//棧頂指針退1

returntrue;//退棧成功}

2023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--順序棧的函數(shù)實現(xiàn)//若棧不空則函數(shù)返回該棧棧頂元素template<classT>boolSeqstack<T>::getTop(T&x){

if(IsEmpty()==true)returnfalse; x=elements[top];returntrue;}2023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--雙棧共享一個棧空間為了既能減少由于棧滿而引起的溢出，又能有效的利用存儲空間，提出一種雙棧共享一個?？臻g的策略。2023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--雙棧共享一個棧空間兩個棧共享一個數(shù)組空間V[maxSize]設立棧頂指針數(shù)組t[2]和棧底指針數(shù)組b[2]t[i]和b[i]分別指示第i個棧的棧頂與棧底初始t[0]=b[0]=-1,t[1]=b[1]=maxSize滿條件：t[0]+1==t[1]//棧頂指針相遇?？諚l件：t[0]=b[0]或t[1]=b[1]//退到棧底2023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--雙棧共享一個棧空間//雙棧的插入算法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/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--雙棧共享一個?？臻g//雙棧的刪除算法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/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--鏈式棧鏈式棧是棧的鏈接存儲表示。鏈式棧的棧頂在鏈表的表頭。因此，新結點的插入和棧頂結點的刪除都在鏈表的表頭，即棧頂進行。2023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--鏈式棧的類定義template<classT>classLinkedStack:publicStack<T>{//鏈式棧類定義private: LinkNode<T>*top;

//棧頂指針public:LinkedStack():top(NULL){}

//構造函數(shù)2023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--鏈式棧的類定義

~LinkedStack(){makeEmpty();

}//析構函數(shù)

voidPush(constT&x);

//進棧

boolPop(T&x);

//退棧

boolgetTop(T&x)const;//取棧頂

boolIsEmpty()const{returntop==NULL;} intgetSize()const;//求棧中元素個數(shù)

voidmakeEmpty();

//清空棧的內(nèi)容

friendostream&operator<<(ostream&os, LinkedStack<T>&s);};2023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--鏈式棧的函數(shù)實現(xiàn)//逐次刪去鏈式棧中的元素直至棧頂指針為空。template<classT>LinkedStack<T>::makeEmpty(){

LinkNode<T>*p; while(top!=NULL) //逐個結點釋放

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

deletep;}}2023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--鏈式棧的函數(shù)實現(xiàn)//將元素值x插入到鏈式棧的棧頂,即鏈頭。template<classT>voidLinkedStack<T>::Push(constT&x){top=newLinkNode<T>(x,top);

//創(chuàng)建新結點

assert(top!=NULL);

//創(chuàng)建失敗退出}2023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--鏈式棧的函數(shù)實現(xiàn)//刪除棧頂結點,返回被刪棧頂元素的值。template<classT>boolLinkedStack<T>::Pop(T&x){

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

LinkNode<T>*p=top;

//暫存棧頂元素

top=top->link;

//退棧頂指針

x=p->data;deletep;

//釋放結點

returntrue; }2023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--鏈式棧的函數(shù)實現(xiàn)//返回棧頂元素的值template<classT>boolLinkedStack<T>::getTop(T&x)const{

if(IsEmpty()==true)returnfalse;//?？辗祷?/p>

x=top->data;returntrue;}2023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--鏈式棧的函數(shù)實現(xiàn)//返回棧中元素個數(shù)template<classT>intLinkedStack<T>::getSizeconst{

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

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

returnk;}2023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--鏈式棧的函數(shù)實現(xiàn)//輸出棧中元素template<classT>ostream&operator<<(ostream&os,LinkedStack<T>&s){ os<<”棧中元素個數(shù)：”<<s.getSize()<<endl; LinkNode<T>*p=s.top;inti=0;

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

returnos;}2023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列例1：一個棧的入棧序列是a、b、c、d、e，則棧的不可能的輸出序列是（C）。

A．edcbaB．decbaC．dceabD．a(chǎn)bcde例2：對于一個棧，給出輸入項a、b、c。如果輸入序列由a、b、c組成，試給出全部可能的輸出序列。

abcacbbacbcacba2023/8/5mayan第三章棧和隊列例1：一個棧的2023/8/16mayan第三章棧和隊列--棧的應用之括號匹配觀察：每個右括號將與最近遇到的那個未匹配的左括號相匹配。

(a×(b+c)-d)(a+b))((((沒有與右括號匹配的左括號沒有與左括號匹配的右括號(2023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--棧的應用之表達式求值一個表達式由操作數(shù)（亦稱運算對象）、操作符（亦稱運算符）和分界符組成。算術表達式有三種表示：中綴(infix)表示

<操作數(shù)><操作符><操作數(shù)>，如A+B；前綴(prefix)表示

<操作符><操作數(shù)><操作數(shù)>，如+AB；后綴(postfix)表示

<操作數(shù)><操作數(shù)><操作符>，如AB+；2023/8/5mayan第三章棧和隊列--棧的2023/8/16mayan第三章棧和隊列--棧的應用之表達式求值表達式示例中綴表達式A+B*(C-D)-E/F后綴表達式ABCD-*+EF/-前綴表達式-+A*B-CD/EF表達式中相鄰兩個操作符的計算次序為：優(yōu)先級高的先計算；優(yōu)先級相同的自左向右計算；當使用括號時從最內(nèi)層括號開始計算。2023/8/5mayan第三章棧和隊列--棧的2023/8/16mayan第三章棧和隊列--棧的應用之表達式求值應用后綴表示計算表達式的值說明：這里只考慮雙目運算的情形。從左向右順序地掃描表達式，并用一個棧暫存掃描到的操作數(shù)或計算結果。在后綴表達式的計算順序中已隱含了加括號的優(yōu)先次序，括號在后綴表達式中不出現(xiàn)。計算例ABCD－×+EF/－2023/8/5mayan第三章棧和隊列--棧的2023/8/16mayan第三章棧和隊列--棧的應用之表達式求值通過后綴表示計算表達式值的過程：順序掃描表達式的每一項，如果該項是操作數(shù)，則將其入棧；如果該項是操作符<op>，則連續(xù)從棧中退出兩個操作數(shù)X和Y，形成運算指令X<op>Y，并將計算結果重新壓入棧中。當表達式的所有項都掃描并處理完后，棧頂存放的就是最后的計算結果。2023/8/5mayan第三章棧和隊列--棧的2023/8/16mayan第三章棧和隊列--棧的應用之表達式求值ABCD－×+EF/－步掃描項項類型動作棧中內(nèi)容1置空棧空2A操作數(shù)進棧A3B操作數(shù)進棧AB4C操作數(shù)進棧ABC5D操作數(shù)進棧ABCD6－操作符D、C退棧，計算C－D，結果R1進棧ABR17×操作符R1、B退棧，計算B×R1，結果R2進棧AR22023/8/5mayan第三章棧和隊列--棧的2023/8/16mayan第三章棧和隊列--棧的應用之表達式求值8+操作符R2、A退棧，計算A+R2，結果R3進棧R39E操作數(shù)進棧R3EF10F操作數(shù)進棧R3EF11/操作符E、F退棧，計算E/F，結果R4進棧R3R412－操作符R3、R4退棧，計算R3－R4，結果R5進棧R5步掃描項項類型動作棧中內(nèi)容ABCD－×+EF/－2023/8/5mayan第三章棧和隊列--棧的2023/8/16mayan第三章棧和隊列--棧的應用之表達式求值中綴表示→轉后綴表示先對中綴表達式按運算優(yōu)先次序加上括號；再把操作符后移到右括號的后面并以就近移動為原則；最后將所有括號消去。

例：中綴表示(A+B)*D-E/(F+A*D)+C，轉換為后綴表示(

(

((A+B)*D)

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

)

)

)+C)后綴表示

AB+D*EFAD*+/-C+2023/8/5mayan第三章棧和隊列--棧的2023/8/16mayan第三章棧和隊列--棧的應用之表達式求值中綴表示→轉前綴表示先對中綴表達式按運算優(yōu)先次序通統(tǒng)加上括號再把操作符前移到左括號前并以就近移動為原則最后將所有括號消去。 例：中綴表示(A+B)*D-E/(F+A*D)+C，轉換為前綴表示(

(

((A+B)*D)

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

)

)

)+C)前綴表示

+-*+ABD/E+F*ADC2023/8/5mayan第三章棧和隊列--棧的2023/8/16mayan第三章棧和隊列--棧的應用之表達式求值利用棧將中綴表示轉換為后綴表示 使用?？蓪⒈磉_式的中綴表示轉換成它的前綴表示和后綴表示。操作符優(yōu)先級 為了實現(xiàn)這種轉換，需要考慮各操作符的優(yōu)先級。優(yōu)先級操作符1單目－，！2×，／，%3＋，－4<，<=，>，>=5==，！=6&&7||2023/8/5mayan第三章棧和隊列--棧的2023/8/16mayan第三章棧和隊列--棧的應用之表達式求值各個算術操作符的優(yōu)先級isp叫做棧內(nèi)(instackpriority)優(yōu)先數(shù)icp叫做棧外(incomingpriority)優(yōu)先數(shù)。操作符優(yōu)先數(shù)相等的情況只出現(xiàn)在括號配對或棧底的“#”號與輸入流最后的“#”號配對時。操作符ch#(×,／,%＋,－)isp01536icp064212023/8/5mayan第三章棧和隊列--棧的2023/8/16mayan第三章棧和隊列--棧的應用之表達式求值中綴表達式轉換為后綴表達式的算法操作符棧初始化，將結束符‘#’進棧。然后讀入中綴表達式字符流的首字符ch。重復執(zhí)行以下步驟，直到ch=‘#’，同時棧頂?shù)牟僮鞣彩恰?’，停止循環(huán)。若ch是操作數(shù)直接輸出，讀入下一個字符ch。若ch是操作符，判斷ch的優(yōu)先級icp和位于棧頂?shù)牟僮鞣鹢p的優(yōu)先級isp：2023/8/5mayan第三章棧和隊列--棧的2023/8/16mayan第三章棧和隊列--棧的應用之表達式求值若icp(ch)>isp(op)，令ch進棧，讀入下一個字符ch。若icp(ch)<isp(op)，退棧并輸出。若icp(ch)==isp(op)，退棧但不輸出，若退出的是“(”號讀入下一個字符ch。算法結束，輸出序列即為所需的后綴表達式。2023/8/5mayan第三章棧和隊列--棧的2023/8/16mayan第三章棧和隊列--棧的應用之表達式求值例：給定中綴表達式A+B*(C-D)-E/F，按上述算法轉換為后綴表達式。步掃描項項類型動作棧中內(nèi)容輸出0‘#’

進棧#1A操作數(shù)#A2＋操作符isp(‘#’)<icp(‘＋’)進棧#＋A3B操作數(shù)

#＋AB4×操作符isp(‘＋’)<icp(‘×’)進棧#＋×AB2023/8/5mayan第三章棧和隊列--棧的2023/8/16mayan第三章棧和隊列--棧的應用之表達式求值步掃描項項類型動作棧中內(nèi)容輸出5(操作符isp(‘×’)<icp(‘(’)進棧#＋×(AB6C操作數(shù)#＋×(ABC7－操作符isp(‘(’)<icp(‘－’)進棧#＋×(－ABC8D操作數(shù)#＋×(－ABCD9)操作符isp(‘－’)>icp(‘)’)退棧#＋×(ABCD－isp(‘(’)==icp(‘)’)退棧#＋×ABCD－10－操作符isp(‘×’)>icp(‘－’)退棧#＋ABCD－×isp(‘＋’)>icp(‘－’)退棧#ABCD－×＋isp(‘#’)<icp(‘－’)進棧#－ABCD－×＋A+B*(C-D)-E/F2023/8/5mayan第三章棧和隊列--棧的2023/8/16mayan第三章棧和隊列--棧的應用之表達式求值步掃描項項類型動作棧中內(nèi)容輸出11E操作數(shù)#－ABCD－×＋E12／操作符isp(‘－’)<icp(‘/’)進棧#－／ABCD－×＋E13F操作數(shù)#－／ABCD－×＋EF14#操作符isp(‘/’)>icp(‘#’)退棧#－ABCD－×＋EF/isp(‘－’)>icp(‘#’)退棧#ABCD－×＋EF/－A+B*(C-D)-E/F2023/8/5mayan第三章棧和隊列--棧的2023/8/16mayan第三章棧和隊列--棧的應用之棧與遞歸遞歸的定義 若一個對象部分地包含它自己，或用它自己給自己定義,則稱這個對象是遞歸的；若一個過程直接地或間接地調(diào)用自己,則稱這個過程是遞歸的過程。以下三種情況常常用到遞歸方法。定義是遞歸的數(shù)據(jù)結構是遞歸的問題的解法是遞歸的2023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--棧的應用之棧與遞歸定義是遞歸的例如：求解階乘函數(shù)的遞歸算法longFactorial(longn){if(n==0)return1;

elsereturnn*Factorial(n-1);}分解過程求值過程2023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--棧的應用之棧與遞歸數(shù)據(jù)結構是遞歸的例如，單鏈表結構 一個結點，它的指針域為NULL，是一個單鏈表;

一個結點，它的指針域指向單鏈表，仍是一個單鏈表。f

f

2023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--棧的應用之棧與遞歸搜索鏈表最后一個結點并打印其數(shù)值template<classT>

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

cout<<f->data<<

endl;elsePrint(f->link);}fffff

abcde遞歸找鏈尾123452023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--棧的應用之棧與遞歸問題的解法是遞歸的例如漢諾塔(TowerofHanoi)問題 問題描述： 有A,B,C三個塔座，A上套有n個直徑不同的圓盤，按直徑從小到大疊放，形如寶塔,編號1,2,3……n。要求將n個圓盤從A移到C，疊放順序不變，移動過程中遵循下列原則：每次只能移一個圓盤圓盤可在三個塔座上任意移動任何時刻，每個塔座上不能將大盤壓到小盤上2023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--棧的應用之棧與遞歸解決方法： 如果n=1，則將這一個盤子直接從A柱移到C柱上。否則，執(zhí)行以下三步： 用C柱做過渡，將A柱上的(n-1)個盤子移到B柱上： 將A柱上最后一個盤子直接移到C柱上； 用A柱做過渡，將B柱上的(n-1)個盤子移到C柱上。2023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--棧的應用之棧與遞歸解決漢諾塔問題的算法#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/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--棧的應用之棧與遞歸遞歸過程改為非遞歸過程遞歸過程簡潔、易編、易懂遞歸過程效率低，重復計算多改為非遞歸過程的目的是提高效率單向遞歸和尾遞歸可直接用迭代實現(xiàn)其非遞歸過程其他情形必須借助棧實現(xiàn)非遞歸過程2023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--棧的應用之棧與遞歸Ackerman函數(shù)定義如下：學生課下學習部分2023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--棧的應用之棧與遞歸遞歸算法：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/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--棧的應用之棧與遞歸非遞歸算法：#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/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--棧的應用之棧與遞歸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/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--隊列的定義隊列（Queue）是只允許在表的一端插入，在另一端刪除的線性表。隊列又叫先進先出（FIFO）的線性表。2023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--隊列的類定義template<classT>classQueue{public:Queue(){};

//構造函數(shù)

～Queue(){};

//析構函數(shù)voidEnQueue(T&x);//進隊列boolDeQueue();//出隊列boolgetFront();//取隊頭boolIsEmpty();//判隊列空boolIsFull(); //判隊列滿intgetSize();//求隊列元素個數(shù)};2023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--循環(huán)隊列順序隊列的概念 隊列的基于數(shù)組的存儲表示稱為順序隊列。利用一個一維數(shù)組elements[maxSize]作為隊列元素的存儲結構。設置兩個指針(下標變量)front和rear，分別指示對頭和隊尾位置。初始化時令front=rear=0。隊尾指針rear指示了實際隊尾位置的后一位置，隊頭指針front則指示真正隊頭元素所在位置。當front==rear，隊列為空；當rear==maxSize，隊列滿。2023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--循環(huán)隊列循環(huán)隊列的概念 解決假溢出的辦法之一：將隊列元素存放數(shù)組首尾相接，形成循環(huán)（環(huán)形）隊列。隊列存放數(shù)組被當作首尾相接的表處理。隊頭、隊尾指針加1時從maxSize-1直接進到0，可用語言的取模(余數(shù))運算實現(xiàn)。隊頭指針進1:front=(front+1)%maxSize;隊尾指針進1:rear=(rear+1)%maxSize;2023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--循環(huán)隊列隊列初始化：front=rear=0;隊空條件：front==rear;隊滿條件：(rear+1)%maxSize==front;注意，在循環(huán)隊列中，最多只能存放maxSize-1個元素。2023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--循環(huán)隊列的類定義template<classT>classSeqQueue{ //隊列類定義protected:intrear,front; //隊尾與隊頭指針

T*elements; //隊列存放數(shù)組

intmaxSize; //隊列最大容量2023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--循環(huán)隊列的類定義public:

SeqQueue(intsz=10);//構造函數(shù)

~SeqQueue(){

delete[]elements;}//析構函數(shù)

boolEnQueue(constT&x);//新元素進隊列

boolDeQueue();//退出隊頭元素

boolgetFront();

//取隊頭元素值

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

2023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--循環(huán)隊列的類定義 boolIsEmpty()const{returnfront==rear;} //判斷隊空

boolIsFull()const//判斷隊滿

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

intgetSize()const//隊中元素個數(shù){return(rear-front+maxSize)%maxSize;} voiddisplay()const;//輸出隊中元素

};2023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--循環(huán)隊列的函數(shù)實現(xiàn)//構造函數(shù)template<classT>SeqQueue<T>::SeqQueue(intsz):front(0),rear(0),maxSize(sz){elements=newT[maxSize];

}2023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--循環(huán)隊列的函數(shù)實現(xiàn)//若隊列不滿,則將x插入到該隊列隊尾,否則返回template<classT>boolSeqQueue<T>::EnQueue(constT&x){if(IsFull()==true)returnfalse;elements[rear]=x;//先存入

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

returntrue; }2023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--循環(huán)隊列的函數(shù)實現(xiàn)//若隊列不空則函數(shù)退隊頭元素并返回其值template<classT>boolSeqQueue<T>::DeQueue(){intx;if(IsEmpty()==true)returnfalse;

x=elements[front];//先取隊頭

front=(front+1)%maxSize;

//再隊頭指針加一

returntrue;}2023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--循環(huán)隊列的函數(shù)實現(xiàn)//若隊列不空則函數(shù)返回該隊列隊頭元素的值template<classT>boolSeqQueue<T>::getFront()const{intx;if(IsEmpty()==true)returnfalse;//隊列空

x=elements[front]; //返回隊頭元素

returntrue;}2023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--循環(huán)隊列的函數(shù)實現(xiàn)//輸出隊列中的元素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/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--鏈式隊列鏈式隊列是基于單鏈表的一種存儲表示。隊列的隊頭指針指向單鏈表的第一個結點，隊尾指針指向單鏈表的最后一個結點。隊空條件為front==NULL;2023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--鏈式隊列的類定義#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/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--鏈式隊列的類定義

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/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--鏈式隊列的函數(shù)實現(xiàn)//置空隊列template<classT>boolLinkedQueue<T>::makeEmpty(){ LinkNode<T>*p;

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

2023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--鏈式隊列的函數(shù)實現(xiàn)template<classT>//將新元素x插入到隊列的隊尾boolLinkedQueue<T>::EnQueue(constT&x){if(front==NULL){

//創(chuàng)建第一個結點

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/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--鏈式隊列的函數(shù)實現(xiàn)//如果隊列不空，將隊頭結點從鏈式隊列中刪去template<classT>boolLinkedQueue<T>::DeQueue(T&x){

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

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

deletep;

returntrue; }

2023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--鏈式隊列的函數(shù)實現(xiàn)//若隊列不空，則函數(shù)返回隊頭元素的值template<classT>boolLinkedQueue<T>::GetFront(T&x){ if(IsEmpty()==true)returnfalse; x=front->data; returntrue;}

2023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--鏈式隊列的函數(shù)實現(xiàn)//求隊列元素個數(shù)template<classT>intLinkedQueue<T>::getSize()const{ LinkNode<T>*p=front;intk=0;

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

returnk;}

2023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列--鏈式隊列的函數(shù)實現(xiàn)//輸出隊列中的元素template<classT>ostream&operator<<(ostream&os,LinkedQueue<T>&Q){ os<<”隊列中元素個數(shù)有”<<Q.getSize()<<endl; LinkNode<T>*p=Q.front;inti=0;

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

returnos;}2023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列

--隊列的應用之打印楊輝三角形將二項式展開，其系數(shù)構成楊輝三角形。2023/8/5mayan第三章棧和隊列

2023/8/16mayan第三章棧和隊列

--隊列的應用之打印楊輝三角形2023/8/5mayan第三章棧和隊列

2023/8/16mayan第三章棧和隊列

--隊列的應用之打印楊輝三角形#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/8/5mayan第三章棧和隊列

2023/8/16mayan第三章棧和隊列

--隊列的應用之打印楊輝三角形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/8/5mayan第三章棧和隊列

2023/8/16mayan第三章棧和隊列--優(yōu)先級隊列的概念每次從隊列中取出的是具有最高優(yōu)先權的元素，這種隊列就是優(yōu)先級隊列（PriorityQueue）。最小優(yōu)先級隊列（minPriorityQueue）：數(shù)字越小優(yōu)先權越高最大優(yōu)先級隊列（maxPriorityQueue）：數(shù)字越大優(yōu)先權越高優(yōu)先權相同時先來先服務。任務編號12345優(yōu)先權200403010執(zhí)行順序315422023/8/5mayan第三章棧和隊列-2023/8/16mayan第三章棧和隊列

--優(yōu)先級隊列的存儲表示與實現(xiàn)優(yōu)先級隊列的數(shù)組存儲表示#include<assert.h>#include<iostream.h>#include<stdlib.h>template<classT>classPQueue{private: