第三章棧隊列和遞歸

第三章棧隊列和遞歸第1頁，共73頁，2023年，2月20日，星期三特殊線性表

棧隊列

串⑴棧的定義⑵操作特性⑶ADT定義⑴隊列定義⑵操作特性⑶ADT定義⑴串的定義⑵基本概念⑶ADT定義順序棧鏈棧循環(huán)隊列鏈隊列順序存儲鏈接存儲邏輯結(jié)構(gòu)存儲結(jié)構(gòu)邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)存儲結(jié)構(gòu)存儲結(jié)構(gòu)比較模式匹配比較比較⑴基本操作的實現(xiàn)⑵時間復(fù)雜度⑴基本操作的實現(xiàn)⑵時間復(fù)雜度第2頁，共73頁，2023年，2月20日，星期三3.1棧（Stack）

3.2隊列

（Queue）１.邏輯結(jié)構(gòu)２.存儲結(jié)構(gòu)與實現(xiàn)３.應(yīng)用實例１.邏輯結(jié)構(gòu)２.存儲結(jié)構(gòu)與實現(xiàn)３.應(yīng)用實例第3頁，共73頁，2023年，2月20日，星期三３.1棧1、棧的邏輯結(jié)構(gòu)空棧：不含任何數(shù)據(jù)元素的棧。

（a1,a2,……,an）棧：限定僅在一端進行插入和刪除操作的線性表。棧頂棧底允許插入和刪除的一端稱為棧頂，另一端稱為棧底。數(shù)據(jù)元素之間的邏輯關(guān)系：一對一。第4頁，共73頁，2023年，2月20日，星期三注：棧的運算規(guī)則只能在棧頂運算，且訪問結(jié)點時依照后進先出（LIFO）或先進后出（FILO）的原則。入棧：插入元素到棧頂（即表尾）的操作。出棧：從棧頂（即表尾）刪除最后一個元素的操作。問：棧與一般線性表有什么不同？一般線性表（堆）棧邏輯結(jié)構(gòu)：一對一邏輯結(jié)構(gòu)：一對一存儲結(jié)構(gòu)：順序表、鏈表存儲結(jié)構(gòu)：順序棧、鏈棧運算規(guī)則：隨機存取運算規(guī)則：后進先出(LIFO)入棧操作演示

出棧操作演示第5頁，共73頁，2023年，2月20日，星期三a1a2a3入棧棧底棧頂插入：入棧、進棧、壓棧棧頂棧頂入棧的操作示圖：棧頂?shù)?頁，共73頁，2023年，2月20日，星期三a1a2a3棧底棧頂刪除：出棧、彈棧棧頂棧頂出棧的操作示圖：棧頂棧的操作特性：后進先出出棧第7頁，共73頁，2023年，2月20日，星期三思考題１：一個棧的輸入序列為123，若在入棧的過程中允許出棧，且每個元素只允許進一次棧，則可能得到的出棧序列有哪些？答：可以通過窮舉所有可能性來求解：①1入1出，2入2出，3入3出，即123；②1入1出，2、3入3、2出，即132；③1、2入，2出，3入3出，即231；④1、2入，2、1出，3入3出，即213；⑤1、2、3入，3、2、1出，即321；合計有5種可能性。第8頁，共73頁，2023年，2月20日，星期三思考題２：設(shè)依次進入一個棧的元素序列為c，a，b，d，則可得到出棧的元素序列是：

Ａ）a，b，c，dＢ）c，d，a，bＣ）b，c，d，aＤ）a，c，d，bA、D可以（B、C不行）。討論：有無通用的判別原則？有。若輸入序列i，j，k，則不存在輸出序例k、i、j;答：第9頁，共73頁，2023年，2月20日，星期三2、棧的存儲結(jié)構(gòu)順序棧、鏈?zhǔn)綏＃ǎ保╉樞驐！獥５捻樞虼鎯Y(jié)構(gòu)(重點)如何改造數(shù)組實現(xiàn)棧的順序存儲？

