【正文】 將元素 elem加入隊中，返回其在隊中值的引用。 u QPop()： 出隊。下溢（隊空）時觸發(fā)異常。 u RollDown()： 將隊中元素循環(huán)向下（隊尾底方向） 推一個位置，隊尾元素到達隊頭。 167。同樣用一維數(shù)組做為隊元素存貯空間。 room：指向元素存儲空間，作為一維數(shù)組使用。為了方便，令 front指向隊頭元素的前一個位置（空位）。這里令 rear指向隊尾元素位置。 這里，由于我們不循環(huán)使用隊空間，故將這種情況的隊列稱為非循環(huán)隊列。 a1 a2 a3 …… an 圖 4 0順序存貯結構的隊列 room: front: rear: 2．進隊 進隊是將元素添加到隊尾，故需訪問隊尾指針 rear. 將元素 x進隊 Q的操作為： if (隊滿 ) 觸發(fā)異常 ； Qrear++。 3．出隊 出隊是將當前隊中頭元素摘取并返回其： if (隊空 ) 觸發(fā)異常 ； Qfront++。 4．隊空 /滿問題 ? 對于這種操作方法，隊列變空時有下列關系成立 Qfront==Qrear 顯然初始狀態(tài)也滿足此式。 ? 分析上面的進隊與出隊算法，由于進隊時 rear增加，但出隊時 rear也不會減小，所以，當進過 N1個元素 (設N為隊空間大小 )后，不論此前是否出過隊， rear也會越界。事實上，如果前面已有元素出了隊，則還有空閑區(qū)可用，由于算法的限制，不能繼續(xù)執(zhí)行進隊操作了。 這種問題的根源是出隊操作所騰出的空位不能重復利用。所以，這種隊列無實用價值。但這種方法效率差； n 循環(huán)隊列法。 (二 ) 循環(huán)隊列 1．基本思想 所謂循環(huán)隊列，就是指將隊列的存貯區(qū)域視作循環(huán)結構，即將存貯區(qū)的第 1個元素視為最后一個元素的后繼，同樣將最后元素視為第 1個元素的前趨，隊列的頭尾指針的移動均可回繞，按這種方式處理的隊列，稱為循環(huán)隊列。 下面考慮循環(huán)隊列的實現(xiàn)。 根據(jù)模運算特點，將頭尾指針加 1后按 N取模即可實現(xiàn)尾指針的回繞。 為了處理方便，我們仍然假定： ? 隊頭指示器 front：指向隊中第 1個元素的前一個位置。 這樣的處理，隊中有一個元素的空間不被利用。 如果設置隊長度 len，隊滿和空的判別，可直接使用len， : 循環(huán)隊 的具體的存儲用類 TQueueSqu描述如下。 //隊空間首地址，當一維數(shù)組用 TElem elemBuff。 //隊空間的大小 long CopyRoom(TElem *objRoom, long n1, TElem * srcRoom, long n2)。 //這兩個函數(shù)與線 性表中相同 public: TQueueSqu()。 ~TQueueSqu()。 QPush(TElem amp。 virtual TElemamp。 virtual TElemamp。 virtual TElemamp。 virtual TElemamp。 virtual void Clear()。 }。注意，我們這里用隊長度判別隊空與滿。 front=0。 size=0。 } template class TElem TQueueSquTElem::TQueueSqu(long mSize) {//初始化，并分配隊空間 len=0。 rear=0。 //分配 mSize個 TElem型元素空間 if (room==NULL) throw TExcepComm(4)。 } template class TElem TElemamp。elem) {//將 elem進隊 ,并返回該元素在隊中的引用 if (len=size1) {//若隊空間不足，則重新分配 long ret=ResizeRoom(size+10)。 } rear++。 //rear加過尾后回繞，實現(xiàn) “ 循環(huán) ” room[rear]=elem。 return room[rear]。 TQueueSquTElem::QPop(void) {//出隊。 len。 if (front=size) front=0。 }。 TQueueSquTelem::GetHead(void) {//返回隊頭元素的引用 return room[(front+1) % size]。 隊列的鏈式存貯結構 (一 ) 存儲方法 與棧類似，若隊中元素個數(shù)變化范圍很大，則可采用鏈式結構（動態(tài)式）。 該鏈表的描述結點應至少含兩個指針：隊頭元素指針與隊尾元素指針，分別令其指向隊中首元素與尾元素對應的結點。 a2 an ^ front rear len a1 圖 40 鏈式隊列基本形式 隊結點 TStackLink 鏈結點 ,隊頭TLinkNode 隊尾結點 (二 ) 面向對象描述 設立一個類 TQueueLink，其從 TQueue0派生而來。至于TLinkNode，仍同前。 TLinkNode *next。 template class TElem class TQueueLink : public TQueue0TElem //隊類 { protected: TLinkNodeTElem *front, *rear。 public: TQueueLink()。 virtual TElemamp。elem)。 QPop(void)。 GetHead(void)。 RollDown()。 RollUp()。 //Newly added functions virtual TLinkNodeTElem*QPushNode (TLinkNodeTElem *pNode)。 virtual const TLinkNodeTElem* GetHeadNode (void)。 }。 template class TElem TQueueLinkTElem::TQueueLink() {//構造函數(shù)，實現(xiàn)初始化 front = NULL。 len = 0。 } template class TElem TElemamp。elem) {//進隊。 pNode = new(nothrow) TLinkNodeTElem。 pNodeinfo = elem 。 //調用 QPushNode, 將新生成的鏈結點推 入隊 return pNodeinfo。 TQueueLinkTElem::QPop(void) {//出隊。注意，在下次調用該函數(shù)前要將返回值復制。 pNode = QPopNode()。 //TElem must support ―=‖ delete pNode。 //返回隊頭元素值的引用 } template class TElem TElemamp。 return frontinfo。將 pNode所指結點進到隊尾 pNodenext = NULL。 //隊不空時，新結點插入到最后一個結點的后面 else front = pNode。 //令 rear指向新的隊尾 len++。 //返回隊頭結點 } template class TElem TLinkNodeTElem *TQueueLinkTElem::QPopNode(void) {//結點出隊。 if (front==NULL) throw TExcepComm(5)。 //TElem must support ―=‖ pNode = front。 //將隊頭元素摘下 if (front==NULL) rear=NULL。 return pNode。 } ? 在 QPushNode()中 ， 在新結點進隊前 ， 要特別注意隊是否為空 ！ 為空時相當于在空鏈中插入結點 ， 要特殊處理 ！ 類似地 ， 在 QPopNode()中 ， 出隊后要特別注意隊是否已變空 ， 若已變空 ， 則 rear指針要置為空 。 串 現(xiàn)實世界中的實體有多種形式，如數(shù)值、文字符號序列、圖形、圖象、聲音等。串在現(xiàn)實世界中是屢見不鮮的。在計算機中，串被認為是一種特殊線性表 ──元素為文字符號的線性表，由于現(xiàn)實問題中經(jīng)常使用串，所以對串應提供靈活多樣的基本操作，選擇合適的存貯結構。 串的邏 輯結構 (一 ) 基本概念 串 是由零個或多個字符構成的有限序列，一般記為 s = ―a1a2… an‖ (n≥ 0) 其中， s代表 串的名稱 ，用雙引號括起來的部分（不含該雙引號本身）為 串值 （即字符序列），每個 ai為一個字符。串值中字符個數(shù)（即 n）稱為 串長 ，長度為 0的串稱為 空串 。串中某字符在串中出現(xiàn)的序號為該字符在串中的 字符位置 ，子串中第 1個字符在串中的序號稱為該子串在該串中的 位置 。那么，串之間的大小關系是如何定義的呢？首先應定義單個字符間的大小關系。字符編碼可有多種，對英文字母和符號， ASCII碼是最常見的一種。例如，字符 A與 B的 ASCII碼分別為 65與 66（十進制），則說 39。39。 ? ASCII(American Standard code for Information Interchange)是美國信息交換標準編碼，長度為 8位二進制符號，所以最多能編 28=256個不同的字符。在字符和數(shù)字中，空格編碼最小， 其次是數(shù)字（按 09的次序）、大寫字母（按 AZ的次序）、小寫字母（按 az的次序）等。漢字的編碼也有幾種，如大陸用的國標碼 (GB2312)，臺灣地區(qū)用的 Big5等。 GB2312將漢字分為兩級編碼，分別稱一級字庫和二級字庫。 ? 要在一個系統(tǒng)中能混合所用多種文字，則需要一種統(tǒng)一的編碼系統(tǒng)，它將各種文字的基本字符在同一空間內編碼。 2．字符串間的大小關系 有了字符大小的定義，就可以考慮串的小關 系了。 下面給出幾個例子說明此定義。下面介紹幾種常見的。 n (long idx)： 返回 s中序號為 idx的字符。 n (s1, mode)： 串比較函數(shù)，比較 s與 s1之間的大小關系，若 ss1，返回負數(shù)；若 s==s1則返回 0；若 ss1則返回正數(shù)。 n 返回值為 s的長度。(s1, maxNum)： 連接函數(shù)。 maxNum 表示最多復制的字符數(shù)目，省缺時表示 “ 全部 ” n 設字符 ch可能在 s中出現(xiàn)若干次，則該函數(shù)返回 ch的第 sn次出現(xiàn)的位置（序號）。 mode為針對 ch的比較 /匹配模式。 n 返回子串s1在 s中第 sn次出現(xiàn)的出現(xiàn)位置（序號）。 ? 在 s中按 mode 方式，從 s中的第 sn起查找 s1的第 sn2個出現(xiàn)，返回出現(xiàn)位置。 mode同前。(sn, num)：求子串函數(shù)。 sn的含義同上。 num=0時表示從 sn起的 “ 全部 ” ，此時，若 sn0則 num相當于正 0(+0)（從左向右的全部），否則相當負 0（ 0）。 sn省缺值為 1. ? 在 s中，用 s2的值替 s1的從第 sn個出現(xiàn)起的 num個