第三章 順序存儲結構的表、堆棧和隊列

第3章順序存儲結構的表、堆棧和隊列3.1順序存儲結構3.2表和順序表

3.3堆棧和順序堆棧3.4隊列和順序隊列3.5優(yōu)先級隊列和順序優(yōu)先級隊列3.1順序存儲結構計算機所處理的所有的數(shù)據(jù)都要存儲在內存中。計算機高級語言系統(tǒng)對數(shù)據(jù)的存儲結構有四種：順序存儲結構、鏈式存儲結構、間接地址和仿真指針。其中，順序存儲結構和鏈式存儲結構是兩種最基本和最常用的存儲結構。本節(jié)討論順序存儲結構，其余三種存儲結構依次在4.1節(jié)、5.2節(jié)和7.1節(jié)中討論。順序存儲結構是計算機中的一種最基本和最主要的數(shù)據(jù)存儲結構。在順序存儲結構中，用戶向系統(tǒng)申請一塊地址連續(xù)的有限空間用于存儲數(shù)據(jù)元素集合，這樣，任意兩個在邏輯上相鄰的數(shù)據(jù)元素在物理上也必然相鄰。在C++中，向系統(tǒng)申請一塊地址連續(xù)的有限空間的方法是使用數(shù)組。數(shù)組有靜態(tài)數(shù)組和動態(tài)數(shù)組兩種。不論是靜態(tài)數(shù)組還是動態(tài)數(shù)組，其功能都是向系統(tǒng)申請一塊地址連續(xù)的有限空間，只是使用的方法不同。

C++中靜態(tài)數(shù)組向系統(tǒng)申請一塊地址連續(xù)的有限空間的方法是使用數(shù)組定義語句“［］”。當程序運行超出該靜態(tài)數(shù)組定義的范圍時，系統(tǒng)自動回收該靜態(tài)數(shù)組的地址空間。一個靜態(tài)數(shù)組定義的例子如下：＃include<stdio.h>

constintMaxSize=100;

voidmain(void){

inti;

inttemp［MaxSize］;//靜態(tài)申請MaxSize個整型元素的存儲空間

for(i=0;i<6;i++){temp［i］=i+1;printf("temp［%d］=%d＼n",i,temp［i］);//C函數(shù)輸出}}當程序運行退出主函數(shù)時，系統(tǒng)將自動回收分配給靜態(tài)數(shù)組temp的地址空間。

C++中動態(tài)數(shù)組向系統(tǒng)申請一塊地址連續(xù)的有限空間的方法是使用動態(tài)存儲分配函數(shù)。動態(tài)數(shù)組存儲空間的回收方法是當不再需要該動態(tài)數(shù)組時，使用動態(tài)存儲釋放函數(shù)。C++中動態(tài)存儲分配函數(shù)用new，動態(tài)存儲釋放函數(shù)用delete。new能自動計算要分配類型的空間大小并自動返回正確的指針類型。delete能自動釋放由new分配的存儲空間。

new的語法格式是：名字指針=new類型名(初始化值)。其中，初始化值可為空。

new分配動態(tài)數(shù)組的語法格式是：名字指針=new類型名［N］。其中，N必須是有確定值的整數(shù)型常量或變量。

delete的語法格式是：delete名字指針

delete釋放動態(tài)數(shù)組的語法格式是：delete［］名字指針上例的動態(tài)數(shù)組定義的例子如下：＃include<iostream.h>＃include<stdlib.h>

voidmain(void){inti,*temp;

constintMaxSize=100;temp=newint［MaxSize］;//動態(tài)申請MaxSize個整型元素的存儲空間

for(i=0;i<6;i++){temp［i］=i+1;//動態(tài)數(shù)組測試

cout<<"i="<<i<<"temp［i］="<<temp［i］<<endl;}delete［］temp;//釋放申請的動態(tài)存儲空間}從上例可見，靜態(tài)數(shù)組存儲空間的申請和釋放由系統(tǒng)自動完成，動態(tài)數(shù)組存儲空間的申請和釋放由用戶通過調用系統(tǒng)函數(shù)完成。設要存儲的數(shù)據(jù)元素為a0,a1,a2,a3,a4,a5，順序存儲結構（不論是用靜態(tài)數(shù)組還是用動態(tài)數(shù)組）向系統(tǒng)申請了MaxSize個ai數(shù)據(jù)類型的存儲空間，size為數(shù)組的當前數(shù)組元素個數(shù)。其內存結構示意圖如圖3―1所示。圖3―1順序存儲結構內存結構示意圖3.2表和順序表

表（List）是一種可在任意位置進行插入和刪除操作的由n（n≥0）個相同類型數(shù)據(jù)元素組成的線性結構，n是表的長度，n=0的表稱作空表。從數(shù)據(jù)元素之間的邏輯關系來劃分，數(shù)據(jù)結構可分為線性結構和非線性結構兩種。線性結構是指數(shù)據(jù)元素之間的邏輯關系為除第一個元素和最后一個元素外，每個數(shù)據(jù)元素都只有一個前驅元素和一個后繼元素。表是最簡單的一種線性結構。對表的操作方法主要有初始化構造表、在表的某一位置插入一個元素、在表的某一位置刪除一個元素、定位某個數(shù)據(jù)元素在表中的存儲位置、取表中某個存儲位置的數(shù)據(jù)元素、判表是否為空等。用順序存儲結構存儲的表稱作順序表（SequentList）。順序表中任意數(shù)據(jù)元素的存取和訪問可通過它的位置指針（即數(shù)組下標）來進行。3.2.1順序表的類定義綜合前面的討論可知，一個順序表涉及的數(shù)據(jù)成員包括數(shù)組、數(shù)組的最大元素個數(shù)和當前數(shù)組元素的個數(shù)。順序表的操作方法和前面討論的表的操作方法相同，主要有初始化構造表、在表的某一位置插入一個元素、在表的某一位置刪除一個元素、定位某個數(shù)據(jù)元素在表中的存儲位置、取表中某個存儲位置的數(shù)據(jù)元素、判表是否為空等。使用靜態(tài)數(shù)組方法的順序表的類定義如下：＃include<iostream.h>＃include<stdlib.h>constintMaxListSize=100;∥MaxListSize是問題要求的元素數(shù)目的最大值ClassSeqList

{private:Datatypedata［MaxListSize］;//抽象類型Datatype定義的數(shù)組

intsize;//數(shù)據(jù)元素個數(shù)

public:SeqList(void);//構造函數(shù)~SeqList(void);//析構函數(shù)

intListSize(void)const;//返回元素的個數(shù)sizeintListEmpty(void)const;//表空返回1；否則返回0

intFind(Datatype&item)const;//返回元素item在表中的位置

DatatypeGetData(intpos)const;//返回位置pos的元素

voidInsert(constDatatype&item,intpos);//在位置pos插入元素itemDatatypeDelete(constintpos);//刪除位置pos的元素并返回

voidClearList(void);//把表清空};3.2.2順序表的類實現(xiàn)順序表類SeqList的實現(xiàn)如下：

//構造函數(shù)。置順序表的數(shù)據(jù)元素個數(shù)size為0SeqList::SeqList(void):size(0){}//析構函數(shù)SeqList::~SeqList(void){}//返回順序表的數(shù)據(jù)元素個數(shù)sizeintSeqList::ListSize(void)const{

returnsize;}//判順序表空否，為空返回1；不空返回0intSeqList::ListEmpty(void)const{if(size==0)return1;else[KG*4]return0;}//定位元素item的位置，返回值為item在順序表中的位置；返回值為-1表示不存在intSeqList::Find(Datatype&item)const{if(size==0)return-1;inti=0;while(i<size&&item!=data［i］)i++;//尋找itemif(i<size)returni;elsereturn-1;}//返回順序表中位置pos上的元素。參數(shù)出錯時退出DatatypeSeqList::GetData(intpos)const{if(pos<0‖pos>size-1)//取的元素序號必須在0至size-1之間{cerr<<"參數(shù)pos越界出錯!"<<endl;exit(1);//參數(shù)1表示出錯退出}

returndata［pos］;}//在指定位置pos插入一個數(shù)據(jù)元素itemvoidSeqList::Insert(constDatatype&item,intpos){inti;if(size==MaxListSize){cerr<<"順序表已滿無法插入！"<<endl;exit(1);}

if(pos<0‖pos>size)//當pos等于size時表示插入在最后{

cerr<<"參數(shù)pos越界出錯!"<<endl;exit(1);}//從后向前把前一個元素遷移到后一個元素位置直到存儲位置pos為止

for(i=size;i>pos;i--)data［i］=data［i-1］;data［pos］=item;//在pos位置插入itemsize++;//數(shù)據(jù)元素個數(shù)size加1}//刪除指定位置pos上的數(shù)據(jù)元素并返回DatatypeSeqList::Delete(constintpos){if(size==0){cerr<<"順序表已空無元素可刪！"<<endl;exit(1);}if(pos<0||pos>size-1)//刪除元素序號必須在0至size-1之間{

cerr<<"參數(shù)pos越界出錯!"<<endl;exit(1);}