012345678a1確定用數(shù)組的哪一端表示棧底。附設(shè)指針top指示棧頂元素在數(shù)組中的位置。

topS第10頁，共73頁，2023年，2月20日，星期三進棧核心語句：top++;S[top]=a1;棧空：top==-1

012345678topa1topa2top進棧的操作步驟如何？第11頁，共73頁，2023年，2月20日，星期三

012345678a1a2棧滿：top==MAX_SIZE-1棧滿的如何判斷？topa3a4a5a6a7a8a9第12頁，共73頁，2023年，2月20日，星期三動態(tài)棧類的定義：template<classtype>//定義模板類DSeqStackclassDSeqStack{public:

DSeqStack(intsize);//構(gòu)造函數(shù)，棧的初始化

~DSeqStack(){delete[]S;}//析構(gòu)函數(shù)

voidPush(consttype&item);//將元素item入棧typePop();//將棧頂元素彈出typeGetTop(); //取棧頂元素（并不刪除）

intEmpty(){returntop==-1;}

//判斷棧是否為空

intfull()const{returntop==MaxSize-1;}//為滿則返回1，否則返回0

voidclear(){top=-1;}//清空棧private:

type*S;//存放棧元素的數(shù)組起始地址

inttop;//棧頂指針，指示棧頂元素在數(shù)組中的下標(biāo)

intMaxSize;//棧最大可容納元素個數(shù)};第13頁，共73頁，2023年，2月20日，星期三順序棧的構(gòu)造函數(shù)算法實現(xiàn)template<classtype>DSeqStack<type>::DSeqStack(intsize):top(-1),MaxSize(size){//建立一個最大尺寸為size的空棧

S=newtype[MaxSize];//創(chuàng)建存儲棧的數(shù)組 if(S==NULL)//分配不成功 {cerr<<"動態(tài)存儲失敗！"<<endl; exit(1);//stdlib.h }}操作接口：

template<classtype>DSeqStack<type>::DSeqStack(intsize);算法實現(xiàn)：第14頁，共73頁，2023年，2月20日，星期三順序棧的入棧操作算法實現(xiàn)template<classtype>voidDSeqStack<type>::Push(consttype&item){if(top==MaxSize-1)throw"棧滿！";

top++;//棧未滿，則入棧

S[top]=item;}操作接口：

template<classtype>voidDSeqStack<type>::Push(consttype&item)算法實現(xiàn)：時間復(fù)雜度？O(1)第15頁，共73頁，2023年，2月20日，星期三出棧核心語句：Item=S[top];top--;邊界條件棧空：top==-1;

012345678topa1topa2top出棧的操作步驟如何？第16頁，共73頁，2023年，2月20日，星期三順序棧的出棧操作算法實現(xiàn)template<classtype>typeDSeqStack<type>::Pop(){typeitem;if(top==-1)throw"?？眨?;

item=S[top--];//等價于item=S[top];top--;returnitem;}操作接口：

template<classtype>typeDSeqStack<type>::Pop();算法實現(xiàn)：時間復(fù)雜度？O(1)第17頁，共73頁，2023年，2月20日，星期三其它類型棧舉例：如兩棧共享空間

解決方案1：直接解決：為每個棧開辟一個數(shù)組空間。

解決方案2：

使用一個數(shù)組來存儲兩個棧。使用一個數(shù)組來存儲兩個棧，讓一個棧的棧底為該數(shù)組的始端，另一個棧的棧底為該數(shù)組的末端，兩個棧從各自的端點向中間延伸。在一個程序中需要同時使用具有相同數(shù)據(jù)類型的兩個棧，如何順序存儲這兩個棧？會出現(xiàn)什么問題？如何解決？第18頁，共73頁，2023年，2月20日，星期三棧1的棧底:固定靠下標(biāo)為0的這一端；棧2的棧底:固定靠下標(biāo)為MaxSize-1的這一端。top1和top2分別為棧1和棧2的棧頂指針；MaxSize:整個數(shù)組空間的大?。▓D中用S表示）；a1

a2…aitop1012…

…S-1top2bj

……b2

b1棧1底棧2底Ｓ兩棧共享空間棧頂與棧底如何設(shè)置？第19頁，共73頁，2023年，2月20日，星期三棧1為空條件：top1==-1棧2為空條件：top2==MaxSize什么時候兩棧為空？012…

…S-1top2top1第20頁，共73頁，2023年，2月20日，星期三a1

a2……aitop1012…

…S-1top2bj

……b2

b1棧滿條件為：top2=top1+1什么時候棧為滿？第21頁，共73頁，2023年，2月20日，星期三（２）鏈?zhǔn)綏！獥５逆準(zhǔn)酱鎯Y(jié)構(gòu)如何改造鏈表實現(xiàn)棧的鏈接存儲？鏈棧需要加頭結(jié)點嗎？將哪一端作為棧頂？注：鏈棧不需要附設(shè)頭結(jié)點。(棧底)(棧頂)topa3a2a4a1^第22頁，共73頁，2023年，2月20日，星期三鏈棧類的定義：template<classtype>classLinkStack;//聲明template<classtype>classNode{friendclassLinkStack<type>;private:

