第-章━━堆棧隊(duì)列結(jié)構(gòu)優(yōu)秀文檔

C++程序設(shè)計(jì)第7章(3)

━━堆棧、隊(duì)列結(jié)構(gòu)1主要內(nèi)容堆棧結(jié)構(gòu)━━順序棧、鏈棧順序棧類的設(shè)計(jì)━━采用面向?qū)ο蟪绦蛟O(shè)計(jì)順序棧類的應(yīng)用舉例鏈棧類的設(shè)計(jì)━━采用面向?qū)ο蟪绦蛟O(shè)計(jì)鏈棧類的應(yīng)用舉例隊(duì)列結(jié)構(gòu)━━順序隊(duì)列、鏈隊(duì)列順序循環(huán)隊(duì)列類的設(shè)計(jì)━━采用面向?qū)ο蟪绦蛟O(shè)計(jì)順序循環(huán)隊(duì)列類的應(yīng)用舉例鏈隊(duì)列類的設(shè)計(jì)━━采用面向?qū)ο蟪绦蛟O(shè)計(jì)鏈隊(duì)列類的應(yīng)用舉例2堆棧結(jié)構(gòu)━━順序棧、鏈棧堆棧的邏輯結(jié)構(gòu)━━是限制插入和刪除操作僅能在一端進(jìn)行的線性結(jié)構(gòu)。

①棧頂與棧底：指線性表的兩端。能進(jìn)行插入和刪除的一端稱棧頂（top）；而另一端稱棧底（bottom）。在棧頂插入新元素稱進(jìn)棧（壓入）；刪除元素稱出棧（彈出）。

②特殊線性表：是后進(jìn)先出（LIFO：LastInFirstOut）結(jié)構(gòu)的線性表。進(jìn)棧時(shí)：最先進(jìn)棧的在最下面，最后進(jìn)棧的在最上面。出棧時(shí)：最后進(jìn)棧的最先出棧，最先進(jìn)棧的最后出棧。堆棧的物理結(jié)構(gòu)━━有連續(xù)、非連續(xù)存儲兩種結(jié)構(gòu)，但邏輯功能基本相同。

①連續(xù)存儲方式：順序棧。

②非連續(xù)存儲方式：鏈棧。堆棧結(jié)構(gòu)的應(yīng)用━━堆棧是最常用、最重要的數(shù)據(jù)結(jié)構(gòu)之一。

【例】

①局部變量是存放在棧中。

②表達(dá)式的優(yōu)先級處理可由棧來實(shí)現(xiàn)。

③函數(shù)調(diào)用時(shí)參數(shù)的傳遞、函數(shù)值的返回也是由棧來實(shí)現(xiàn)。3堆棧結(jié)構(gòu)━━順序棧、鏈棧順序棧的物理結(jié)構(gòu)━━連續(xù)存儲

①可以隨機(jī)訪問順序棧中的元素。

②需要先開一定量的內(nèi)存空間，使用時(shí)有可能溢出。③順序棧的操作執(zhí)行簡單，速度快。鏈棧的物理結(jié)構(gòu)━━非連續(xù)存儲

①只能順序訪問鏈棧中的元素。

②隨用隨開內(nèi)存空間，使用時(shí)不可能溢出。③鏈棧的操作執(zhí)行復(fù)雜（不斷地動(dòng)態(tài)分配），速度慢。

(棧頂)top

(棧底)bottom61004麥宏巖83…61003程可國6961002鞏號文7261001方飛飛96順序?？臻g

出棧進(jìn)棧

61001方飛飛9661004麥宏巖08361002鞏浩文72top61003程可國69…鏈?？臻g

進(jìn)棧出棧4順序棧類的設(shè)計(jì)━━采用面向?qū)ο蟪绦蛟O(shè)計(jì)順序棧類模板StackSeq的設(shè)計(jì)：㈠私有成員數(shù)據(jù)：①inttop;//棧頂指針（對于順序棧，棧頂位置就是棧頂元素的下標(biāo)）②T*elements;//?？臻g首地址（對于順序棧，?？臻g是T類型的數(shù)組，開在動(dòng)態(tài)存儲區(qū)）③intmax;//?？臻g中最多容納的元素個(gè)數(shù)（對順序棧，就是?？臻g數(shù)組的長度）(棧底)bottom

(棧頂)

top...............

順序?？臻g中最多可容納max個(gè)元素

出棧進(jìn)棧

（?？臻g首地址）elements5順序棧類的設(shè)計(jì)━━采用面向?qū)ο蟪绦蛟O(shè)計(jì)㈡公有成員函數(shù)：

①StackSeq(int=20);//構(gòu)造函數(shù)（參數(shù)省略時(shí)，默認(rèn)?？臻g中最多容納20個(gè)元素）

②~StackSeq();//析構(gòu)函數(shù)（釋放動(dòng)態(tài)存儲區(qū)的?？臻g）

③voidpush(Td);//壓棧（將d元素壓入棧中，本操作top將改變）④Tpop();//出棧（彈出棧頂元素并返回，本操作top將改變）

⑤Tget(intk);//讀取并返回棧內(nèi)第k號元素（元素編號為第0~top號，本操作top不變）⑥intlength();//求出棧內(nèi)元素的個(gè)數(shù)⑦voidprint();//輸出棧內(nèi)所有元素（將第0~top號的元素依次輸出，本操作top不變）⑧voidempty();//清空棧（使棧內(nèi)無任何元素，即空棧）

