【文章內(nèi)容簡(jiǎn)介】 例 假設(shè)以 I和 O分別表示進(jìn)棧和出棧操作，棧的初態(tài)和終態(tài)均為空，進(jìn)棧和出棧的操作序列可表示為僅由 I和 O組成的序列。 ①下面所示的序列中哪些是合法的？ ② 通過(guò)對(duì) ①的分析，寫出一個(gè)算法判定所給的操作序列是否合法。若合法返回 1；否則返回 0。（假設(shè)被判定的操作序列已存入一維數(shù)組中） 33 解： ① A、 D均合法，而 B、 C不合法。因?yàn)樵?B中，先進(jìn)棧一次，立即出棧 2次，這會(huì)造成棧下溢。在 C中共進(jìn)棧 5次，出棧 3次，棧的終態(tài)不為空。 ②本例用一個(gè)鏈棧來(lái)判斷操作序列是否合法，其中 A為存放操作序列的字符數(shù)組， n為該數(shù)組的元素個(gè)數(shù)（這里的 ElemType類型設(shè)定為 char。） 34 int Judge(char A[ ],int n) { int i。 ElemType x。 LinkStack *ls。 InitStack(ls)。 for (i=0。in。i++) { if (A[i]==?I?) //進(jìn)棧 Push(ls,A[i])。 else if(A[i]==?O?) //出棧 Pop(ls,x)。 else return 0。 //其他值無(wú)效退出 } return (lsnext==NULL)。 //棧為空時(shí)返回 1，否則返回 0 } 35 隊(duì)列 隊(duì)列的基本概念 返回 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu) 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 36 隊(duì)列也是一種運(yùn)算受限的線性表 ,在這種線性表上，插入限定在表的某一端進(jìn)行，刪除限定在表的另一端進(jìn)行。允許插入的一端稱為 隊(duì)尾 ，允許刪除的一端稱為 隊(duì)頭 。 隊(duì)列的基本概念 a1 a2 a3 … an 出隊(duì)列 入隊(duì)列 隊(duì)頭 隊(duì)尾 37 隊(duì)列與現(xiàn)實(shí)生活中人們?yōu)榈玫侥撤N服務(wù)（如購(gòu)物、購(gòu)票等）而排隊(duì)十分相似。排隊(duì)的規(guī)則是不允許“插隊(duì)”，新加入的成員只能排在隊(duì)尾，而且隊(duì)中全體成員只能按順序向前移動(dòng)，當(dāng)?shù)竭_(dá)隊(duì)頭（并得到服務(wù)）后離隊(duì)。隊(duì)列的特點(diǎn)是 先進(jìn)先出 ，因此，隊(duì)列又稱為先進(jìn)先出線性表。 38 隊(duì)列以線性表為邏輯結(jié)構(gòu)，其基本運(yùn)算如下： ?① 初始化隊(duì)列 InitQueue(qu) ?② 入隊(duì)列 EnQueue(qu,x) ?③ 出隊(duì) DeQueue(qu,x) ?④ 取隊(duì)頭元素 GetHead(qu,x) ?⑤ 判斷隊(duì)列空 QueueEmptyq(qu) 39 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu) ? 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱為順序隊(duì)，它由一個(gè)一維數(shù)組（用于存儲(chǔ)隊(duì)列中元素）及兩個(gè)分別指示隊(duì)頭和隊(duì)尾的變量組成， ? 這兩個(gè)變量分別稱為“隊(duì)頭指針”和“隊(duì)尾指針”（注意它們并非指針變量，而是數(shù)組的下標(biāo)）。 ? 隊(duì)尾指針（ real） 指示隊(duì)尾元素在一維數(shù)組中的 當(dāng)前位置 ， ? 隊(duì)頭指針（ front） 指示隊(duì)頭元素在一維數(shù)組中的當(dāng)前位置的 前一個(gè)位置 。 40 順序隊(duì)列的類型定義如下 : const int QueueSize=20。 //隊(duì)列的容量 typedef struct sqqueue { ElemType data[QueueSize]； //保存隊(duì)中元素 int front, rear； //隊(duì)頭和隊(duì)尾指針 } SqQueue 其中 data為存儲(chǔ)隊(duì)列中元素的一維數(shù)組 。 隊(duì)頭指針 front和隊(duì)尾指針 rear定義為整型變量 ， 實(shí)際取值范圍是 0~QueueSize1。 41 隊(duì)列的入隊(duì)和出隊(duì)操作示意圖 4 3 2 1 0 front ,re ar (a) 空隊(duì) D C B A front rear ( b ) A,B,C,D 入隊(duì) 4 3 2 1 0 D C B front rear (c) 出隊(duì)一次 4 3 2 1 0 front rear (d) 出隊(duì) 4 次 4 3 2 1 0 42 ? 從前圖中看到 , 圖 (a) 為隊(duì)列的初始狀態(tài) , 有front==rear成立 ,該條件可以作為隊(duì)列空的條件 。 ? 那么能不能用 rear==QueueSize1作為隊(duì)滿的條件呢 ？ 顯然不能 ,在圖 (d)中 ,隊(duì)列為空 ,但仍滿足該條件 。這時(shí)入隊(duì)時(shí)出現(xiàn) “ 上溢出 ” ,這種溢出并不是真正的溢出 ,在 data數(shù)組中存在可以存放元素的空位置 ,所以這是一種假溢出 。 ? 為了能夠充分地使用數(shù)組中的存儲(chǔ)空間 ,把數(shù)組的前端和后端連接起來(lái) ,形成一個(gè)環(huán)形的順序表 ,即把存儲(chǔ)隊(duì)列元素的表從邏輯上看成一個(gè)環(huán) ,稱為 環(huán)形隊(duì)列 。 43 環(huán)形隊(duì)列首尾相連 ,當(dāng)隊(duì)首 front指針滿足 front==QueueSize1后 ,再前進(jìn)一個(gè)位置就自動(dòng)到 0,這可以利用除法取余的運(yùn)算 (MOD)來(lái)實(shí)現(xiàn) : 隊(duì)頭指針進(jìn) 1: front=(front+1) MOD QueueSize 隊(duì)尾指針進(jìn) 1: rear=(rear+1)MOD QueueSize 環(huán)形隊(duì)列的隊(duì)頭指針和隊(duì)尾指針初始化時(shí)都置0:front=rear=0。 在隊(duì)尾插入新元素和刪除隊(duì)頭元素時(shí) ,指針都按逆時(shí)針?lè)较蜻M(jìn) 1。 44 為了區(qū)別于隊(duì)列空條件，用 (rear+1)MOD QueueSize==front 來(lái)判斷是否隊(duì)已滿，也就是說(shuō)，讓 rear指到 front的前一位置就認(rèn)為隊(duì)列已滿。此時(shí)，因隊(duì)頭指針指示實(shí)際隊(duì)頭的前一個(gè)位置所以在隊(duì)列滿時(shí)實(shí)際空了一個(gè)元素位置。 如果不留這個(gè)空位置，讓隊(duì)尾指針 rear一直存到這個(gè)位置，必然有 rear==front，則隊(duì)列空條件和隊(duì)列滿條件就混淆了。 45 循環(huán)隊(duì)的入隊(duì)和出隊(duì)操作示意圖 rear 0 1 2 3 4 front (a) 空隊(duì) ( b ) A,B,C 入隊(duì) re ar 0 1 2 3 4 front A B C rear 0 1 2 3 4 A B C D front ( c )D 入隊(duì) , 隊(duì)滿 rear 0 1 2 3 4 C D front (d) 出隊(duì) 2 次 rear 0 1 2 3 4 front (e) 出隊(duì) 2 次 , 隊(duì)空 46 環(huán)形隊(duì)列 qu的 4要素： ? 隊(duì)空條件： = ? 隊(duì)滿條件： (+1)%QueueSize== ? 進(jìn)隊(duì)操作： 1；元素進(jìn)隊(duì)。 ? 出隊(duì)操作： 1；元素出隊(duì)。 47 在環(huán)形隊(duì)列中 ,實(shí)現(xiàn)隊(duì)列的基本運(yùn)算算法如下 : (1)初始化隊(duì)列運(yùn)算算法 其主要操作是：創(chuàng)建一個(gè)隊(duì)列結(jié)點(diǎn) ， 用 sq指向該隊(duì)列結(jié)點(diǎn) ， 并指定 sqfront=sqrear=0 void InitQueue(SqQueue *amp。sq) //qu為引用型參數(shù) { sq=(SqQueue *)malloc (sizeof(SqQueue))。 sqfront=sqrear=0。 //指針初始化 } 48 (2)入隊(duì)運(yùn)算算法 其主要操作是：先判斷隊(duì)列是否已滿 ， 若不滿 ，將隊(duì)尾指針增 1,在該位置存放 x。 對(duì)應(yīng)算法如下 : int EnQueue(SqQueue *amp。sq,ElemType x) { if ((sqrear+1)%QueueSize==sqfront) //隊(duì)滿 return 0。 sqrear=(sqr