Datatypetemp=data［pos］;//從pos至size-2逐個元素左移,data［size-1］移入data［size-2］中

for(inti=pos;i<size-1;i++)data［i］=data［i+1］;size--;//數(shù)據(jù)元素個數(shù)size減1

returntemp;}//置順序表為空voidSeqList::ClearList(void){size=0;//數(shù)據(jù)元素個數(shù)size置為初始化值}3.2.3順序表上插入、刪除算法的效率分析順序表上的插入和刪除是順序表類中時間復雜度最高的成員函數(shù)。順序表上的插入和刪除過程的圖示如圖3―2（a）和圖3―2（b）。圖3―2（a）是在原來已有6個元素的順序表的pos=3位置插入數(shù)據(jù)元素item=13的過程圖示；圖3―2（b）是在原來已有7個元素的順序表中刪除pos=3位置的數(shù)據(jù)元素的過程圖示。圖3―2順序表上的插入和刪除

(a)插入一個數(shù)據(jù)元素；(b)刪除一個數(shù)據(jù)元素在順序表中插入一個數(shù)據(jù)元素時，算法中時間復雜度最高的部分是循環(huán)移動數(shù)據(jù)元素。循環(huán)移動數(shù)據(jù)元素的效率和插入數(shù)據(jù)元素的位置pos有關，最壞情況是pos=0，需移動size個數(shù)據(jù)元素；最好情況是pos=size，需移動0個數(shù)據(jù)元素。設Pi是在第i個存儲位置插入一個數(shù)據(jù)元素的概率，設順序表中的數(shù)據(jù)元素個數(shù)為n，當在順序表的任何位置上插入數(shù)據(jù)元素的概率相等時，有Pi=1／(n+1)，則向順序表插入一個數(shù)據(jù)元素時所需移動的數(shù)據(jù)元素的平均次數(shù)為在順序表中刪除一個數(shù)據(jù)元素時，算法中時間復雜度最高的部分也是循環(huán)移動數(shù)據(jù)元素。循環(huán)移動數(shù)據(jù)元素的效率和刪除數(shù)據(jù)元素的位置pos有關，最壞情況是pos=0，需移動size-1個數(shù)據(jù)元素；最好情況是pos=size，需移動0個數(shù)據(jù)元素。設Qi是在第i個存儲位置插入一個數(shù)據(jù)元素的概率，設順序表中已有的數(shù)據(jù)元素個數(shù)為n，當在順序表的任何位置上插入數(shù)據(jù)元素的概率相等時，有Qi=1/n，則向順序表插入一個數(shù)據(jù)元素時所需移動的數(shù)據(jù)元素的平均次數(shù)為：在順序表中定位一個數(shù)據(jù)元素時，累加計數(shù)變量i次數(shù)的分析和在順序表中刪除一個數(shù)據(jù)元素的分析類同。順序表中的其余操作都和數(shù)據(jù)元素個數(shù)n無關，因此，在上述順序表中插入和刪除一個數(shù)據(jù)元素的時間復雜度為O（n）；定位一個數(shù)據(jù)元素的時間復雜度為O（n）；其余操作的時間復雜度均為O（1）。