⑨boolisEmpty();//判斷棧是否為空⑩boolisFull();//判斷棧是否已滿

6【例】（順序棧類模板StackSeq的定義，以“stackseq.h”為文件名保存。）#include<>template<typenameT>classStackSeq//順序棧類模板StackSeq的聲明{inttop;//棧頂指針（對于順序棧，棧頂位置就是棧頂元素的下標(biāo)）

T*elements;//?？臻g首地址（對于順序棧，?？臻g是T類型的數(shù)組，開在動(dòng)態(tài)存儲區(qū)）

intmax;//?？臻g中最多容納的元素個(gè)數(shù)（對于順序棧，就是?？臻g數(shù)組的長度）public:

StackSeq(int=20);//構(gòu)造函數(shù)（參數(shù)省略時(shí)，默認(rèn)棧空間中最多容納20個(gè)元素）

~StackSeq();//析構(gòu)函數(shù)（釋放動(dòng)態(tài)存儲區(qū)的?？臻g）voidpush(Td);//壓棧（將d元素壓入棧中，本操作top將改變）

Tpop();//出棧（彈出棧頂元素并返回，本操作top將改變）

Tget(intk);//讀取并返回棧內(nèi)第k號元素（元素編號為第0~top號，本操作top不變）

intlength();//求出棧內(nèi)元素的個(gè)數(shù)

voidprint();//輸出棧內(nèi)所有元素（將第0~top號的元素依次輸出，本操作top不變）

voidempty();//清空棧（使棧內(nèi)無任何元素，即空棧）

boolisEmpty();//判斷棧是否為空

boolisFull();//判斷棧是否已滿};7//構(gòu)造函數(shù)template<typenameT>

StackSeq<T>::StackSeq(intn){

top=-1;//棧頂top為-1時(shí)，表示空棧

elements

=

newT[n];//在堆區(qū)建立?？臻g（T類型數(shù)組，首地址存放在elements中）

max=n;

//?？臻g中最多容納的元素個(gè)數(shù)（也就是?？臻g數(shù)組的長度）

assert(

elements!=0

);}

//分配不成功，則結(jié)束程序//析構(gòu)函數(shù)template<typenameT>

StackSeq<T>::~StackSeq(){delete[]elements;}

//釋放動(dòng)態(tài)存儲區(qū)的?？臻g//壓棧template<typenameT>

void

StackSeq<T>::push(Td){assert(

!isFull()

);//棧滿，則結(jié)束程序elements[++top]=d;}

//棧頂指針先加1，元素d再進(jìn)棧//出棧template<typenameT>

T

StackSeq<T>::pop(){assert(

!isEmpty()

);//?？?，則結(jié)束程序returnelements[top--];}//返回棧頂元素，然后棧頂指針減1

8//讀取并返回棧內(nèi)第k號元素（棧內(nèi)元素編號為第0~top號）template<typenameT>

T

StackSeq<T>::get(intk){

assert(

k>=0&&k<=top

);//超出棧內(nèi)有效數(shù)據(jù)范圍，則結(jié)束程序returnelements[k];}

//本操作top不變//求出棧內(nèi)元素的個(gè)數(shù)template<typenameT>

int

StackSeq<T>::length(){return(top+1);}//輸出棧內(nèi)所有元素（將第0~top號的元素依次輸出）template<typenameT>

void

StackSeq<T>::print(){

for(inti=0;i<=top;i++)cout<<elements[i];}//本操作top不變//清空棧（使棧內(nèi)無任何元素，即空棧）template<typenameT>

void

StackSeq<T>::empty(){top=-1;}

//判斷棧是否為空template<typenameT>

bool

StackSeq<T>::isEmpty(){return(top==-1);}//判斷棧是否已滿template<typenameT>

bool

StackSeq<T>::isFull(){return(top==max-1);}9順序棧類的應(yīng)用舉例【例】（在文件s1.txt中，有若干學(xué)生成績資料。要求：以Student類作為順序棧元素的數(shù)據(jù)類，對順序棧類模板StackSeq中的各成員函數(shù)進(jìn)行測試。學(xué)生類Student的聲明，前面例子中已出現(xiàn)，并以“student.h”為文件名保存。）#include<>#include<stdlib.h>#include“”#include“”voidmain(){ifstreaminf(“s1.txt”,ios::in|ios::nocreate);if(!inf){cout<<“無法打開文件s1.txt!\n”;exit(1);}

StackSeq<Student>s_SS(10);

//定義學(xué)生棧s_SS

Students;cout<<“依次壓入s_SS棧中…\n”;while(inf>>s

&&

!s_SS.isFull()

)s_SS.push(s);

inf.close();在s1.txt中，學(xué)生資料：61001方飛飛9661002鞏浩文7261003程可國6961004麥宏巖3361005文一奇9761006王碧方9910cout<<“s_SS棧內(nèi)元素個(gè)數(shù)=”<<s_SS.length()<<endl;cout<<“s_SS棧內(nèi)元素有：\n”;

s_SS.print();cout<<“s_SS棧內(nèi)0號元素是：\n”<<s_SS.get(0);cout<<“s_SS棧內(nèi)3號元素是：\n”<<s_SS.get(3);cout<<“s_SS棧內(nèi)元素個(gè)數(shù)=”<<s_SS.length()<<endl;cout<<“依次全部出棧…\n”;while(!s_SS.isEmpty())cout<<s_SS.pop();

cout<<“s_SS棧內(nèi)元素個(gè)數(shù)=”<<s_SS.length()<<endl;

cout<<s_SS.pop();}運(yùn)行：依次壓入s_SS棧中…s_SS棧內(nèi)元素個(gè)數(shù)=6s_SS棧內(nèi)元素有：61001方飛飛9661002鞏浩文7261003程可國6961004麥宏巖3361005文一奇9761006王碧方99s_SS棧內(nèi)的0號元素是：61001方飛飛96s_SS棧內(nèi)的3號元素是：61004麥宏巖33s_SS棧內(nèi)元素個(gè)數(shù)=6依次全部出?！?1006王碧方9961005文一奇9761004麥宏巖3361003程可國6961002鞏浩文7261001方飛飛96s_SS棧內(nèi)元素個(gè)數(shù)=0Assertionfailed：!isEmpty()11【例】（使用順序棧類模板StackSeq，建立整數(shù)棧i_SS、字符棧c_SS，隨機(jī)產(chǎn)生6個(gè)范圍在0~9之間的整數(shù)、6個(gè)范圍在A~Z之間的字母，依次進(jìn)各棧，再出各棧。）#include<iostream.h>#include<stdlib.h>#include“”voidmain(){StackSeq<int>i_SS(6);StackSeq<char>c_SS(8);cout<<“依次進(jìn)棧…\n”;cout<<“整數(shù)棧：\t字符棧：\n”;for(inti=0;i<6;i++){i_SS.push(rand()%10);

c_SS.push(rand()%26+65);

cout<<i_SS.get(i)<<“\t\t”<<c_SS.get(i)<<endl;}12if(i_SS.isFull())cout<<“整數(shù)棧已滿!\n”;elsecout<<“整數(shù)棧未滿，可再壓入”<<6-i_SS.length()<<“個(gè)!\n”;if(c_SS.isFull())cout<<“字符棧已滿!\n”;elsecout<<“字符棧未滿，可再壓入”<<8-c_SS.length()<<“個(gè)!\n”;cout<<“依次出?！璡n”;cout<<“整數(shù)棧：\t字符棧：\n”;for(i=0;i<6;i++)cout<<i_SS.pop()<<“\t\t”<<c_SS.pop()<<endl;if(i_SS.isEmpty())cout<<“整數(shù)棧已空!\n”;if(c_SS.isEmpty())cout<<“字符棧已空!\n”;

}運(yùn)行：依次進(jìn)?！麛?shù)棧：字符棧：1H4G9U8E2Y5N整數(shù)棧已滿！字符棧未滿，可再壓入2個(gè)!依次進(jìn)?！麛?shù)棧：字符棧：5N2Y8E9U4GH整數(shù)棧已空！字符棧已空！13【例】（棧結(jié)構(gòu)應(yīng)用于表達(dá)式優(yōu)先級的實(shí)現(xiàn)。若有+-*/運(yùn)算符和等號=組成的算術(shù)表達(dá)式，只有兩個(gè)優(yōu)先級(先*/后+-)。設(shè)：A+B*C-D/E=；實(shí)現(xiàn)運(yùn)算符的優(yōu)先級。）【算法】定義兩個(gè)棧：操作數(shù)棧