typedata;Node<type>*next;//此處<T>也可以省略};template<classtype>classLinkStack{public:LinkStack();//構(gòu)造函數(shù)，置空鏈棧~LinkStack();//析構(gòu)函數(shù)，釋放鏈棧中各結(jié)點的存儲空間voidPush(typeitem);//將元素item入棧typePop();//將棧頂元素出棧typeGetTop();//取棧頂元素（并不刪除）boolEmpty();//判斷鏈棧是否為空棧private:

Node<type>*top;//棧頂指針即鏈棧的頭指針};第23頁，共73頁，2023年，2月20日，星期三鏈棧的構(gòu)造函數(shù)算法實現(xiàn)template<classtype>LinkStack<type>::LinkStack(){

top=NULL;//初始化空棧}操作接口：

template<classtype>LinkStack<type>::LinkStack();算法實現(xiàn)：第24頁，共73頁，2023年，2月20日，星期三算法實現(xiàn)：template<classtype>voidinkStack<type>::Push(typex){

Node<type>*s;s=newNode<type>;

s->data=x;s->next=top;

top=s;}topanan-1a1∧鏈棧的入棧算法實現(xiàn)xstop操作接口：template<classtype>voidLinkStack<type>::Push(typex)；為什么沒有判斷棧滿？第25頁，共73頁，2023年，2月20日，星期三算法實現(xiàn)：template<classtype>typeLinkStack<type>::Pop(){Node<type>*p;typex;if(top==NULL)throw“?？?;

x=top->data;p=top;

top=top->next;

deletep;returnx;}鏈棧的出棧算法實現(xiàn)：操作接口：template<classT>TLinkStack<T>::Pop();topanan-1a1∧topp

top++可以嗎？第26頁，共73頁，2023年，2月20日，星期三順序棧和鏈棧的比較時間性能：相同，都是常數(shù)時間O(1)?？臻g性能：順序棧：有元素個數(shù)的限制和空間浪費的問題。鏈棧：沒有棧滿的問題，只有當(dāng)內(nèi)存沒有可用空間時才會出現(xiàn)棧滿，但是每個元素都需要一個指針域，從而產(chǎn)生了結(jié)構(gòu)性開銷。

總之，采用順序棧存儲方式，可使多個棧共享空間；當(dāng)棧中元素個數(shù)變化較大，且存在多個棧的情況下，鏈棧是棧的首選存儲方式。第27頁，共73頁，2023年，2月20日，星期三調(diào)用函數(shù)或子程序非它莫屬；遞歸運算的有力工具；用于保護現(xiàn)場和恢復(fù)現(xiàn)場；簡化了程序設(shè)計的問題；其它應(yīng)用：如括號匹配問題、表達式計算問題等。答：3、棧的應(yīng)用舉例為什么要設(shè)計棧？它有什么獨特用途？第28頁，共73頁，2023年，2月20日，星期三數(shù)制轉(zhuǎn)換（十轉(zhuǎn)八進制）