在進行面向對象的程序設計時，任何一個新類的設計都要考慮它的派生類對它的繼承。當把順序表上的插入和刪除成員函數(shù)設計成如圖3―3所示的方式時，任何類似順序表但對順序表上插入和刪除操作要考慮數(shù)據(jù)元素原來順序的都不能繼承它。解決這個問題的一個方法是設計一個順序表基類，然后分別設計兩個派生類，一個設計成圖3―2方式的插入和刪除成員函數(shù)，另一個設計成圖3―3方式的插入和刪除成員函數(shù)。這樣上述問題就可妥善解決。圖3―3順序表上不考慮原來順序的插入和刪除(a)插入一個數(shù)據(jù)元素；(b)刪除一個數(shù)據(jù)元素3.2.4順序表的應用例3―1編寫一個程序向順序表中插入5個整數(shù)值，然后以插入次序刪除這5個數(shù)。程序如下：

typedefintDatatype;∥具體應用時定義的數(shù)據(jù)類型Datatype

＃include"SeqList.h“∥類SeqList的定義和實現(xiàn)頭文件voidmain(void){SeqListmyList;for(inti=0;i<5;i++)∥插入5個整型元素

myList.Instert(i+10,i);cout<<"測試GetData()成員函數(shù)結果如下："<<endl;for(i=0;i<5;i++)cout<<myList.GetData(i)<<"";cout<<"測試Delete()成員函數(shù)結果如下："<<endl;for(i=0;i<5;i++)cout<<myList.Delete(0)<<"";}程序輸出為：測試GetData()成員函數(shù)結果如下：1011121314測試Delete()成員函數(shù)結果如下：1011121314在上述順序表類SeqList的定義中，數(shù)據(jù)類型Datatype是一個未定義的抽象符號。在上面我們定義數(shù)據(jù)類型Datatype為整型int，我們也可以定義數(shù)據(jù)類型Datatype為字符型char，我們還可以定義數(shù)據(jù)類型Datatype為任意一個自定義的結構體類型或一個類類型。定義數(shù)據(jù)類型Datatype為一個自定義的結構體類型的例子見本章例3―3；定義數(shù)據(jù)類型Datatype為一個類類型的概念見2.2節(jié)中類Line中對類Point類型變量的定義。下面是例3―1數(shù)據(jù)類型Datatype改為char類型的程序。typedefcharDatatype;//定義數(shù)據(jù)類型Datatype為char類型＃include"SeqList.h"voidmain(void){SeqListlist;inti;

for(i=0;i<5;i++)//插入5個字符元素

list.Insert(′A′+i,i);for(i=0;i<5;i++)//依次刪除5個字符元素并在屏幕顯示

cout<<list.Delete(0)<<“";}

此時程序的輸出為：

ABCDE3.3堆棧和順序堆棧堆棧（Stack）是一種特殊的線性表，是一種只允許在表的一端進行插入和刪除操作的線性表。堆棧中允許進行插入和刪除操作的一端稱為棧頂，另一端稱為棧底。棧頂?shù)漠斍拔恢檬莿討B(tài)的，標識棧頂當前位置的稱為棧頂指示器（或棧頂指針）。堆棧的插入和刪除操作通常稱為進棧或入棧，堆棧的刪除操作通常稱為出?；蛲藯?。當棧中沒有數(shù)據(jù)元素時稱之為空棧。根據(jù)堆棧的定義，每次進棧的數(shù)據(jù)元素都放在原當前棧頂元素之前而成為新的棧頂元素，每次退棧的數(shù)據(jù)元素都是原當前棧頂元素，這樣，最后進入堆棧的數(shù)據(jù)元素總是最先退出堆棧，因此，堆棧也稱作后進先出表。用順序存儲結構存儲的堆棧稱為順序堆棧（SequentStack）。圖3―4是一個順序堆棧的動態(tài)示意圖。圖中，最大元素個數(shù)設為6，top為棧頂指示器。圖3―4（a)表示一個空棧；圖3―4(b)表示插入一個數(shù)據(jù)元素A后的狀態(tài)；圖3―4(c)表示插入數(shù)據(jù)元素B、C、D后的狀態(tài)；圖3―4(d)表示刪除數(shù)據(jù)元素D、C后的狀態(tài)；圖3―4(e)表示刪除數(shù)據(jù)元素B、A后的狀態(tài)。圖3―4順序堆棧的動態(tài)示意圖（a)空棧；(b)插入數(shù)據(jù)元素A后；(c)插入數(shù)據(jù)元素B、C、D后；(d)刪除數(shù)據(jù)元素D、C后；(e)刪除數(shù)據(jù)元素B、A后3.3.1順序堆棧類定義和實現(xiàn)1.直接類定義和實現(xiàn)方法直接定義是指直接定義順序堆棧類，不考慮順序堆棧類數(shù)據(jù)成員對順序表類數(shù)據(jù)成員的繼承。下面的順序堆棧定義中部分類成員函數(shù)使用了內聯(lián)函數(shù)的方法。＃include<stdlib.h>＃include<iostream.h>constintMaxStackSize=100;classSeqStack