n_S，運(yùn)算符棧

c_S。從左往右掃描算術(shù)表達(dá)式，遇到操作數(shù)，則壓入n_S棧；遇到運(yùn)算符，則與c_S棧棧頂運(yùn)算符比較優(yōu)先級，若新運(yùn)算符優(yōu)先級高，或此時(shí)c_S?？?，則壓入c_S棧；否則將c_S棧棧頂運(yùn)算符出棧，與n_S棧出棧的兩個(gè)操作數(shù)進(jìn)行運(yùn)算，結(jié)果壓入n_S棧，再將新運(yùn)算符壓入c_S棧。繼續(xù)掃描，直至遇到＝號，掃描結(jié)束。兩棧的元素繼續(xù)按前面規(guī)則出棧運(yùn)算。

n_Sc_SAC+B*B*C→T1D/E→T2-n_Sc_SAD+T1/E-n_Sc_SAT2+T1A+T3→T4T1-T2→T3n_Sc_SA+T314鏈棧類的設(shè)計(jì)━━采用面向?qū)ο蟪绦蛟O(shè)計(jì)結(jié)點(diǎn)類模板Node的聲明：前面例子中已出現(xiàn)，并以“node.h”為文件名保存。結(jié)點(diǎn)類模板Node的成員：㈠私有成員數(shù)據(jù)：①數(shù)據(jù)域：Tdata;//T類型的變量data

②鏈域：Node<T>*next;//next為指向下一個(gè)結(jié)點(diǎn)的指針㈡公有成員函數(shù)：

①Node

();//表頭結(jié)點(diǎn)的構(gòu)造

②Node

(Td);//普通結(jié)點(diǎn)的構(gòu)造

③voidset

(Td);//將當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)域置為d④Tget();//獲取并返回當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)域

⑤voidshow();//輸出當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)域㈢友元函數(shù)、友元類：

friendclassListLink<T>;

//友元類，鏈表類可以訪問結(jié)點(diǎn)類的私有、保護(hù)成員

friendclassStackLink<T>;

//友元類，鏈棧類可以訪問結(jié)點(diǎn)類的私有、保護(hù)成員

friendclassQueueLink<T>;

//友元類，鏈隊(duì)列類可以訪問結(jié)點(diǎn)類的私有、保護(hù)成員15鏈棧類的設(shè)計(jì)━━采用面向?qū)ο蟪绦蛟O(shè)計(jì)鏈棧類模板StackLink的設(shè)計(jì)：㈠私有成員數(shù)據(jù)：①Node<T>*top;㈡公有成員函數(shù)：

