【正文】 則返回 1；否則返回 0。 x=sqdata[(sqfront+1 )%QueueSize]。 int GetHead(SqQueue *sq,ElemType amp。 return 1。 sqfront=(sqfront+1)%QueueSize。 int DeQueue(SqQueue *sq,ElemType amp。 return 1。 sqrear=(sqrear+1)%QueueSize。 對應(yīng)算法如下 : int EnQueue(SqQueue *amp。 sqfront=sqrear=0。 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。 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ì)。此時(shí)，因隊(duì)頭指針指示實(shí)際隊(duì)頭的前一個(gè)位置所以在隊(duì)列滿時(shí)實(shí)際空了一個(gè)元素位置。 在隊(duì)尾插入新元素和刪除隊(duì)頭元素時(shí) ,指針都按逆時(shí)針方向進(jìn) 1。 ? 為了能夠充分地使用數(shù)組中的存儲空間 ,把數(shù)組的前端和后端連接起來 ,形成一個(gè)環(huán)形的順序表 ,即把存儲隊(duì)列元素的表從邏輯上看成一個(gè)環(huán) ,稱為 環(huán)形隊(duì)列 。 ? 那么能不能用 rear==QueueSize1作為隊(duì)滿的條件呢 ？ 顯然不能 ,在圖 (d)中 ,隊(duì)列為空 ,但仍滿足該條件 。 隊(duì)頭指針 front和隊(duì)尾指針 rear定義為整型變量 ， 實(shí)際取值范圍是 0~QueueSize1。 40 順序隊(duì)列的類型定義如下 : const int QueueSize=20。 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ì)列的順序存儲結(jié)構(gòu) ? 隊(duì)列的順序存儲結(jié)構(gòu)簡稱為順序隊(duì)，它由一個(gè)一維數(shù)組（用于存儲隊(duì)列中元素）及兩個(gè)分別指示隊(duì)頭和隊(duì)尾的變量組成， ? 這兩個(gè)變量分別稱為“隊(duì)頭指針”和“隊(duì)尾指針”（注意它們并非指針變量，而是數(shù)組的下標(biāo)）。排隊(duì)的規(guī)則是不允許“插隊(duì)”，新加入的成員只能排在隊(duì)尾，而且隊(duì)中全體成員只能按順序向前移動，當(dāng)?shù)竭_(dá)隊(duì)頭（并得到服務(wù)）后離隊(duì)。允許插入的一端稱為 隊(duì)尾 ，允許刪除的一端稱為 隊(duì)頭 。 //其他值無效退出 } return (lsnext==NULL)。 else if(A[i]==?O?) //出棧 Pop(ls,x)。in。 InitStack(ls)。 ElemType x。 ②本例用一個(gè)鏈棧來判斷操作序列是否合法，其中 A為存放操作序列的字符數(shù)組， n為該數(shù)組的元素個(gè)數(shù)（這里的 ElemType類型設(shè)定為 char。因?yàn)樵?B中，先進(jìn)棧一次，立即出棧 2次，這會造成棧下溢。若合法返回 1；否則返回 0。 } 32 例 假設(shè)以 I和 O分別表示進(jìn)棧和出棧操作，棧的初態(tài)和終態(tài)均為空，進(jìn)棧和出棧的操作序列可表示為僅由 I和 O組成的序列。 int StackEmpty(LinkStack *ls) { if (ls==NULL) return 1。 return 1。x) { if (ls==NULL) //棧空 ， 下溢出 return 0。 } } 30 (4)取棧頂元素運(yùn)算算法 其主要操作是：若棧為空 （ 即 lsnext所指結(jié)點(diǎn) ） 的data域值賦給 x。 free(p)。 x=pdata。 if (ls==NULL) //棧空 ， 下溢出 return 0。ls,ElemType amp。 } 29 (3)出棧運(yùn)算算法 其主要操作是：將棧頂結(jié)點(diǎn) （ 即 lsnext所指結(jié)點(diǎn) ） 的 data域值賦給 x， 然后刪除該棧頂結(jié)點(diǎn) 。 pnext=ls。 p=(LinkStack *)malloc(sizeof(LinkStack))。 void Push(LinkStack *amp。ls) { ls=NULL。 27 在 鏈棧中 ,棧的基本運(yùn)算算法如下 : (1)初始化棧運(yùn)算算法 其主要操作是：創(chuàng)建一個(gè)頭結(jié)點(diǎn) *ls, 用 ls=NULL標(biāo)識棧為空棧 。 //存儲結(jié)點(diǎn)數(shù)據(jù) struct stnode *next。 因鏈棧本身沒有容量限制，故在用戶內(nèi)存空間的范圍內(nèi)不會出現(xiàn)棧滿情況。棧中的其他結(jié)點(diǎn)通過它們的 next域鏈接起來。其中，單鏈表的第一個(gè)節(jié)點(diǎn)就是鏈棧棧頂結(jié)點(diǎn)， ls稱為棧頂指針 。 } 24 棧的鏈?zhǔn)酱鎯Y(jié)構(gòu) 棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)是以某種形式的鏈表作為棧的存儲結(jié)構(gòu)，棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)簡稱為鏈棧，其組織形式與單鏈表類似。 if (match(exp)==1) printf(表達(dá)式 %s括號配對 \n,exp)。 else return 0。amp。 } 23 i++。 else nomatch=1。 break。 case ?]?: if(st[top]=?[?) top。 else nomatch=1。break。 case ?{?: st[top]=exps[i]。top++。break。 nomatch==0) 22 { switch(exps[i]) { case ?(?: st[top]=exps[i]。 while (exps[i]!=?\0?amp。 int match(char *exps) { char st[Max],top=1,i=0。若 top==0，則返回 1。 解 :設(shè)置一個(gè)棧 st,用 i掃描表達(dá)式 exps：遇到 (、[和 {時(shí)，將其進(jìn)棧 ,遇到）、 ]和 }時(shí) ,判斷棧頂是否是匹配的括號。 } 21 例 設(shè)計(jì)一個(gè)算法 ， 判斷一個(gè)表達(dá)式中符號“ （ ” 與 “ ） ” 、 “ [”與 “ ]”、 “ {”與 “ }”是否匹配 。 int StackEmpty(SqStack st) { if (==1) return 1。 r