{

private:Datatypedata［MaxStackSize］;//抽象類型Datatype的數(shù)組

inttop;//棧頂位置指示器

public:SeqStack(void)//構造函數(shù){top=0;};//內聯(lián)函數(shù)方式~SeqStack(void)//析構函數(shù){};//內聯(lián)函數(shù)方式

voidPush(constDatatype&item);//把元素item入棧

DatatypePop(void);//出棧數(shù)據(jù)元素并返回

DatatypePeek(void)const;//讀棧頂數(shù)據(jù)元素并返回

intStackEmpty(void)const//堆?？辗祷?；否則返回0{return(top==0);};//內聯(lián)函數(shù)方式

intGetSize(void)const//讀棧元素個數(shù)top{returntop;};//內聯(lián)函數(shù)方式

voidClearStack(void)//清空堆棧使之為初始化狀態(tài){top=0;}//內聯(lián)函數(shù)方式};棧頂位置指示器top和順序表中的當前元素個數(shù)size的含義完全相同，只是在堆棧中用top更能反映它的棧頂位置指示器的含義，所以在此使用了不同的名字。此外，順序堆棧中的數(shù)組data［］和順序表中的數(shù)組data［］也完全相同。因此我們說，順序堆棧和順序表的邏輯結構完全相同，只是兩者允許的操作集合不同，順序表允許在任意位置插入和刪除，而順序堆棧只允許在棧頂位置插入和刪除，所以我們也可以說，順序堆棧是操作受限制的順序表。//把元素item入棧；堆棧滿時出錯退出voidSeqStack::Push(constDatatype&item){if(top==MaxStackSize){cerr<<"堆棧已滿!"<<endl;exit(1);}data［top］=item;//top的初始值為0是有效存儲單元,所以先存儲itemtop++;//然后top加1}//出棧并返回棧頂元素；堆?？諘r出錯退出DatatypeSeqStack::Pop(){if(top==0){cout<<"堆棧已空!"<<endl;exit(1);}top--;//top先減1

returndata［top］;//然后取top位置上的元素返回}//取棧頂元素返回DatatypeSeqStack::Peek(void)const{if(top==0){cerr<<"堆?？?"<<endl;exit(1);}returndata［top-1］;//top指在棧頂?shù)南乱粋€位置,取top-1上的元素返回}2.繼承類定義和實現(xiàn)方法繼承類定義指考慮順序堆棧類數(shù)據(jù)成員對順序表類數(shù)據(jù)成員繼承性的定義。

＃include"SeqList.h"classSeqStack:privateSeqList

{public:SeqStack(void);//構造函數(shù)~SeqStack(void){};//析構函數(shù)

voidPush(constDatatype&item);//元素item入棧

DatatypePop(void);//出棧元素并返回

DatatypePeek(void)const;//讀棧頂元素并返回

intStackEmpty(void)const;//?？諘r返回1;否則返回0

intGetSize(void)const;//讀棧元素個數(shù)sizevoidClearStack(void);//清空堆棧使之為初始化狀態(tài)};在以下SeqStack類的實現(xiàn)中都是調用了基類SeqList的公有成員函數(shù)，因為是private派生方式，所以此時基類SeqList的所有公有成員函數(shù)成為派生類SeqStack的私有成員函數(shù)。派生類SeqStack通過調用基類SeqList的公有成員函數(shù)來實現(xiàn)成員函數(shù)的功能。//構造函數(shù)SeqStack::SeqStack(void){SeqList();}//把元素item入棧;棧滿時出錯退出voidSeqStack::Push(constDatatype&item){if(ListSize()==MaxListSize)//基類的ListSize()返回基類的size值{

cerr<<"堆棧已滿!"<<endl;exit(1);}

Insert(item,ListSize());//在當前頂部位置插入元素}//出棧并返回棧頂元素;棧空時出錯退出DatatypeSeqStack::Pop(void){if(ListSize()==0){cerr<<"堆棧已空!"<<endl;exit(1);}returnDelete(ListSize()-1);//刪除最后存入的元素并返回}//取棧頂元素返回DatatypeSeqStack::Peek(void)const{returnGetData(ListSize()-1);//取最后存入的元素返回}//判堆?？辗?，空返回1；非空返回0intSeqStack::StackEmpty(void)const{returnListEmpty();}//讀棧元素個數(shù)sizeintSeqStack::GetSize(void)const{returnListSize();}//清空堆棧使之為初始化狀態(tài)voidSeqStack::ClearStack(void){ClearList();}上述文件名為CSeqStack.h。

3.3.2順序堆棧應用——表達式計算堆棧是各種軟件系統(tǒng)中應用最廣泛的數(shù)據(jù)結構之一。例如，表達式計算是編譯系統(tǒng)中的基本問題，其實現(xiàn)方法是堆棧的一個典型應用。在編譯系統(tǒng)中，要把便于人理解的表達式翻譯成能正確求值的機器指令序列，通常需要先把表達式變換成機器便于理解的形式，這就要變換表達式的表示序列。借助順序堆棧即可實現(xiàn)這樣的變換。在機器內部，任何一個表達式都是由操作數(shù)、運算符和分界符組成的。操作數(shù)和運算符是表達式的主要部分，分界符標志了一個表達式的結束。我們稱操作數(shù)、運算符和分界符為一個表達式的單詞。根據(jù)表達式的類型，表達式可分為三類，即算術表達式、關系表達式和邏輯表達式。為敘述簡潔，我們僅討論算術表達式的計算。算術表達式只包含加、減、乘、除、左括號和右括號。讀者不難把他推廣到其他類型表達式的計算中。假設計算機高級語言中的一個算術表達式為

A+(B-C/D)*E這種算術表達式中的運算符總是出現(xiàn)在兩個操作數(shù)之間（除單目運算符外），所以也稱為中綴表達式。編譯系統(tǒng)對中綴形式的算術表達式處理的方法是先把它轉換為后綴形式的算術表達式。后綴形式的算術表達式就是表達式中的運算符出現(xiàn)在操作數(shù)之后，并且不含括號。例如，中綴算術表達式A+B的后綴表達式為AB+。要把一個中綴算術表達式變換成相應的后綴表達式要考慮算術運算規(guī)則。算術四則運算的規(guī)則是：

（1）先乘除后加減；（2）先括號內后括號外；（3）同級別時先左后右。上面的中綴表達式寫成滿足四則運算規(guī)則的相應的后綴表達式即為

ABCD/-E*+

其運算次序為：T1=CD/；T2=BT1-；T3=T2E*；T4=AT2E+?？梢?，后綴表達式有以下兩個特點：（1）后綴表達式的操作數(shù)與中綴表達式的操作數(shù)先后次序相同，只是運算符的先后次序改變；（2）后綴表達式中沒有括號，后綴表達式的運算符次序就是其執(zhí)行次序。綜上所述，編譯系統(tǒng)中表達式的計算分為兩個步驟：（1）把中綴表達式變換成相應的后綴表達式；（2）根據(jù)后綴表達式計算表達式的值。表3―1給出了包括加、減、乘、除、左括號、右括號和分界符的算術運算符間的優(yōu)先級關系表。表中，θ1代表棧頂運算符，θ2代表當前掃描讀到的運算符。

表3―1運算符優(yōu)先級關系表表3-1是四則運算三條規(guī)則的變形。當θ1為+或-，θ2為*或/時，θ1的優(yōu)先級高于θ2的優(yōu)先級，滿足規(guī)則（1）的先乘除后加減。當θ1為+、-、*或/，θ2為“（”時，θ1的優(yōu)先級高于θ2的優(yōu)先級，滿足規(guī)則（2）的先括號內后括號外。當θ1的運算符和θ2的運算符同級別時，θ1的優(yōu)先級高于θ2的優(yōu)先級，滿足規(guī)則（3）的同級別時先左后右。幾個特殊處理考慮如下：(1)由于后綴表達式無括號，當θ1為“（”，θ2為“）”時，用標記“=”使算法在此時去掉該對括號。(2)當θ1為“＃”，θ2為“＃”時，用標記“=”使算法在此時結束處理。（3）表中值為空，表示不允許出現(xiàn)此種情況，一旦出現(xiàn)即為中綴表達式語法出錯，如θ1為“）”，θ2為“（”的情況即為中綴表達式語法出錯。為簡化下面的算法設計，我們在下邊的算法設計中未考慮此種中綴表達式語法出錯情況。根據(jù)以上分析，中綴表達式變換為后綴表達式的算法步驟是：（1）設置一個堆棧，初始時將棧頂元素置為“?！薄＃?）順序讀入中綴表達式，當讀到的單詞為操作數(shù)時就將其輸出，并接著讀下一個單詞。（3）令x1為當前棧頂運算符的變量，x2為當前掃描讀到運算符的變量，當順序從中綴表達式中讀入的單詞為運算符時就賦予x2，然后比較x1的優(yōu)先級與x2的優(yōu)先級，若x1的優(yōu)先級高于x2的優(yōu)先級，將x1退棧并作為后綴表達式的一個單詞輸出，然后接著比較新的棧頂運算符x1的優(yōu)先級與x2的優(yōu)先級。上述算法的C++實現(xiàn)如下,其中函數(shù)Proceed(charx1,charx2)完成兩個運算符x1和x2優(yōu)先級的比較，函數(shù)Postfix(SeqStack&s,char*Expression)借助堆棧s完成中綴表達式Expression到后綴表達式的轉換和輸出。主函數(shù)用中綴表達式等于“A+(B-C/D)*E＃”的例子驗證算法。圖3―5中綴表達式變換成后綴表達式的過程

＃include<string.h>typedefcharDatatype;//定義具體問題的數(shù)據(jù)類型Datatype

＃include"SeqStack.h"charProceed(charx1,charx2)//運算符x1和x2優(yōu)先級的比較{charResult;charMidString［2］;Result=′<′;//Result的初始值為′<′MidString［0］=x2;//x2賦于MidString［0］MidString［1］=0;//添字符串的結束標記0//x1大于x2。比較中利用了求子串函數(shù)strstr()if(((x1==′+′||x1==′-′)&&strstr("+-)＃",MidString)!=NULL)||((x1==′*′||x1==′/′)&&strstr("+-*/)＃",MidString)!=NULL)||(x1==′)′&&strstr("+-*/)＃",MidString)!=NULL))Result=′>′;x1等于x2elseif((x1==′(′&&x2==′)′)||(x1==′?！?&x2==′?！?)Result=′=′;//x1和x2取值出錯

elseif((x1==′(′&&x2==′?！?||(x1==′)′&&x2==′(′)||(x1==′＃′&&x2==′)′))Result=′′;//當三種情況均不是時為x1小于x2。returnResult;//返回Result}intPostfix(SeqStack&s,char*Expression)//借助堆棧s的中綴表達式Expression到后綴表達式的轉換和輸出{

charx1,x2;intj=0;s.Push(′?！?;//初始棧頂置為＃

x2=Expression［j］;//取第一個單詞給x2x1=s.Peek();//棧頂?shù)姆纸绶＝ox1while(1)//循環(huán)直到轉換完畢{

if(x2!=′+′&&x2!=′-′&&x2!=′*′&&x2!=′/′&&

x2!=′(′&&x2!=′)′&&x2!=′＃′)//x2為操作數(shù){

cout<<x2<<′′;//輸出操作數(shù)x2x2=Expression［++j］//繼續(xù)取下一個單詞給x2}elseif(Proceed(x1,x2)==′<′)//x1的優(yōu)先級<x2的優(yōu)先級{

s.Push(x2);//把x2入棧

x1=s.Peek();//取新的棧頂元素給x1x2=Expression［++j］;//繼續(xù)取下一個單詞給x2}

elseif(Proceed(x1,x2)==′>′)//x1的優(yōu)先級>x2的優(yōu)先級{

x1=s.Pop();[DW1]//退棧

cout<<x1<<′′;//輸出x1x1=s.Peek();//取新的棧頂元素給x1}//x1等于左括號x2等于右括號

elseif(Proceed(x1,x2)==′=′&&x1==′(′&&x2==′)′){s.Pop();//退棧去掉左括號

x1=s.Peek();//取新的棧頂元素給x1

x2=Expression［++j］;//重新取x2的值去掉右括號}//轉換完畢

elseif(Proceed(x1,x2)==′=′&&x1==′?！?&x2==′＃′){cout<<′?！?return1;//轉換成功返回1}

elseif(Proceed(x1,x2)==′′)break;//語法有錯{

cout<<"中綴表達式語法有錯!"<<endl;

return0；//轉換失敗返回0}

voidmain(void)//主函數(shù){

charExpression［80］={"A+(B-C/D)*E＃"};SeqStacks;Postfix(s,Expression);}程序運行輸出轉換后的后綴表達式，程序輸出為：

ABCD/-E*+

在上述程序中若想使用繼承方式的順序堆棧，只需把包含宏語句改為：＃include"CSeqStack.h"

即可。設算法中單詞個數(shù)為n，該算法對輸入的中綴表達式進行了一次從左到右的掃描，對其中每個操作數(shù)執(zhí)行了一次輸出，對每個操作符執(zhí)行進棧和出棧各一次，所以算法的時間復雜度為O（n）。上述程序的中綴表達式為"A+(B-C/D)*E"，這個中綴表達式中所有操作數(shù)變量均為單字符變量，程序中也是按單字符變量分割操作數(shù)變量的。實際上，所有計算機高級語言中均支持多字符變量，如何在此基礎上允許中綴表達式的操作數(shù)變量為多字符變量已超出了本課程討論的范圍，我們不作討論。把中綴表達式變換為后綴表達式的另一種方法是設置一個堆棧用于臨時存放操作符，給每個操作符按照四則運算規(guī)則規(guī)定一個棧內優(yōu)先數(shù)和一個棧外優(yōu)先數(shù)。當掃描到的操作符的棧外優(yōu)先數(shù)大于當前棧頂操作符的棧內優(yōu)先數(shù)時，則掃描到的操作符進棧；當掃描到的操作符的棧外優(yōu)先數(shù)小于當前棧頂操作符的棧內優(yōu)先數(shù)時，則當前棧頂操作符退棧并輸出。這個過程一直進行到?？諡橹埂@種方法的算法實現(xiàn)有興趣的讀者可參見相關文獻或自己設計。把中綴表達式變換成相應的后綴表達式后，計算后綴表達式的值的過程仍是一個堆棧應用問題。其算法思想是：設置一個堆棧存放操作數(shù)，從左到右依次掃描后綴表達式，每讀到一個操作數(shù)就將其進棧；每讀到一個運算符就從棧頂取出兩個操作數(shù)施以該運算符所代表的運算操作，并把該運算結果作為一個新的操作數(shù)入棧；此過程一直進行到后綴表達式讀完，最后棧頂?shù)牟僮鲾?shù)就是該后綴表達式的運算結果。計算后綴表達式值的算法我們將作為鏈式堆棧的應用例子在第4章中討論。圖3―6是以后綴表達式ABCD/-E*+為例說明上述算法思想的后綴表達式求值過程，其中設MaxStackSize=6。圖3―6后綴表達式求值過程3.4隊列和順序隊列

隊列（Queue）也是一種特殊的線性表，是一種只允許在表的一端進行插入操作，在表的另一端進行刪除操作的線性表。表中允許進行插入操作的一端稱為隊尾，允許進行刪除操作的一端稱為隊頭。隊頭和隊尾分別由隊頭指示器（或稱隊頭指針）和隊尾指示器（或稱隊尾指針）指示。隊列的插入操作通常稱作入隊列，隊列的刪除操作通常稱作出隊列。當隊列中沒有數(shù)據(jù)元素時稱作空隊列。根據(jù)隊列的定義，每次進隊列的數(shù)據(jù)元素都放在原來的隊尾之后成為新的隊尾元素，每次出隊列的數(shù)據(jù)元素都是原來的隊頭元素。這樣，最先入隊列的數(shù)據(jù)元素總是最先出隊列，所以隊列也稱作先進先出表。用順序存儲結構存儲的隊列稱作順序隊列（SequentQueue）。圖3―7是一個有6個存儲空間的順序隊列的動態(tài)示意圖。圖中，front為隊頭指示器，rear為隊尾指示器。

圖3―7（a)表示一個空隊列；圖3―7(b)表示入隊列數(shù)據(jù)元素A、B、C后的狀態(tài)；圖3―7(c)表示出隊列數(shù)據(jù)元素A、B后的狀態(tài)；圖3―7(d)表示入隊列數(shù)據(jù)元素D、E、F后的狀態(tài)。對隊列的操作主要有：初始化建立一個隊列、入隊列、出隊列、取隊頭數(shù)據(jù)元素和判隊列是否為空等操作。圖3―7順序隊列的動態(tài)示意圖

（a)空隊列；(b)入隊列A、B、C后的狀態(tài)；(c)出隊列A、B后的狀態(tài)；(d)入隊列D、E、F后的狀態(tài)3.4.1順序循環(huán)隊列對于順序隊列，從圖3―7(d)可以看出，此時若繼續(xù)進行入隊列操作將使隊尾指示器rear的值超出順序隊列定義的6個存儲空間的范圍而“溢出”，但此時隊列中還有2個存儲空間可供存儲，因此，這時的“溢出”并不是由于存儲空間不夠而產生的溢出，這種溢出通常稱作假溢出。由于存在假溢出問題，所以順序隊列很少在實際軟件系統(tǒng)中使用。實際軟件系統(tǒng)中使用的順序隊列基本都是這里要討論的順序循環(huán)隊列。假溢出是由于隊尾指示器rear的值和隊頭指示器front的值不能由所定義存儲空間的最大值自動轉為所定義存儲空間的最小值而產生的，因此，解決的方法是把順序隊列所使用的存儲空間構造成一個邏輯上首尾相連的循環(huán)隊列。當rear和front達到MaxQueueSize-1后，再前進一個位置就自動到0，這可以利用求模（或稱取余）運算（%）來實現(xiàn)。如何判斷順序循環(huán)隊列的隊列滿和隊列空條件呢？首先，我們看順序循環(huán)隊列隊頭指示器front和隊尾指示器rear的初始化值，設順序循環(huán)隊列的MaxQueueSize=6，令front=rear=0，其狀態(tài)如圖3―8(a)所示；當入隊列數(shù)據(jù)元素A、B、C、D、E、F后順序循環(huán)隊列滿，此時有front=rear=0，其狀態(tài)如圖3―8(b)所示；當出隊列數(shù)據(jù)元素A、B、C、D、E、F后順序循環(huán)隊列空，此時有front=rear=0，其狀態(tài)如圖3―8(c)所示。圖3―8順序循環(huán)隊列的隊列滿和隊列空狀態(tài)(a)初始化狀態(tài)；(b)隊列滿狀態(tài)；(c)隊列空狀態(tài)可見，此時隊列滿和隊列空的隊頭指示器front和隊尾指示器rear的取值狀態(tài)相同，這是無法區(qū)分的。解決的方法通常是少用一個存儲空間，以隊尾指示器rear加1等于隊頭指示器front為隊列滿的條件。即順序循環(huán)隊列的隊列滿條件為(rear+1)%MaxQueueSize==front