①StackLink();//構(gòu)造函數(shù)（空棧）

②~StackLink();//析構(gòu)函數(shù)（釋放棧內(nèi)各結(jié)點(diǎn)的動(dòng)態(tài)空間）

③voidpush(Td);//壓棧（將d元素壓入棧中，本操作top將改變）④Tpop();//出棧（彈出棧頂元素并返回，本操作top將改變）

⑤TgetTop();//讀取并返回棧頂元素（本操作top不變）⑥intlength();//求出棧內(nèi)元素的個(gè)數(shù)⑦voidprint();//輸出棧內(nèi)所有元素（本操作top不變）⑧voidempty();//清空棧（使棧內(nèi)無任何元素，即空棧）

⑨boolisEmpty();//判斷棧是否為空61001方飛飛9661004麥宏巖08361002鞏浩文72top…鏈?？臻g

進(jìn)棧出棧16【例】（鏈棧類模板StackLink的定義，以“stacklink.h”為文件名保存。）#include<>template<typenameT>classStackLink//鏈棧類模板StackLink的聲明{Node<T>*top;//指向棧頂結(jié)點(diǎn)的指針

public:

StackLink

(){top=NULL;}

//構(gòu)造函數(shù)（空棧）~StackLink

(){empty();}

//析構(gòu)函數(shù)（釋放棧內(nèi)各結(jié)點(diǎn)的動(dòng)態(tài)空間）voidpush(Td);//壓棧（將d元素壓入棧中，本操作top將改變）

Tpop();//出棧（彈出棧頂元素并返回，本操作top將改變）

TgetTop()//讀取并返回棧頂元素（本操作top不變）{assert(

!isEmpty()

);returntop->data

;}intlength();//求出棧內(nèi)元素的個(gè)數(shù)

voidprint();//輸出棧內(nèi)所有元素（本操作top不變）voidempty();//清空棧（使棧內(nèi)無任何元素，即空棧）

boolisEmpty(){returntop==NULL;}

//判斷棧是否為空};17{assert(!isFull());//隊(duì)列滿，則結(jié)束程序②非連續(xù)存儲方式：鏈棧。cout<<“s_QS隊(duì)列中元素個(gè)數(shù)=”<<s_QS.{ifstreaminf(“s1.boolisFull();//判斷棧是否已滿cout<<“s_QS隊(duì)列中2號元素是：\n”<<s_QS.cout<<“s_SL棧內(nèi)元素有：\n”;if(!inf){cout<<“無法打開文件s1.{ifstreaminf(“s1.s_SS棧內(nèi)元素個(gè)數(shù)=0~QueueLink(){empty();}//析構(gòu)函數(shù)（釋放隊(duì)列中各結(jié)點(diǎn)的動(dòng)態(tài)空間）StackSeq<char>c_SS(8);61004麥宏巖33⑨boolisEmpty();//判斷棧是否為空③voidenter(Td);//進(jìn)隊(duì)（將d元素加入到隊(duì)尾，本操作rear將改變）while(top!=NULL){temp=top;top=top->next;deletetemp;}}//壓棧（將d元素壓入棧中，本操作top將改變）template<typenameT>

void

StackLink<T>::push(Td){Node<T>*pnew=newNode<T>(d);pnew->next=top;top=pnew;}//出棧（彈出棧頂元素并返回，本操作top將改變）

template<typenameT>

T

StackLink<T>::pop(){assert(

!isEmpty()

);//?？?，則結(jié)束程序

Node<T>*temp=top;top=top->next;Tda=temp->data;deletetemp;returnda;}18//求出棧內(nèi)元素的個(gè)數(shù)template<typenameT>

int

StackLink<T>::length(){Node<T>*temp=top;intcount=0;

while(temp!=NULL){

count++;

temp=temp->next;}returncount;}//輸出棧內(nèi)所有元素（本操作top不變）template<typenameT>

void

StackLink<T>::print(){Node<T>*temp=top;

while(temp!=NULL){cout<<temp->data;temp=temp->next;}

}

//清空棧（使棧內(nèi)無任何元素，即空棧）template<typenameT>

void

StackLink<T>::empty(){Node<T>*temp;

while(top!=NULL

){

temp=top;

top=top->next;deletetemp;}

}19鏈棧類的應(yīng)用舉例【例】（在文件s1.txt中，有若干學(xué)生成績資料。要求：以Student類作為鏈棧結(jié)點(diǎn)的數(shù)據(jù)類，對鏈棧類模板StackLink中的各成員函數(shù)進(jìn)行測試。學(xué)生類Student的聲明，前面例子中已出現(xiàn)，并以“student.h”為文件名保存。）#include<>#include<stdlib.h>#include“”#include“”#include“”voidmain(){ifstreaminf(“s1.txt”,ios::in|ios::nocreate);if(!inf){cout<<“無法打開文件s1.txt!\n”;exit(1);}

StackLink<Student>s_SL;

//定義學(xué)生棧s_SL

Students;cout<<“依次壓入s_SL棧中…\n”;while(inf>>s

)s_SL.push(s);