設(shè)計思路：用棧暫存低位值算法分析：NNdiv8Nmod87492911101棧的應(yīng)用實例１：如：(74)10=(112)8第29頁，共73頁，2023年，2月20日，星期三voidconversion(){//對于輸入的任意一個非負(fù)十進制整數(shù)，//打印輸出與其等值的八進制數(shù)；

SeqStack<int>s1(10); intN,n;inte;

cout<<"請輸入一十進制數(shù)："<<endl; cin>>N;

n=N; while(n){ s1.Push(n%８); n=n/８; }

while(!s1.Empty()){ e=s1.Pop(); cout<<e; }cout<<endl;}第30頁，共73頁，2023年，2月20日，星期三3.1棧（Stack）

3.2隊列

（Queue）１.邏輯結(jié)構(gòu)２.存儲結(jié)構(gòu)與實現(xiàn)３.應(yīng)用實例１.邏輯結(jié)構(gòu)２.存儲結(jié)構(gòu)與實現(xiàn)第31頁，共73頁，2023年，2月20日，星期三３.2隊列1、隊列的邏輯結(jié)構(gòu)空隊：不含任何數(shù)據(jù)元素的隊列。

（a1,a2,……,an）隊列：只允許在一端進行插入操作，而在另一端進行刪除操作的線性表。。隊尾隊頭允許插入的一端稱為隊尾，另一端允許刪除的稱為隊頭。數(shù)據(jù)元素之間的邏輯關(guān)系：一對一。第32頁，共73頁，2023年，2月20日，星期三注：隊列的運算規(guī)則只能在隊尾進行插入運算，在隊頭進行刪除運算;且訪問結(jié)點時依照先進先出（FIFO）或后進后出（LILO）的原則。入隊：插入元素到隊列的隊尾的操作。出隊：從隊頭刪除一個元素的操作。問：隊列與一般線性表有什么不同？一般線性表隊列邏輯結(jié)構(gòu)：一對一邏輯結(jié)構(gòu)：一對一存儲結(jié)構(gòu)：順序表、鏈表存儲結(jié)構(gòu)：順序隊、鏈隊運算規(guī)則：隨機存取運算規(guī)則：先進先出(FIFO)

第33頁，共73頁，2023年，2月20日，星期三隊列的操作特性：先進先出a1a2a3入隊隊尾隊頭出隊隊頭入隊出隊操作示意圖:隊尾隊尾隊尾第34頁，共73頁，2023年，2月20日，星期三2、隊列的存儲結(jié)構(gòu)與實現(xiàn)順序隊列、鏈?zhǔn)疥犃校ǎ保╉樞蜿犃小犃械捻樞虼鎯Y(jié)構(gòu)(重點)如何改造數(shù)組實現(xiàn)隊列的順序存儲？

012345678a1確定用數(shù)組如何表示隊頭、隊尾。附設(shè)指示器rear指示隊尾元素（在數(shù)組中最后一個元素的位置），指示器front指示隊頭（隊頭元素所在位置的前一位置）。

