【正文】 (一 ) 非循環(huán)隊(duì)列 1．存儲方法 與棧類似，隊(duì)列也有相應(yīng)的順序存貯結(jié)構(gòu)。 u RollUp()： 將隊(duì)中元素循環(huán)向上（隊(duì)頭方向）推一 個(gè)位置，隊(duì)頭元素到達(dá)隊(duì)尾。 u GetHead(void)： 與 QPop()類似，只是不摘下元素。將隊(duì)頭元素摘下，并返回其值的引用。溢出時(shí)觸發(fā)異常。elem)： 進(jìn)隊(duì)。該函數(shù)可直接在此實(shí)現(xiàn)。該函數(shù)可直接在此實(shí)現(xiàn)。 u len： 私有數(shù)據(jù)成員，表示隊(duì)中當(dāng)前元素個(gè)數(shù)。 }。 RollUp()=0。 RollDown()=0。 GetHead(void)=0。 QPop(void)=0。elem)=0。 virtual TElemamp。 char IsEmpty() {return (len=0)? 1:0。 public: long GetLen(void) {return len。下面是描述隊(duì)列的抽象模型的類 TQueue0，它規(guī)定了通用操作接口（基本操作），是各種存儲結(jié)構(gòu)的隊(duì)列的基礎(chǔ)。抽象模型主要通過基本操作定義。在計(jì)算機(jī)算法實(shí)現(xiàn)中，也經(jīng)常使用隊(duì)列記錄需按 FIFO方式處理的數(shù)據(jù)。 隊(duì)是一種先進(jìn)先出 FIFO（ First In First Out）的結(jié)構(gòu)，元素出隊(duì)的次序與進(jìn)隊(duì)次序相同。插入與刪除操作分別稱為入隊(duì)與出隊(duì)。 隊(duì)列的邏輯結(jié)構(gòu) (一 ) 基本概念 隊(duì)列 (Queue)，簡稱為隊(duì)，是一種限定僅分別在表的兩端進(jìn)行插入與刪除的線性表。 棧 1 棧 2 圖 40 兩棧共享存貯空間 167。 (三 ) 兩棧共享存貯空間 對于兩棧共享存貯空間，可以特殊處理，以避免移動元素。 8) [兩邊移 ] 根據(jù)均衡原則，分頭向左右兩移動若干元素（總量為 m個(gè)）。 7) [右移 ] 將序號為 stop[r] ~ stop[i]+1的數(shù)組元素依次向右移 m位置，并修改相應(yīng)的棧頂與棧底指針。 5)[確定移動方向 ] 若 rm與 lm均為 0，則應(yīng)兩邊移，轉(zhuǎn) 8；若 lm=0，或 lm=0但 lmrm，則表明應(yīng)向右移，轉(zhuǎn) 7，（否 則應(yīng)向左移，下滑到 6）。 4)[確定移量量 ] 若 rs=m（ r存在），計(jì)算在 i棧右方讓出空位 的元素移動量 rm=stop[r] – stop[i]否則 (r不存在 )令 rm=0。 2) [向左搜索空閑區(qū) ] 對 l=i1, i2, …, 0 ，計(jì)算各棧的空閑空間，并累計(jì)到 ls 中，一旦 ls=m，則停止搜索，并記下當(dāng)前 l值。 這里，用 n表示 numStacks. 為了使讀者了解另外一種算法描述 方法，這里采用自然語言流程描述法。 } 4．棧移動 相比這下，棧移動過程 MoveStack(s, i, m)較復(fù)雜，它的功能是為 i號棧騰出 m個(gè)空位。 s→top[i] 。 //進(jìn)棧 } 3．出棧 設(shè) s為 TSstacks的一個(gè)實(shí)例的指針，將 i號棧頂?shù)脑貜棾龇祷氐倪^程為 Pop(i) { if (stop[i]==sbot[i]) 觸發(fā)?？债惓?。 //i號棧滿 ,調(diào)用MoveStacks為 I號棧讓出 1個(gè)位置 if (ret 0) 觸發(fā)異常； //棧真滿，無空閑空間可利用 } stop[i]++。 sbot[numStacks]=totSize。 inumStacks。 ??????n um S tac k sto tSi z e??????n um S t ac k st o t Si z e 棧 1 棧 2 … … 棧 n top[0] bot[0] top[1] bot[1] top[2] bot[2] top[n1] bot[n1] 圖 40 n棧共享存貯空間初始空間分配 top[n] bot[n] （二）算法考慮 下面用偽碼給出 n棧共享空間的主要算法。 初始時(shí)，令它們各占有 個(gè)元素的空間（最后一個(gè)棧要多占有一些）， 即令 top[i]=bot[i]= * i 這里， i=0, 1, … , numStacks1。 //下面是其他成員函數(shù)，此略 }。 //棧底指針數(shù)組 public: TStacks(long mNumStacks, long mTotSize)。 // 總?？臻g尺寸 TElem *room。 template class TElem //設(shè)棧元素類型為可變類型Telem class Tstacks { long numStacks。然而，由于各個(gè)棧在獨(dú)立工作，它們的進(jìn)棧出棧操作是隨機(jī)的，所以某次 MoverStack的移動量最小并不能保證總的平均移動量最小。它的設(shè)計(jì)目標(biāo)應(yīng)能使系統(tǒng)運(yùn)行期間內(nèi)的總的平均元素移動量最小。若系統(tǒng)中使用 n個(gè)棧，每個(gè)棧的最大尺寸為 ni(i=1,2, …, n) ，則 n個(gè)棧要預(yù)分配的總存貯容量為 如果已知這 n個(gè)棧 在任何時(shí)刻的總的存貯 ??niin1 占用量均不會超過 N，且有 N 則可考慮令 這 n個(gè)棧共享一塊大小為 N的存貯區(qū)，以節(jié)省存貯空間(圖 40) 棧 1 棧 2 … … 棧 n 棧 1底 棧 2底 棧 3底 棧 n底 圖 4 0n棧共享存貯空間 ??niin1 在這種情況下，除第一個(gè)棧外，其它棧的棧底位置均不固定，當(dāng)某棧溢出時(shí)（即棧頂與下一個(gè)棧的棧底重疊時(shí)），應(yīng)該移動若干個(gè)棧，為該棧讓出一些空間，這個(gè)過程稱為棧移動過程 MoveStack。 } ? 注意，“ delete p‖并不自動將 p置為空，所以，若在上面的程序中， 沒有“ top=NULL‖，則如果再次所用對應(yīng)的對象，會發(fā)生錯誤！ 167。 //釋放原 p所指結(jié)點(diǎn) } top = NULL。 p=pnext。 p=top。 template class TElem const TLinkNodeTElem*TStackLink TElem::GetTopNode(void) { return top。 return pNode。 top = topnext。 elemBuff = topinfo。 template class TElemTLinkNodeTElem*TStackLink TElem::PopNode(void) { TLinkNodeTElem *pNode。 return pNode。 top = pNode。 } 5．結(jié)點(diǎn)進(jìn) PushNode(TLinkNodeTelem *pNode)： 將 pNode所指結(jié)點(diǎn)壓入棧頂， 返回該結(jié)點(diǎn)的地址。 template class TElem TElemamp。 return elemBuff。 pNode = PopNode()。 template class TElem TElemamp。 //調(diào)用成員函數(shù)將新結(jié)點(diǎn)壓入棧 return pNodeinfo。 pNodeinfo = elem 。 pNode = new(nothrow) TLinkNodeTElem。TStackLinkTelem::Push(TElem amp。elem)： 先生成一個(gè)鏈結(jié)點(diǎn)， 將 elem值賦予其 info，然后調(diào)用 PushNode將 該結(jié)點(diǎn)壓入棧，返回棧頂元素的內(nèi)容的引用。 } template class TElemTStackLink TElem::~TStackLink() { Clear()。析構(gòu)函數(shù)的任務(wù)是 釋放所有結(jié) 點(diǎn)（通過調(diào) Clear()） . template class TElemTStackLink TElem::TStackLink() { top = NULL。 ? 至于成員函數(shù)的說明，在下面給出。 ? 它的幾個(gè)重要的數(shù)據(jù)成員為： top棧頂指針，指向棧中第一個(gè)元素結(jié)點(diǎn)。除了包 含了 TStack0的全部成員外，還增加了一套針對鏈 指針的操作。 ? TStackLink類從數(shù)據(jù)結(jié)構(gòu)的角度看，相當(dāng)于圖 示的棧頭結(jié)點(diǎn)。 virtual void Print()。 virtual TLinkNodeTElem* PopNode(void)。 virtual void Clear()。 virtual TElemamp。 virtual TElemamp。 virtual TElemamp。 virtual TElemamp。 Push(TElem amp。 ~TStackLink()。 //棧頂結(jié)點(diǎn)指針 TElem elemBuff。 //鏈指針 }。在定義該類前，需 定義鏈表中結(jié)點(diǎn)的類型 TLinkNode： template class TElem struct TLinkNode { TElem info。圖 40是鏈?zhǔn)綏５氖疽?。另外可設(shè)一個(gè)存貯當(dāng)前棧中元素個(gè)數(shù)的量。 ? 與線性鏈表類似，鏈?zhǔn)綏Ｒ残枰粋€(gè)描述結(jié)點(diǎn)，它作為整個(gè)棧的代表。 ? 我們這里仍然采用單鏈表存儲棧元素。對于棧，由于插入與刪除只在棧頂進(jìn)行，故不存在第一個(gè)問題。 棧的鏈?zhǔn)? 存貯結(jié)構(gòu) (一 ) 存儲方法 與線性表類似，棧也可采用鏈?zhǔn)酱尜A結(jié)構(gòu)。 }。 //令 room存儲新空間的地址 size=newSize。 //調(diào)用 CopyRoom將原空間 的內(nèi)容復(fù)制到新空間 if (room!=NULL) delete room。 //申請一塊新空間 if (pE==NULL) throw TExcepComm(2)。 TElem *pE。 }。 i++) objRoom[i] = srcRoom[i]。 //源數(shù)據(jù)個(gè)數(shù) (n2)大于目標(biāo)空間 (n1)時(shí)，只復(fù)制 n1個(gè) for (i=0。 k=n2。 return room[len1]。 i++)