inf.close();在s1.txt中，學(xué)生資料：61001方飛飛9661002鞏浩文7261003程可國6961004麥宏巖3361005文一奇9761006王碧方9920voidpush(Td);//壓棧（將d元素壓入棧中，本操作top將改變）Students;⑨boolisEmpty();//判斷隊(duì)列是否為空要求：以Student類作為順序隊(duì)列元素的數(shù)據(jù)類，對順序循環(huán)隊(duì)列類模板QueueSeq中的各成員函數(shù)進(jìn)行測試。隊(duì)列結(jié)構(gòu)━━順序隊(duì)列、鏈隊(duì)列8Evoidmain()學(xué)生類Student的聲明，前面例子中已出現(xiàn)，并以“student.61006王碧方99整數(shù)棧：字符棧：while(inf>>s)s_QL.{return((rear-front+max)%max);}//析構(gòu)函數(shù)（釋放動(dòng)態(tài)存儲區(qū)的隊(duì)列空間）cout<<“s_SL棧內(nèi)元素個(gè)數(shù)=”<<s_SL.length()<<endl;cout<<“s_SL棧內(nèi)元素有：\n”;

s_SL.print();cout<<“s_SL棧頂元素是：\n”<<s_SL.getTop();cout<<“s_SL棧內(nèi)元素個(gè)數(shù)=”<<s_SL.length()<<endl;cout<<“依次全部出?！璡n”;while(!s_SL.isEmpty())cout<<s_SL.pop();

cout<<“s_SL棧內(nèi)元素個(gè)數(shù)=”<<s_SL.length()<<endl;

cout<<s_SL.pop();}運(yùn)行：依次壓入s_SL棧中…s_SL棧內(nèi)元素個(gè)數(shù)=6s_SL棧內(nèi)元素有：61006王碧方9961005文一奇9761004麥宏巖3361003程可國6961002鞏浩文7261001方飛飛96s_SL棧頂元素是：61006王碧方99s_SL棧內(nèi)元素個(gè)數(shù)=6依次全部出?！?1006王碧方9961005文一奇9761004麥宏巖3361003程可國6961002鞏浩文7261001方飛飛96s_SL棧內(nèi)元素個(gè)數(shù)=0Assertionfailed：!isEmpty()21隊(duì)列結(jié)構(gòu)━━順序隊(duì)列、鏈隊(duì)列隊(duì)列的邏輯結(jié)構(gòu)━━是限制插入和刪除操作分別在兩端進(jìn)行的線性結(jié)構(gòu)。

①隊(duì)頭與隊(duì)尾：指線性表的兩端。能進(jìn)行插入的一端稱隊(duì)尾（rear）；能進(jìn)行刪除的一端稱隊(duì)頭（front）。在隊(duì)尾加入新元素稱進(jìn)隊(duì)；在隊(duì)頭刪除元素稱出隊(duì)。

②特殊線性表：是先進(jìn)先出（FIFO：FirstInFirstOut）結(jié)構(gòu)的線性表。進(jìn)隊(duì)時(shí)：隨隊(duì)尾加入元素，隊(duì)尾指針（rear）不斷向后移。出隊(duì)時(shí)：隨隊(duì)頭元素的出隊(duì)，隊(duì)頭指針（front）也不斷向后移。即：進(jìn)隊(duì)與出隊(duì)都是隊(duì)尾和隊(duì)頭指針的位置在變。隊(duì)列的物理結(jié)構(gòu)━━有連續(xù)、非連續(xù)存儲兩種結(jié)構(gòu)，但邏輯功能基本相同。

①連續(xù)存儲方式：順序隊(duì)列。

②非連續(xù)存儲方式：鏈隊(duì)列。隊(duì)列結(jié)構(gòu)的應(yīng)用━━隊(duì)列是最常用、最重要的數(shù)據(jù)結(jié)構(gòu)之一。

【例】在Windows操作系統(tǒng)中，使用了很多消息等待隊(duì)列，以實(shí)現(xiàn)先來的先服務(wù)。22順序隊(duì)列的物理結(jié)構(gòu)━━連續(xù)存儲

①可以隨機(jī)訪問順序隊(duì)列中的元素。

②需要先開一定量的內(nèi)存空間，使用時(shí)有可能溢出。③順序隊(duì)列的操作執(zhí)行簡單，速度快。

鏈隊(duì)列的物理結(jié)構(gòu)━━非連續(xù)存儲

①只能順序訪問鏈隊(duì)列中的元素。

②隨用隨開內(nèi)存空間，使用時(shí)不可能溢出。③鏈隊(duì)列的操作執(zhí)行復(fù)雜（不斷地動(dòng)態(tài)分配），速度慢。

隊(duì)列結(jié)構(gòu)━━順序隊(duì)列、鏈隊(duì)列61004麥宏巖83…61003程可國6961002鞏號文7261001方飛飛96rear（隊(duì)尾）進(jìn)隊(duì)出隊(duì)（隊(duì)頭）front元素相對的移動(dòng)方向隊(duì)頭、隊(duì)尾指針的移動(dòng)方向（隊(duì)頭）front出隊(duì)61001方飛飛96…61002鞏浩文7261003程可國6961004麥宏巖083（隊(duì)尾）rear進(jìn)隊(duì)23順序循環(huán)隊(duì)列類的設(shè)計(jì)━━采用面向?qū)ο蟪绦蛟O(shè)計(jì)對順序隊(duì)列的分析：