rearSfront第35頁，共73頁，2023年，2月20日，星期三01234入隊出隊實例1：a1a2a3a4依次入隊a1a2a3a4rearrearrearrear入隊操作時間性能為O(1)front第36頁，共73頁，2023年，2月20日，星期三實例2：a1a2依次出隊01234入隊出隊a1a2a3a4rearfrontfrontfront出隊操作時間性能為O(1)隊列的移動有什么特點？整個隊列向數(shù)組下標(biāo)較大方向移動單向移動性第37頁，共73頁，2023年，2月20日，星期三假溢出：當(dāng)元素被插入到數(shù)組中下標(biāo)最大的位置上之后，隊列的空間就用盡了，盡管此時數(shù)組的低端還有空閑空間，這種現(xiàn)象叫做假溢出。繼續(xù)入隊會出現(xiàn)什么情況？01234入隊出隊a3a4rearfronta5rear第38頁，共73頁，2023年，2月20日，星期三循環(huán)隊列：將存儲隊列的數(shù)組頭尾相接。如何解決假溢出？01234入隊出隊a3a4fronta5rearreara6第39頁，共73頁，2023年，2月20日，星期三a3a2a10123N-1rearfront循環(huán)隊列（臆造）順序隊列a3a2a1frontrear0123..N-1新問題：在循環(huán)隊列中，空隊特征是front==rear；隊滿時也會有front==rear；判決條件將出現(xiàn)二義性！解決方案有三：①加設(shè)標(biāo)志位，讓刪除動作使其為1,插入動作使其為0,則可識別當(dāng)前front==rear②使用一個計數(shù)器記錄隊列中元素個數(shù)（即隊列長度）；③人為浪費一個單元，令隊滿特征為front==(rear+1)%N；第40頁，共73頁，2023年，2月20日，星期三隊空條件:front==rear

(初始化時：front=rear)隊滿條件：front==(rear+1)%N(N=maxsize)隊列長度：L=（N＋rear－front）%NJ2J3

J1J4

J5frontrear問2：在具有n個單元的循環(huán)隊列中，隊滿時共有多少個元素？

n-1個5

問1：左圖中隊列長度L=？第41頁，共73頁，2023年，2月20日，星期三例1：一循環(huán)隊列如下圖所示，若先刪除4個元素，接著再插入4個元素，請問隊頭和隊尾指針分別指向哪個位置?front

J5rear解：由圖可知，初始狀態(tài),隊頭和隊尾指針的初態(tài)分別為front=0和rear=5。刪除4個元素后(front+4)%6=4；再插入4個元素后，r=(rear+4)%6=(5+4)%6=3

frontfrontfrontfrontJ1J2

J5rearfrontrearrearrearrear

J6

J7

J8

J9J3J4第42頁，共73頁，2023年，2月20日，星期三動態(tài)循環(huán)隊列類的定義：（重點）//DCirQueue.h#ifndefDCirQueue_H#defineDCirQueue_Htemplate<classT>//定義模板類DCirQueueclassDCirQueue{public:

DCirQueue(intsize=10);//構(gòu)造函數(shù)，置空隊~DCirQueue(){delete[]queue;};//析構(gòu)函數(shù)

voidEnQueue(Tx);//將元素x入隊TDeQueue();//將隊頭元素出隊TGetQueue();//取隊頭元素（并不刪除）boolIsEmpty();//判斷隊列是否為空

intIsfull()const{return(rear+1)%maxsize==front;} //隊列滿則返回1，否則返回0private:

T*queue;//存放隊列元素的數(shù)組intfront,rear;//隊頭和隊尾指針，分別指向隊頭元素的前一個位置和隊尾元素的位置

intmaxsize;//隊列最大可容納元素個數(shù)為maxsize-1};#endif第43頁，共73頁，2023年，2月20日，星期三循環(huán)隊列的構(gòu)造函數(shù)算法實現(xiàn)template<classT>DCirQueue<T>::DCirQueue(intsize):front(0),rear(0),maxsize(size){

queue=newT[maxsize]; if(queue==NULL) throw"動態(tài)分配失敗!";}操作接口：

