【正文】 第 4章 特殊線性表─ 棧、隊、串 棧、隊列、串是常用數(shù)據(jù)結構。其中棧與隊列不僅 可直接用于描述問題，而且大量用于算法的實現(xiàn)中。串多用于直接描述非數(shù)值的簡單信息。 從數(shù)據(jù)元素間的邏輯關系看，棧、隊列與串是線性 表，但從操作方式與種類看，它們與線性表有許多不同。因此，若把數(shù)據(jù)間邏輯關系與相應的操作作為整體看待（即作為抽象數(shù)據(jù)類型），它們應為新的數(shù)據(jù)結構。事實上，棧與隊列是操作受限的線性表，串是元素受限的線性表。盡管它們與線性表有許多 共同點，但也有不少特殊性。 167。 隊列的邏輯結構 167。 串的邏輯結構 167。 隊列 167。 棧的鏈式存貯結構 167。 棧的邏輯結構 167。 棧的順序存貯結構 167。 隊列的鏈式存貯結構 167。 多棧共享存貯空間 * 167。 串的存貯結構 167。 棧 167。 隊列的順序存儲結構 167。 串 167。 棧 167。 棧的邏輯結構 (一 ) 基本概念 棧是一種限定僅在表的一端進行插入與刪除的線性表。允許進行插入與刪除的這一端稱為棧頂，而另一端稱為棧底，不含元素的空表稱為空棧，插入與刪除分別稱進棧與出棧。見圖 40。 由于插入與刪除只能在同一端進行，所以較先進棧的元素，在進行出棧操作時，較后才能出棧。特別是，最先進棧者，最后才能出棧，而最晚進棧者，必最先出棧。因此，棧也稱作 先進后出 （ First InLast Out）的線性表，簡稱 FILO表。 在現(xiàn)實世界中，也有許多符合棧模型的例子。例如，火車扳道站、單車道死胡同等，都是棧的例子。在計算機系統(tǒng)中，棧的例子更是多見，例如，記錄中斷返回地址（斷點）的結構就是棧。 a1 a2 a3 a4 … an 棧底 棧頂 進棧 出棧 圖 40 棧示意圖 在中斷發(fā)生時，為了處理完中斷事件后恢復被中斷程序的繼續(xù)執(zhí)行，需記下斷點。在允許多級中斷的情況下，中斷處理過程仍可能被其它中斷所中斷，因此，系統(tǒng)可能同時要保存多個斷點。由于中斷恢復是先恢復最近被打斷的過程，所以斷點的保存次序與取出次序正好相反，這正好滿足棧的特性。 棧中元素除具有線性關系外，還具有先進后出的特性，所以在應用時，應根據(jù)這兩點決定是否使用棧。 通過使用棧，可以產生一定規(guī)則的排列次序。例如，我們假定有 n個元素 1， 2， …,n ，它們按 1,2, …, n 的次序進棧， i進棧時 1~(i 1)都已進過棧，其中某些因素也可以已經按規(guī)則出了棧。 每種元只 允許進一次棧。而出棧無具體規(guī)定（即可隨時出棧），每個元素位于棧頂時就可以出棧了。 這樣，每種完全進 出棧后 .出棧次序都是這 n個元素的一個全排列。全排列最多有 n! 種例如，對 n=3，則全 排列有 3!=6種，其中可能的出棧次序是： 123： 1進 —1出 —2進 —2出 —3進 —3出 132： 1進 —1出 —2進 —3進 —3出 —2出 213： 1進 —2進 —2出 —1出 3進 —3出 231： 1進 —2進 —2出 —3進 —3出 —1出 321： 1進 —2進 —3進 —3出 —2出 —1出 不可能的次序是： 3 1 2 從該例看出，在可能的出棧序列中，若對任意元素k，若它后 面有小于它的元素，則這些小于它的元素必須以“逆序”出現(xiàn)。例如， n=4時， 1423是不可能的出棧序列，因為 4后面的 23是順序排列。 據(jù)此，對于一般的 n，可設計算法，編寫一個計算機程序，找出所有的可能出棧次序和不可能出棧次序。 (二 ) 棧抽象模型 u 這里，我們將棧視為一個抽象對象 /類（亦稱 接 口），即不考慮它的具體數(shù)據(jù)結構存儲，不考慮 基本操作的實現(xiàn)，只考慮它的基本操作的接口 （輸入 /輸出）。該抽象對象 /類從面向對象觀點定 義了棧的屬性、方法。由于是抽象的，所以，該 類無具體對象，只用做派生各種對象 /類，例如， 下面將介紹的棧的順序存儲和鏈式存儲所對應的 類均是這里的抽象類的派生類。 u 從基本操作上看，棧是線性表的子集，故應當是 線性表的父類，這樣，線性表類也可以共享棧的 方法。 template class TElem //設棧元素可以是任意類型，故使用類模板，用 TElem代表可變元素類型 class TStack0 { protected: long len。 public: long GetLen(void) {return len。 }。 char IsEmpty() {return (len=0)? 1:0。 }。 virtual TElemamp。 Push(TElem amp。elem)=0。 virtual TElemamp。 Pop(void)=0。 virtual TElemamp。 GetTop(void)=0。 virtual TElemamp。 RollDown()=0。 virtual TElemamp。 RollUp()=0。 virtual void Clear()=0。 }。 下面對該類中主要部分進行說明。 u len：私有數(shù)據(jù)成員，表示棧中當前元素個數(shù)。 u GetLen(void)：返回棧長度（元素個數(shù)）。有了 len， 該 函數(shù)可直接在此實現(xiàn)。 u IsEmpty()：檢查棧是否為空，空時返回邏輯真，否則 ，返回邏輯假。該函數(shù)可直接在此實現(xiàn)。 u Push(TElem amp。elem)：進棧操作，將元素 elem壓入棧。 返回棧頂元素的引用。溢出時觸發(fā)異常。 u Pop()：出棧操作，將棧頂元素摘下，并返回其值。下溢 （棧 空）時觸發(fā)異常。 u GetTop(void)：與 Pop()類似，只是不摘下元素。 u RollDown()：將棧中元素循環(huán)向下（棧底方向）下推一個位置，棧底元素到達棧頂。 u RollUp()：將棧中元素循環(huán)向上（棧頂方向）上推一個位置，棧頂元素到達棧底。 167。 棧的順序 存貯結構 (一 ) 存貯方法 棧是一種特殊的線性結構，故它可按線性結構的存貯方式存貯，即順序與鏈式。 仍然用一維數(shù)組模擬連續(xù)的存貯空間（在此是存放棧元素的空間）。由于插入與刪除都是針對表的一端進行的，所以設置一個量指示插入 /刪除端的位置，一般稱該量為棧頂指針（指示器）。 不過，在棧底固定的順序存儲下，棧頂指示器與棧長度存在對應關系，它們二者可以互相推出。這種用一維數(shù)組與棧頂指針表示棧的結構如圖 40所示。 a1 a2 a3 a4 … … an 元素空間： 棧頂指示器： 圖 4 0 棧序存儲結構 假設棧底在地址小的一端 (二 ) 順序棧類 u 根據(jù)上面的討論，順序結構的棧的類定義如下。該類是前面介紹的抽象類 TStack0的派生類。下面就新出現(xiàn)的成分說明。 u room：指向一塊 TElem類型的動態(tài)空間，充當元素類型為 TElem的一維數(shù)組，用于存儲棧元素。 u size：記錄 room所指空間的大小。 u elemBuff：元素緩沖區(qū)，主要用于臨時存放從棧中摘取下的元素，作為函數(shù)的返回值引用。 u long ResizeRoom(long newSize)：重新分配一塊大小為 newSize的空間，并復制原數(shù)據(jù)。 u CopyRoom(TElem *objRoom, long n1, TElem* u srcRoom, long n2)：用于復制數(shù)據(jù)。 template class TElem class TStackSqu : public TStack0TElem { protected: TElem *room。 TElem elemBuff。 long size。 long CopyRoom(TElem *objRoom, long n1, TElem *srcRoom, long n2)。 long ResizeRoom(long newSize)。 public: TStackSqu()。 TStackSqu(long mSize)。 ~TStackSqu()。 virtual TElemamp。 Push(TElem amp。elem)。 virtual TElemamp。 Pop(void)。 virtual TElemamp。 GetTop(void)。 virtual TElemamp。 RollDown()。 virtual TElemamp。 RollUp()。 virtual void Clear()。 virtual void Print()。 }。 (三 ) 基本操作的實現(xiàn) 下面的程序給出了棧的連續(xù)存貯結構下的基本操作的實現(xiàn)。 由于較簡單，這里就不給出說明了。 template class TElem TStackSquTElem::TStackSqu() //構造函數(shù)，實現(xiàn)初始化 { room=NULL。 //未分配空間，置相應的標志 size=0。 len=0。 } template class TElem //另一構造函數(shù)，實現(xiàn)初始化和空間分配。 TStackSquTElem::TStackSqu(longmSize) { len=0。 room=new TElem[mSize]。 //分配 m個元素的空間 if (room==NULL) throw TExcepComm(4)。 size=mSize。 //記下空間大小 } template class TElem TStackSquTElem::~TStackSqu(){//析構函數(shù)，釋放在構造函數(shù)中所申請的空間 if (room!=NULL) delete[] room。 } template class TElem TElemamp。 TStackSquTElem::Push(TElem amp。elem) {//進棧操作，將 elem壓入棧，并返回棧頂元素 if (len=size1) {//?？臻g不足時，調用 ResizeRoom重新分配空間 long ret=ResizeRoom(size+10)。 if (ret0) throw TExcepComm(3)。 } room[len]=elem。 //elem進棧