空隊(duì)時(shí)，隊(duì)頭指針front（下標(biāo)）和隊(duì)尾指針rear（下標(biāo)）重疊在一起，都為-1。進(jìn)隊(duì)時(shí)隨著隊(duì)尾加入元素，隊(duì)尾指針（rear）不斷加1移動(dòng)；出隊(duì)時(shí)隨著隊(duì)頭元素的出隊(duì)，隊(duì)頭指針（front）也不斷加1移動(dòng)。進(jìn)隊(duì)和出隊(duì)都是隊(duì)尾和隊(duì)頭指針的位置在變（若要位置不變，移動(dòng)元素工作量太大），最后造成分配給隊(duì)列的存儲空間前端不能再被利用，而后端逐漸產(chǎn)生溢出。rearfrontArearfrontrearfrontDCBArearfrontJIHGFEDCDCrearfront（空隊(duì)）（A進(jìn)隊(duì)）（BCD進(jìn)隊(duì)）（AB出隊(duì)）（EFGHIJ進(jìn)隊(duì)）順序隊(duì)列空間987654321024順序循環(huán)隊(duì)列類的設(shè)計(jì)━━采用面向?qū)ο蟪绦蛟O(shè)計(jì)順序循環(huán)隊(duì)列：將順序隊(duì)列做成一個(gè)邏輯上的循環(huán)隊(duì)列；而這樣做會使得：空隊(duì)時(shí)rear=front，滿隊(duì)時(shí)rear=front；為了區(qū)分空隊(duì)與滿隊(duì)，在隊(duì)列中少放一個(gè)元素，即隊(duì)列中只剩下一個(gè)空位置時(shí)就算滿隊(duì)，以此作為標(biāo)志來區(qū)分空隊(duì)與滿隊(duì)。01234567frontrearABCDE（ABCDE進(jìn)隊(duì)）01234567rearfront（空隊(duì)）DC01234567Erearfront（AB出隊(duì)）01234567FfrontrearCDEGHI（FGHI進(jìn)隊(duì)、滿隊(duì)）25順序循環(huán)隊(duì)列類的設(shè)計(jì)━━采用面向?qū)ο蟪绦蛟O(shè)計(jì)順序循環(huán)隊(duì)列類模板QueueSeq的設(shè)計(jì)：㈠私有成員數(shù)據(jù)：①intrear,front;//隊(duì)尾、隊(duì)頭指針（對于順序隊(duì)列，就是隊(duì)尾、隊(duì)頭位置的下標(biāo)）②T*elements;//隊(duì)列空間的首地址（隊(duì)列空間是T類型的數(shù)組，開在動(dòng)態(tài)存儲區(qū)）③intmax;//隊(duì)列空間最多可容納的元素個(gè)數(shù)+1（也就是隊(duì)列空間數(shù)組的長度）㈡公有成員函數(shù)：

①Q(mào)ueueSeq(int=20);//構(gòu)造函數(shù)（參數(shù)省略時(shí)，隊(duì)列空間默認(rèn)最多容納19個(gè)元素）

②~QueueSeq();//析構(gòu)函數(shù)（釋放動(dòng)態(tài)存儲區(qū)的隊(duì)列空間）

③voidenter(Td);//新元素d從隊(duì)尾進(jìn)隊(duì)（rear改變）④Tleave();//隊(duì)頭元素出隊(duì)（front改變，返回出隊(duì)的元素）

⑤Tget(intk);//讀取并返回隊(duì)列中的第k號元素（隊(duì)頭元素編號為1。front不變）

⑥intlength();//求出隊(duì)列中元素的個(gè)數(shù)⑦voidprint();//輸出隊(duì)列中的所有元素（從隊(duì)頭元素開始輸出。front不變）⑧voidempty();//清空隊(duì)列（使隊(duì)列中無任何元素，即空隊(duì)）

⑨boolisEmpty();//判斷隊(duì)列是否為空⑩boolisFull();//判斷隊(duì)列是否已滿

26【例】（順序循環(huán)隊(duì)列類模板QueueSeq的聲明，以“queueseq.h”為文件名保存。）#include<assert.h>template<typenameT>classQueueSeq//順序循環(huán)隊(duì)列類模板QueueSeq的聲明{intrear,front;//隊(duì)尾、隊(duì)頭指針（對于順序隊(duì)列，就是隊(duì)尾、隊(duì)頭位置的下標(biāo)）

T*elements;//隊(duì)列空間的首指針（隊(duì)列空間是T類型的數(shù)組，開在動(dòng)態(tài)存儲區(qū)）

intmax;//隊(duì)列空間最多可容納的元素個(gè)數(shù)+1（也就是隊(duì)列空間數(shù)組的長度）public:

QueueSeq(int=20);//構(gòu)造函數(shù)（參數(shù)省略時(shí)，隊(duì)列空間默認(rèn)最多容納19個(gè)元素）~QueueSeq();//析構(gòu)函數(shù)（釋放動(dòng)態(tài)存儲區(qū)的隊(duì)列空間）voidenter(Td);//新元素d從隊(duì)尾進(jìn)隊(duì)（rear改變）

Tleave();//隊(duì)頭元素出隊(duì)（front改變，返回出隊(duì)的元素）

Tget(intk);//讀取并返回隊(duì)列中的第k號元素（隊(duì)頭元素編號為1號。front不變）

intlength();//求出隊(duì)列中元素的個(gè)數(shù)

voidprint();//輸出隊(duì)列中的所有元素（從隊(duì)頭元素開始輸出。front不變）

voidempty();//清空隊(duì)列（使隊(duì)列中無任何元素，即空隊(duì)）

boolisEmpty();//判斷隊(duì)列是否為空