順序循環(huán)隊列的隊列空條件仍然為

rear==front3.4.2順序循環(huán)隊列類的定義和實現(xiàn)根據(jù)上面對順序循環(huán)隊列的分析，我們有順序循環(huán)隊列類的定義和實現(xiàn)如下：

＃include<iostream.h>＃include<stdlib.h>constintMaxQueueSize=100;classSeqQueue

{private:Datatypedata［MaxQueueSize］;//抽象類型Datatype定義的數(shù)組

intfront;//隊頭指示器

intrear;//隊尾指示器

intcount;//元素個數(shù)計數(shù)器

public:SeqQueue(void)//構造函數(shù){front=rear=0;count=0;};~SeqQueue(void){};//析構函數(shù)

voidQInsert(constDatatype&item);//入隊列

DatatypeQDelete(void);//出隊列

DatatypeQFront(void)const;//讀隊頭元素值

intQueueEmpty(void)const//判隊列是否為空{returnfront==rear;};voidClearQueue(void)//清空隊列{front=rear=0;count=0;}intGetSize(void)const//取隊列元素個數(shù){returncount;};}//把元素item入隊列voidSeqQueue::QInsert(constDatatype&item){if(count==MaxQueueSize){cerr<<"隊列已滿!"<<endl;exit(1);}data［rear］=item;//把元素item加在隊尾

rear=(rear+1)%MaxQueueSize;///隊尾指示器加1

count++;//計數(shù)器加1}//把隊頭元素出隊列，出隊列元素由返回值帶回DatatypeSeqQueue::QDelete(){Datatypetemp;if(count==0){cerr<<"隊列已空!"<<endl;exit(1);}temp=data［front］;//保存原隊頭元素值

front=(front+1)%MaxQueueSize;//隊頭指示器加1

count--;//計數(shù)器減1

returntemp;//返回原隊頭元素}//讀隊頭元素，隊頭元素由返回值帶回DatatypeSeqQueue::QFront(void)const{if(count==0){cerr<<"隊列空!"<<endl;exit(1);}returndata［front］;//返回隊頭元素}上述文件名為SeqQueue.h。一個6個元素的順序循環(huán)隊列的入隊列過程見圖3―9。其中圖3―9（a）為初始狀態(tài)，圖3―9（b）為無循環(huán)情況的入隊列過程，圖3―9（c）為循環(huán)情況的入隊列過程。圖3―9順序循環(huán)隊列的入隊列過程一個6個元素的順序循環(huán)隊列的出隊列過程見圖3―10。其中圖3―10（a）為初始狀態(tài)，圖3―10（b）為無循環(huán)情況的出隊列過程，圖3―10（c）為循環(huán)情況的出隊列過程。圖3―10順序循環(huán)隊列的出隊列過程

3.4.3順序循環(huán)隊列的應用由于順序循環(huán)隊列和順序隊列結構近似，但順序循環(huán)隊列的功能大大優(yōu)于順序隊列的功能，所以順序隊列幾乎不被采用。順序循環(huán)隊列的應用很廣泛。例如，操作系統(tǒng)中的各種數(shù)據(jù)緩沖區(qū)的先進先出管理，應用系統(tǒng)中的各種事件排隊管理，等等。這里我們討論一個用順序循環(huán)隊列和順序堆棧實現(xiàn)判斷一個字符序列是否是回文的例子。例3―2編程序判斷一個字符序列是否是回文(回文是指一個字符序列以中間字符為基準兩邊字符完全相同)。程序從鍵盤輸入一個字符序列存入字符串str中，字符串長度小于等于80，輸入字符序列以回車換行符為結束標記，字符串str中不包括回車換行符。把字符串中字符逐個分別存入隊列和堆棧，然后逐個出隊列和退棧并比較出隊列的元素和退棧的元素是否相等，若全部相等則該字符序列是回文，否則就不是回文。程序如下：＃include<string.h>typedefcharDatatype;//定義具體應用的數(shù)據(jù)類型Datatype

＃include"SeqQueue.h"＃include"SeqStack.h"voidmain(void){SeqStackmyStack;SeqQueuemyQueue;charstr［80］;cout<<"輸入字符序列，回車換行符結束："<<endl;cin.getline(str,80);//從鍵盤接收字符序列

inth=strlen(str);//求字符序列長度

for(inti=0;i<h;i++){myQueue.QInsert(str［i］);myStack.Push(str［i］);}while(!myQueue.QueueEmpty()){if(myQueue.QDelete()!=myStack.Pop()){cout<<"不是回文!"<<endl;

return;}}cout<<"是回文!"<<endl;}第一次程序運行狀態(tài)為：輸入字符序列，回車換行符結束：

ABCDEDCBA

字符序列是回文!第二次程序運行狀態(tài)為：輸入字符序列，回車換行符結束：

ABCDEDC

字符序列不是回文!判斷一個字符序列是否是回文還有更簡單的方法。這里的程序主要是為了舉例說明順序隊列類和順序堆棧類的使用方法。3.5優(yōu)先級隊列和順序優(yōu)先級隊列優(yōu)先級隊列（PriorityQueue）是帶有優(yōu)先級的隊列。隊列是數(shù)據(jù)元素的先進先出表，即最先進入隊列的元素將最先被刪除。但在有些軟件系統(tǒng)中有時也要求把進入隊列中的元素分優(yōu)先級，出隊列（即刪除）時，首先選擇優(yōu)先級最高的元素出隊列，對優(yōu)先級相同的元素則按先進先出的原則出隊列。簡單的優(yōu)先級隊列也可不考慮優(yōu)先級相同的元素的先進先出問題。3.5.1順序優(yōu)先級隊列類定義和類實現(xiàn)通常優(yōu)先級隊列的優(yōu)先級為一數(shù)值，并規(guī)定數(shù)值越小優(yōu)先級越高。一個不考慮優(yōu)先級相同元素的先進先出問題的順序優(yōu)先級隊列類的定義和實現(xiàn)如下：＃include<iostream.h>＃include<stdlib.h>

constintMaxPQueueSize=100;

classSeqPQueue

{private:

Datatypedata［MaxPQueueSize］;

//抽象類型Datatype定義的數(shù)組

intsize;

//數(shù)據(jù)元素個數(shù)

public:SeqPQueue()//構造函數(shù){size=0;}~SeqPQueue(void){}//析構函數(shù)

voidPQInsert(constDatatype&item);

//把元素item插入隊尾

DatatypePQDelete(void);//把隊頭元素刪除并由函數(shù)返回

DatatypePQFront(void)const;

//讀隊頭元素值并由函數(shù)返回

intPQueueEmpty(void)const//判隊列是否為空{returnsize==0;}voidClearPQueue(void)//清空隊列{size=0;}intGetSize(void)const//取隊列元素個數(shù){returnsize;}};voidSeqPQueue::PQInsert(constDatatype&item)//把元素item插入隊尾{

if(size==MaxPQueueSize){cout<<"隊列已滿!"<<endl;

exit(1);}data［size］=item;//把元素item加在隊尾

size++;//數(shù)據(jù)元素個數(shù)加1}DatatypeSeqPQueue::PQDelete(void)

//把優(yōu)先級最高的元素刪除并由函數(shù)返回{

if(size<=0){cout<<"隊列已空!"<<endl;exit(1);}

Datatypemin=data［0］;//初始選data［0］為優(yōu)先級最高的元素

intminIndex=0;//minIndex為優(yōu)先級最高元素的下標

for(inti=1;i<size;i++)//尋找優(yōu)先級最高的元素及對應下標

if(data［i］<min){min=data［i］;minIndex=i;}data［minIndex］=data［size-1］;//把最后一個元素放在被刪除元素的位置size--;//數(shù)據(jù)元素個數(shù)減1returnmin;//返回優(yōu)先級最高的元素}DatatypeSeqPQueue::PQFront(void)const//讀優(yōu)先級最高元素并由函數(shù)返回{

if(size<=0){cout<<"隊列已空!"<<endl;exit(1);}//方法和把優(yōu)先級最高的元素刪除并由函數(shù)返回方法類同

Datatypemin=data［0］;intminIndex=0;for(inti=1;i<size;i++)if(data［i］<min){min=data［i］;minIndex=i;}returnmin;}上述文件名為SeqPQueue.h?？紤]優(yōu)先級相同元素的先進先出問題的順序優(yōu)先級隊列，只需把出隊列成員函數(shù)改為如下形式即可。//把隊頭元素刪除并由函數(shù)返回，對相同優(yōu)先級的元素按先進先出原則刪除并返回

DatatypeSeqPQueue::PQDelete(void){

if(size<=0)

{cout<<"隊列已空!"<<endl;exit(1);}

Datatypemin=data［0］;

//初始選data［0］為優(yōu)先級最高的元素intminIndex=0;//minIndex為優(yōu)先級最高元素的下標for(inti=1;i<size;i++)

//尋找優(yōu)先級最高的