template<classT>DCirQueue<T>::DCirQueue(intsize);算法實現(xiàn)：01234rearfront第44頁，共73頁，2023年，2月20日，星期三循環(huán)隊列的入隊算法實現(xiàn)template<classT>voidDCirQueue<T>::EnQueue(Tx){if((rear+1)%maxsize==front)throw“隊滿";

rear=(rear+1)%maxsize;

//隊尾指針在循環(huán)意義下加1queue[rear]=x;//在隊尾處插入元素}操作接口：

template<classT>voidDCirQueue<T>::EnQueue(Tx)算法實現(xiàn)：01234rearfrontreara1第45頁，共73頁，2023年，2月20日，星期三循環(huán)隊列的出隊算法實現(xiàn)template<classT>TDCirQueue<T>::DeQueue(){if(rear==front)throw"下溢";

front=(front+1)%maxsize;

//隊頭指針在循環(huán)意義下加1returnqueue[front];//讀取并返回出隊前的隊頭元素，注意隊頭指針}操作接口：

template<classT>TDCirQueue<T>::DeQueue()算法實現(xiàn)：a101234入隊a4a5a6出隊frontrearfronta3第46頁，共73頁，2023年，2月20日，星期三循環(huán)隊列的讀隊頭元素算法實現(xiàn)template<classT>TDCirQueue<T>::GetQueue(){inti;if(rear==front)throw“隊空!";

i=(front+1)%maxsize;

//注意不要給隊頭指針賦值returnqueue[i];}操作接口：

template<classT>TDCirQueue<T>::GetQueue()算法實現(xiàn)：a101234a4a5a6出隊frontreara3i入隊第47頁，共73頁，2023年，2月20日，星期三（2）隊列的鏈接存儲結(jié)構(gòu)及實現(xiàn)

鏈隊列：隊列的鏈接存儲結(jié)構(gòu)隊頭指針即為鏈表的頭指針；常用不帶頭結(jié)點鏈表結(jié)構(gòu)。a1a2an∧如何改造單鏈表實現(xiàn)隊列的鏈接存儲？rearfront第48頁，共73頁，2023年，2月20日，星期三front==NULL;front==rear;空鏈隊列如何表示？rearfrontNULLNULL鏈隊列滿如何表示？無需考慮滿的情況。第49頁，共73頁，2023年，2月20日，星期三鏈?zhǔn)疥犃蓄惖亩x：template<classT>structNode{Tdata;Node<T>*next;//此處<T>也可以省略};template<classT>classLinkQueue{public:LinkQueue();//構(gòu)造函數(shù)，初始化一個空的鏈隊列~LinkQueue();//析構(gòu)函數(shù)，釋放鏈隊中各結(jié)點的存儲空間voidEnQueue(Tx);//將元素x入隊TDeQueue();//將隊頭元素出隊TGetQueue();//取鏈隊列的隊頭元素boolEmpty();//判斷鏈隊列是否為空private:

Node<T>*front,*rear;

//隊頭和隊尾指針，分別指向頭結(jié)點和終端結(jié)點};第50頁，共73頁，2023年，2月20日，星期三鏈隊的構(gòu)造函數(shù)算法實現(xiàn)template<classT>LinkQueue<T>::LinkQueue(){

front=rear=NULL;}操作接口：

template<classT>LinkQueue<T>::LinkQueue()；算法實現(xiàn)：第51頁，共73頁，2023年，2月20日，星期三

xs鏈隊列的實現(xiàn)——入隊fronta1an∧rear∧rearfrontxs∧rearrear隊不空核心算法描述：Node<T>*s=newNode<T>;s->data=x;s->next=NULL;rear->next=s;rear=s;操作接口：

template<classT>voidLinkQueue<T>::EnQueue(Tx)NULLfront隊空時核心算法描述：Node<T>*s=newNode<T>;s->data=x;s->next=NULL;front=rear=s;第52頁，共73頁，2023年，2月20日，星期三template<classT>voidLinkQueue<T>::EnQueue(Tx){ Node<T>*s;s=newNode<T>;s->data=x;//申請一個數(shù)據(jù)域為x的結(jié)點ss->next=NULL; if(front==NULL)//空隊列，新結(jié)點既是隊頭，又是隊尾 {front=rear=s; } else

{rear->next=s;//將結(jié)點s插入到隊尾rear=s;}}算法實現(xiàn)：第53頁，共73頁，2023年，2月20日，星期三鏈隊列的實現(xiàn)——出隊操作接口：template<classT>TLinkQueue<T>::DeQueue()fronta2an∧rearNode<T>*p=front;x=p->data;Front=NULL;rear=front;deletep;pa2∧rear隊列不空時算法描述：Node<T>*p=front;x=p->data;front=front->next;deletep;隊列只有一個元素時?a1frontfrontP第54頁，共73頁，2023年，2月20日，星期三鏈隊的出隊操作算法實現(xiàn)template<classT>TLinkQueue<T>::DeQueue(){ Node<T>*p;intx;if(front==NULL)throw“隊空";

p=front; x=p->data;//暫存隊頭元素

front=front->next;//將隊頭元素所在結(jié)點摘鏈if(front==NULL)rear=front;

//判斷出隊前隊列長度是否為1

deletep;returnx;}操作接口：template<classT>TLinkQueue<T>::DeQueue()；算法實現(xiàn)：第55頁，共73頁，2023年，2月20日，星期三鏈隊的獲得隊首元素操作算法實現(xiàn)template<classT>TLinkQueue<T>::GetQueue(){if(front!=NULL) returnfront->data;}操作接口：template<classT>TLinkQueue<T>::GetQueue()算法實現(xiàn)：第56頁，共73頁，2023年，2月20日，星期三隊列的其它鏈接存儲結(jié)構(gòu)用帶頭結(jié)點的單鏈表實現(xiàn)隊列的鏈接存儲？隊頭指針即為鏈表的頭指針，指向頭結(jié)點。a1a2an∧rearfront空鏈隊列front∧rear第57頁，共73頁，2023年，2月20日，星期三xsfronta1an∧rear∧rearfrontxs∧∧rearrear核心算法描述：Node<T>*s=front->next;s->data=x;s->next=NULL;rear->next=s;rear=s;隊列為空時如何入隊如何操作？用帶頭結(jié)點的單鏈表如何實現(xiàn)隊列的入隊操作？第58頁，共73頁，2023年，2月20日，星期三fronta1an∧rearfronta1p∧∧rearrear核心算法描述：Node<T>*p=front->next;x=p->data;front->next=p->next;deletep;隊列中僅有一個元素時出隊如何操作？用帶頭結(jié)點的單鏈表如何實現(xiàn)隊列的出隊操作？a2p核心算法描述：rear=front;第59頁，共73頁，2023年，2月20日，星期三練習(xí)1：數(shù)組Ｑ[n]用來表示一個循環(huán)隊列，f為當(dāng)前隊列首元素的前一位置，r為隊尾元素的位置。假定隊列中元素的個數(shù)小于n，計算隊列中元素個數(shù)的公式為:（Ａ）r－f（Ｂ）（n＋f－r）%n（Ｃ）n＋r－f（Ｄ）（n＋r－f）%n4種公式哪種合理？當(dāng)r≥f時（A）合理；當(dāng)r<f時（C）合理；分析：綜合2種情況，以（D）的表達最為合理練習(xí)2：在一個循環(huán)隊列中，若約定隊首指針指向隊首元素的前一個位置。那么，從循環(huán)隊列中刪除一個元素時，其操作是先

，后

。

移動隊首指針取出元素√第60頁，共73頁，2023年，2月20日，星期三離散事件的模擬（模擬事件發(fā)生的先后順序）；操作系統(tǒng)中多道作業(yè)的處理（一個CPU執(zhí)行多個作業(yè)）；3.簡化程序設(shè)計。答：為什么要設(shè)計隊列？它有什么獨特用途？第61頁，共73頁，2023年，2月20日，星期三小結(jié)線性表、棧與隊的異同點相同點：邏輯結(jié)構(gòu)相同，都是線性的；都可以用順序存儲或鏈表存儲；棧和隊列是兩種特殊的線性表，即受限的線性表（只是對插入、刪除運算加以限制）。不同點：①運算規(guī)則不同，線性表為隨機存取，而棧是只允許