boolisFull();//判斷隊(duì)列是否已滿

};27//構(gòu)造函數(shù)（參數(shù)省略時(shí)，隊(duì)列空間默認(rèn)最多容納19個(gè)元素）template<typenameT>

QueueSeq<T>::QueueSeq(intn){

rear=front=0;//隊(duì)尾rear等于隊(duì)頭front，表示空棧，初始值都為0

elements

=newT[n];//在堆區(qū)建立隊(duì)列空間（是T類型數(shù)組，首地址保存在elements中）

max=n;//隊(duì)列空間最多容納元素個(gè)數(shù)+1（對于順序隊(duì)列，就是隊(duì)列空間數(shù)組的長度）assert(elements!=0);}

//分配不成功，則結(jié)束程序//析構(gòu)函數(shù)（釋放動(dòng)態(tài)存儲區(qū)的隊(duì)列空間）template<typenameT>

QueueSeq<T>::~QueueSeq(){delete[]elements;}

//釋放動(dòng)態(tài)存儲區(qū)的隊(duì)列空間//新元素d從隊(duì)尾進(jìn)隊(duì)（rear改變）template<typenameT>

void

QueueSeq<T>::enter(Td){assert(!isFull());//隊(duì)列滿，則結(jié)束程序rear=(rear+1)%max;elements[rear]=d;}

//隊(duì)尾指針先加1，元素再進(jìn)隊(duì)//隊(duì)頭元素出隊(duì)（front改變，返回出隊(duì)的元素）template<typenameT>

T

QueueSeq<T>::leave(){assert(!isEmpty());//隊(duì)列空，則結(jié)束程序front=(front+1)%max;returnelements[front];}//隊(duì)頭指針先加1，隊(duì)頭元素離隊(duì)28//讀取并返回隊(duì)列中的第k號元素（隊(duì)頭元素編號為1。front不變）template<typenameT>

T

QueueSeq<T>::get(intk){

assert(k>=1&&k<=length());//超出隊(duì)列中有效數(shù)據(jù)范圍，則結(jié)束程序returnelements[(front+k)%max];}//讀取并返回隊(duì)列中的第k號元素（front不變）//求出隊(duì)列中元素的個(gè)數(shù)template<typenameT>

int

QueueSeq<T>::length(){return((rear-front+max)%max);}//輸出隊(duì)列中的所有元素（從隊(duì)頭元素開始輸出。front不變）template<typenameT>

void

QueueSeq<T>::print(){

for(inti=1;i<=length(

);i++)cout<<elements[(front+i)%max];}//清空隊(duì)列（使隊(duì)列中無任何元素，即空隊(duì)）

template<typenameT>

void

QueueSeq<T>::empty(){rear=front=0

;}

//判斷隊(duì)列是否為空template<typenameT>

bool

QueueSeq<T>::isEmpty(){return(rear==front);}//判斷隊(duì)列是否已滿template<typenameT>

bool

QueueSeq<T>::isFull(){return((rear+1)%max)==front;}29【例】（在文件s1.txt中，有若干學(xué)生成績資料。要求：以Student類作為順序隊(duì)列元素的數(shù)據(jù)類，對順序循環(huán)隊(duì)列類模板QueueSeq中的各成員函數(shù)進(jìn)行測試。學(xué)生類Student的聲明，前面例子中已出現(xiàn)，并以“student.h”為文件名保存。）#include<>#include<stdlib.h>#include“”#include“”voidmain(){ifstreaminf(“s1.txt”,ios::in|ios::nocreate);if(!inf){cout<<“無法打開文件s1.txt!\n”;exit(1);}

QueueSeq<Student>s_QS(10);

//定義學(xué)生隊(duì)列s_QSStudents;inti=0;cout<<“依次進(jìn)入sQS隊(duì)列中…\n”;while(inf>>s

&&

!s_QS.isFull()

){s_QS.enter(s);cout<<s_QS.get(++i);}

inf.close();在s1.txt中，學(xué)生資料：61001方飛飛9661002鞏浩文7261003程可國6961004麥宏巖3361005文一奇9761006王碧方99順序循環(huán)隊(duì)列類的應(yīng)用舉例30cout<<“s_QS隊(duì)列中元素個(gè)數(shù)=”<<s_QS.length()<<endl;cout<<“s_QS隊(duì)列中2號元素是：\n”<<s_QS.get(2);cout<<“s_QS隊(duì)列中5號元素是：\n”<<

s_QS.get(5);cout<<“s_QS隊(duì)列中元素個(gè)數(shù)=”<<

s_QS.length()<<endl;cout<<“現(xiàn)在前3位依次出隊(duì)：\n”;for(i=1;(i<=3&&!s_QS.isEmpty());i++)cout<<s_QS.leave();cout<<“s_QS隊(duì)列中元素有：\n”;

s_QS.print();

cout<<“s_QS隊(duì)列中元素個(gè)數(shù)=”<<s_QS.length()<<endl;}運(yùn)行：依次進(jìn)入s_QS隊(duì)列中…61001方飛飛9661002鞏浩文7261003程可國6961004麥宏巖3361005文一奇9761006王碧方99sQS隊(duì)列中元素個(gè)數(shù)=6s_QS隊(duì)列中2號元素是：61002鞏浩文72s_QS隊(duì)列中5號元素是：61005文一奇97s_QS隊(duì)列中元素個(gè)數(shù)=6前3位依次出隊(duì)：61001方飛飛9661002鞏浩文7261003程可國69s_QS隊(duì)列中元素有：61004麥宏巖3361005文一奇9761006王碧方99s_QS隊(duì)列中元素個(gè)數(shù)=331順序循環(huán)隊(duì)列類的設(shè)計(jì)━━采用面向?qū)ο蟪绦蛟O(shè)計(jì)cout<<“依次壓入s_SS棧中…\n”;⑨boolisEmpty();//判斷棧是否為空while(inf>>s)s_QL.61003程可國6961006王碧方9961002鞏浩文72template<typenameT>boolStackSeq<T>::isEmpty(){return(top==-1);}61006王碧方99出隊(duì)時(shí)隨著隊(duì)頭元素的出隊(duì)，隊(duì)頭指針（front）也不斷加1移動(dòng)。順序循環(huán)隊(duì)列類的設(shè)計(jì)━━采用面向?qū)ο蟪绦蛟O(shè)計(jì)if(c_SS.front=(front+1)%max;returnelements[front];}//隊(duì)頭指針先加1，隊(duì)頭元素離隊(duì)//出隊(duì)（隊(duì)頭元素離隊(duì)，并返回其值，本操作front將改變）⑨boolisEmpty();//判斷棧是否為空while(top!=NULL){temp=top;top=top->next;deletetemp;}}鏈隊(duì)列的物理結(jié)構(gòu)━━非連續(xù)存儲鏈隊(duì)列類的設(shè)計(jì)━━采用面向?qū)ο蟪绦蛟O(shè)計(jì)結(jié)點(diǎn)類模板Node的聲明：前面例子中已出現(xiàn)，并以“node.h”為文件名保存。結(jié)點(diǎn)類模板Node的成員：㈠私有成員數(shù)據(jù)：①數(shù)據(jù)域：Tdata;//T類型的變量data

②鏈域：Node<T>*next;//next為指向下一個(gè)結(jié)點(diǎn)的指針㈡公有成員函數(shù)：

①Node

();//表頭結(jié)點(diǎn)的構(gòu)造

②Node

(Td);//普通結(jié)點(diǎn)的構(gòu)造

③voidset

(Td);//將當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)域置為d④Tget();//獲取并返回當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)域

⑤voidshow();//輸出當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)域㈢友元函數(shù)、友元類：

friendclassListLink<T>;

//友元類，鏈表類可以訪問結(jié)點(diǎn)類的私有、保護(hù)成員

friendclassStackLink<T>;

//友元類，鏈棧類可以訪問結(jié)點(diǎn)類的私有、保護(hù)成員

friendclassQueueLink<T>;

//友元類，鏈隊(duì)列類可以訪問結(jié)點(diǎn)類的私有、保護(hù)成員32鏈隊(duì)列類的設(shè)計(jì)━━采用面向?qū)ο蟪绦蛟O(shè)計(jì)鏈隊(duì)列類模板QueueLink的設(shè)計(jì)：㈠私有成員數(shù)據(jù)：①Node<T>*rear,*front;//指向隊(duì)尾結(jié)點(diǎn)、隊(duì)頭結(jié)點(diǎn)的指針㈡公有成員函數(shù)：

①Q(mào)ueueLink();//構(gòu)造函數(shù)（空隊(duì)列）

②~QueueLink();//析構(gòu)函數(shù)（釋放隊(duì)列中各結(jié)點(diǎn)的動(dòng)態(tài)空間）

③voidenter(Td);//進(jìn)隊(duì)（將d元素加入到隊(duì)尾，本操作rear將改變）④Tleave();//出隊(duì)（隊(duì)頭元素離隊(duì)，并返回其值，本操作front將改變）

⑤TgetFront();//讀取并返回隊(duì)頭元素（本操作front不變）⑥intlength();//求出隊(duì)列中元素的個(gè)數(shù)⑦voidprint();//輸出隊(duì)列中所有元素（本操作front、rear不變）⑧voidempty();//清空隊(duì)列（使隊(duì)列中無任何元素，即空隊(duì)列）

⑨boolisEmpty();//判斷隊(duì)列是否為空（隊(duì)頭）front出隊(duì)61001方飛飛96…61002鞏浩文7261004麥宏巖083（隊(duì)尾）rear進(jìn)隊(duì)33【例】（鏈隊(duì)列類模板QueueLink的定義，以“queuelink.h”為文件名保存。）#include<>template<typenameT>classQueueLink//鏈隊(duì)列類模板QueueLink的聲明{Node<T>*rear,*front;//指向隊(duì)尾結(jié)點(diǎn)、隊(duì)頭結(jié)點(diǎn)的指針

public:

QueueLink

(){rear=front=NULL;}

//構(gòu)造函數(shù)（空隊(duì)列）~QueueLink

(){empty();}

//析構(gòu)函數(shù)（釋放隊(duì)列中各結(jié)點(diǎn)的動(dòng)態(tài)空間）voidenter(Td);//進(jìn)隊(duì)（將d元素加入到隊(duì)尾，本操作rear將改變）

Tleave();//出隊(duì)（隊(duì)頭元素離隊(duì)，并返回其值，本操作front將改變）

TgetFront()//讀取并返回隊(duì)頭元素（本操作front不變）{assert(

!isEmpty()

);returnfront->data

;}intlength();//求出隊(duì)列中元素的個(gè)數(shù)

voidprint();//輸出隊(duì)列中所有元素（本操作front、rear不變）voidempty();//清空隊(duì)列（使隊(duì)列中無任何元素，即空隊(duì)列）

boolisEmpty(){returnfront==NULL;}

//判斷隊(duì)列是否為空};