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

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

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

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

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

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

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

【例】

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

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

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

①可以隨機訪問順序棧中的元素。

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

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

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

(棧頂)top

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

出棧進棧

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

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

(棧頂)

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

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

出棧進棧

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

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

②~StackSeq();//析構(gòu)函數(shù)（釋放動態(tài)存儲區(qū)的棧空間）

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

⑤Tget(intk);//讀取并返回棧內(nèi)第k號元素（元素編號為第0~top號，本操作top不變）⑥intlength();//求出棧內(nèi)元素的個數(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ù)組，開在動態(tài)存儲區(qū)）

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

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

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

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

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

intlength();//求出棧內(nèi)元素的個數(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時，表示空棧

elements

=

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

max=n;

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

assert(

elements!=0

);}

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

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

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

void

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

!isFull()

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

//棧頂指針先加1，元素d再進棧//出棧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)元素的個數(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ù)進行測試。學(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)元素個數(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)元素個數(shù)=”<<s_SS.length()<<endl;cout<<“依次全部出?！璡n”;while(!s_SS.isEmpty())cout<<s_SS.pop();

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

cout<<s_SS.pop();}運行：依次壓入s_SS棧中…s_SS棧內(nèi)元素個數(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)元素個數(shù)=6依次全部出棧…61006王碧方9961005文一奇9761004麥宏巖3361003程可國6961002鞏浩文7261001方飛飛96s_SS棧內(nèi)元素個數(shù)=0Assertionfailed：!isEmpty()11【例】（使用順序棧類模板StackSeq，建立整數(shù)棧i_SS、字符棧c_SS，隨機產(chǎn)生6個范圍在0~9之間的整數(shù)、6個范圍在A~Z之間的字母，依次進各棧，再出各棧。）#include<iostream.h>#include<stdlib.h>#include“”voidmain(){StackSeq<int>i_SS(6);StackSeq<char>c_SS(8);cout<<“依次進棧…\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()<<“個!\n”;if(c_SS.isFull())cout<<“字符棧已滿!\n”;elsecout<<“字符棧未滿，可再壓入”<<8-c_SS.length()<<“個!\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”;

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

n_S，運算符棧

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

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è)計━━采用面向?qū)ο蟪绦蛟O(shè)計結(jié)點類模板Node的聲明：前面例子中已出現(xiàn)，并以“node.h”為文件名保存。結(jié)點類模板Node的成員：㈠私有成員數(shù)據(jù)：①數(shù)據(jù)域：Tdata;//T類型的變量data

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

①Node

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

②Node

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

③voidset

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

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

friendclassListLink<T>;

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

friendclassStackLink<T>;

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

friendclassQueueLink<T>;

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

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

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

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

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

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

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

public:

StackLink

(){top=NULL;}

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

(){empty();}

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

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

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

!isEmpty()

);returntop->data

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

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

boolisEmpty(){returntop==NULL;}

//判斷棧是否為空};17{assert(!isFull());//隊列滿，則結(jié)束程序②非連續(xù)存儲方式：鏈棧。cout<<“s_QS隊列中元素個數(shù)=”<<s_QS.{ifstreaminf(“s1.boolisFull();//判斷棧是否已滿cout<<“s_QS隊列中2號元素是：\n”<<s_QS.cout<<“s_SL棧內(nèi)元素有：\n”;if(!inf){cout<<“無法打開文件s1.{ifstreaminf(“s1.s_SS棧內(nèi)元素個數(shù)=0~QueueLink(){empty();}//析構(gòu)函數(shù)（釋放隊列中各結(jié)點的動態(tài)空間）StackSeq<char>c_SS(8);61004麥宏巖33⑨boolisEmpty();//判斷棧是否為空③voidenter(Td);//進隊（將d元素加入到隊尾，本操作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)元素的個數(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é)點的數(shù)據(jù)類，對鏈棧類模板StackLink中的各成員函數(shù)進行測試。學(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();//判斷隊列是否為空要求：以Student類作為順序隊列元素的數(shù)據(jù)類，對順序循環(huán)隊列類模板QueueSeq中的各成員函數(shù)進行測試。隊列結(jié)構(gòu)━━順序隊列、鏈隊列8Evoidmain()學(xué)生類Student的聲明，前面例子中已出現(xiàn)，并以“student.61006王碧方99整數(shù)棧：字符棧：while(inf>>s)s_QL.{return((rear-front+max)%max);}//析構(gòu)函數(shù)（釋放動態(tài)存儲區(qū)的隊列空間）cout<<“s_SL棧內(nèi)元素個數(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)元素個數(shù)=”<<s_SL.length()<<endl;cout<<“依次全部出棧…\n”;while(!s_SL.isEmpty())cout<<s_SL.pop();

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

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

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

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

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

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

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

①可以隨機訪問順序隊列中的元素。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

QueueSeq<T>::QueueSeq(intn){

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

elements

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

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

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

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

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

void

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

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

T

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

T

QueueSeq<T>::get(intk){

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

int

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

void

QueueSeq<T>::print(){

for(inti=1;i<=length(

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

template<typenameT>

void

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

;}

//判斷隊列是否為空template<typenameT>

bool

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

bool

QueueSeq<T>::isFull(){return((rear+1)%max)==front;}29【例】（在文件s1.txt中，有若干學(xué)生成績資料。要求：以Student類作為順序隊列元素的數(shù)據(jù)類，對順序循環(huán)隊列類模板QueueSeq中的各成員函數(shù)進行測試。學(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é)生隊列s_QSStudents;inti=0;cout<<“依次進入sQS隊列中…\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)隊列類的應(yīng)用舉例30cout<<“s_QS隊列中元素個數(shù)=”<<s_QS.length()<<endl;cout<<“s_QS隊列中2號元素是：\n”<<s_QS.get(2);cout<<“s_QS隊列中5號元素是：\n”<<

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

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

s_QS.print();

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

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

①Node

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

②Node

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

③voidset

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

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

friendclassListLink<T>;

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

friendclassStackLink<T>;

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

friendclassQueueLink<T>;

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

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

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

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

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

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

public:

QueueLink

(){rear=front=NULL;}

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

(){empty();}

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

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

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

!isEmpty()

);returnfront->data

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

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

boolisEmpty(){returnfront==NULL;}

//判斷隊列是否為空};