數(shù)據(jù)結(jié)構(gòu)解說(shuō)演示課件

第3章 隊(duì)列,與棧一樣，隊(duì)列也是一種操作受限的線性表。隊(duì)列在操作系統(tǒng)和事務(wù)管理等軟件設(shè)計(jì)中應(yīng)用廣泛，如鍵盤(pán)輸入緩沖區(qū)問(wèn)題就是利用隊(duì)列的思想實(shí)現(xiàn)的。 本章重點(diǎn)和難點(diǎn)： 1、隊(duì)列的順序表示與實(shí)現(xiàn) 2、隊(duì)列的鏈?zhǔn)奖硎九c實(shí)現(xiàn),3.1 隊(duì)列的定義與抽象數(shù)據(jù)類型,隊(duì)列只允許在表的一端進(jìn)行插入操作，在表的另一端進(jìn)行刪除操作。3.1.1 什么是隊(duì)列 隊(duì)列（queue）是一種先進(jìn)先出（first in first out，縮寫(xiě)為FIFO）的線性表，它只允許在表的一端進(jìn)行插入，另一端刪除元素。這與我們?nèi)粘Ｉ钪械呐抨?duì)是一致的，最早進(jìn)入隊(duì)列的元素最早離開(kāi)。在隊(duì)列中，允許插入的一端稱為隊(duì)頭（front），允許刪除的一端稱為隊(duì)尾（rear）。因此又稱隊(duì)列為先進(jìn)先出（FIFO）表。,3.1 隊(duì)列的定義與抽象數(shù)據(jù)類型,假設(shè)隊(duì)列為q=（a1，a2，ai，an），那么a1為隊(duì)頭元素，an為隊(duì)尾元素。進(jìn)入隊(duì)列時(shí)，是按照a1，a2，an的順序進(jìn)入的，退出隊(duì)列時(shí)也是按照這個(gè)順序退出的。也就是說(shuō)，當(dāng)先進(jìn)入隊(duì)列的元素都退出之后，后進(jìn)入隊(duì)列的元素才能退出。即只有當(dāng)a1，a2，an-1都退出隊(duì)列以后，an才能退出隊(duì)列。,3.1 隊(duì)列的定義與抽象數(shù)據(jù)類型,2基本操作集合（1）置空隊(duì)列InitQueue(Q)：初始化操作，建立一個(gè)空隊(duì)列Q。（2）判隊(duì)列空QueueEmpty(Q)：若Q為空隊(duì)列，返回1，否則返回0。（3）入隊(duì)列EnQueue(Q,x)：若隊(duì)列不滿，插入元素x到隊(duì)列Q的隊(duì)尾。（4）出隊(duì)列DeQueue(Q)：若隊(duì)列不空，刪除隊(duì)頭元素，并返回該元素。（5）取隊(duì)頭Gethead(Q)：若隊(duì)列不空，返回隊(duì)頭元素。（,3.2 隊(duì)列的順序存儲(chǔ)及實(shí)現(xiàn),3.2.1 順序隊(duì)列的表示 順序隊(duì)列通常采用一維數(shù)組依次存放從隊(duì)頭到隊(duì)尾的元素。同時(shí)，使用兩個(gè)指針?lè)謩e指示數(shù)組中存放的第一個(gè)元素和最后一個(gè)元素的位置。其中，指向第一個(gè)元素的指針被稱為隊(duì)頭指針front，指向最后一個(gè)元素的指針被稱為隊(duì)尾指針rear。 元素a、b、c、d、e、f、g依次進(jìn)入隊(duì)列后的狀態(tài)如圖3.2所示。元素a存放在數(shù)組下標(biāo)為0的存儲(chǔ)單元中，g存放在下標(biāo)為6的存儲(chǔ)單元中，隊(duì)頭指針front指向第一個(gè)元素a，隊(duì)尾指針rear指向最后一個(gè)元素g的下一位置。,3.2 隊(duì)列的順序存儲(chǔ)及實(shí)現(xiàn),在使用隊(duì)列前，先初始化隊(duì)列，此時(shí)，隊(duì)列為空，隊(duì)頭指針front和隊(duì)尾指針rear都指向隊(duì)列的第一個(gè)位置，即front=rear=0，如圖3.3所示。 每一個(gè)元素進(jìn)入隊(duì)列，隊(duì)尾指針rear就會(huì)增1，若元素a、b、c依次進(jìn)入空隊(duì)列，front指向第一個(gè)元素，rear指向下標(biāo)為3的存儲(chǔ)單元，如圖3.4所示。,3.2 隊(duì)列的順序存儲(chǔ)及實(shí)現(xiàn),當(dāng)一個(gè)元素出隊(duì)列時(shí)，隊(duì)頭指針front增1，隊(duì)頭元素即a出隊(duì)后，front向后移動(dòng)一個(gè)位置，指向下一個(gè)位置，rear不變，如圖3.3所示。,3.2 隊(duì)列的順序存儲(chǔ)及實(shí)現(xiàn),3.2.2 順序隊(duì)列的“假溢出” 在對(duì)順序隊(duì)列進(jìn)行插入和刪除操作的過(guò)程中，可能會(huì)出現(xiàn)“假溢出”現(xiàn)象。經(jīng)過(guò)多次插入和刪除操作后，實(shí)際上隊(duì)列還有存儲(chǔ)空間，但是又無(wú)法向隊(duì)列中插入元素，我們將這種溢出稱為“假溢出”。 例如，在圖3.2所示的隊(duì)列中插入3個(gè)元素h、i、j，然后刪除2個(gè)元素a，b之后，就會(huì)出現(xiàn)如圖3.6所示的情況。當(dāng)插入元素j后，隊(duì)尾指針rear將越出數(shù)組的下界而造成“假溢出”。,3.2 隊(duì)列的順序存儲(chǔ)及實(shí)現(xiàn),3.2.3 順序循環(huán)隊(duì)列的表示 1順序循環(huán)隊(duì)列 為了充分利用存儲(chǔ)空間，消除這種“假溢出”現(xiàn)象，當(dāng)隊(duì)尾指針rear和隊(duì)頭指針front到達(dá)存儲(chǔ)空間的最大值（假定隊(duì)列的存儲(chǔ)空間為QueueSize）的時(shí)候，讓隊(duì)尾指針和隊(duì)頭指針轉(zhuǎn)化為0，這樣就可以將元素插入到隊(duì)列還沒(méi)有利用的存儲(chǔ)單元中。例如，在圖3.6中，插入元素j之后，rear將變?yōu)?，可以繼續(xù)將元素插入到下標(biāo)為0的存儲(chǔ)單元中。這樣就把順序隊(duì)列使用的存儲(chǔ)空間構(gòu)造成一個(gè)邏輯上首尾相連的循環(huán)隊(duì)列。,3.2 隊(duì)列的順序存儲(chǔ)及實(shí)現(xiàn),當(dāng)隊(duì)尾指針rear達(dá)到最大值QueueSize-1時(shí)，前提是隊(duì)列中還有存儲(chǔ)空間，若要插入元素，就要把隊(duì)尾指針rear變?yōu)?；當(dāng)隊(duì)頭指針front達(dá)到最大值QueueSize-1時(shí)，若要將隊(duì)頭元素出隊(duì)，要讓隊(duì)頭指針front變?yōu)?。這可通過(guò)取余操作實(shí)現(xiàn)隊(duì)列的首尾相連。例如，假設(shè)QueueSize=10，當(dāng)隊(duì)尾指針rear=9時(shí)，若要將新元素入隊(duì)，則先令rear=（rear+1）%10=0，然后將元素存入隊(duì)列的第0號(hào)單元，通過(guò)取余操作實(shí)現(xiàn)了隊(duì)列的邏輯上的首尾相連。,3.2 隊(duì)列的順序存儲(chǔ)及實(shí)現(xiàn),2順序循環(huán)隊(duì)列的隊(duì)空和隊(duì)滿判斷 但是，在順序循環(huán)隊(duì)列在隊(duì)空和隊(duì)滿的情況下，隊(duì)頭指針front和隊(duì)尾指針rear同時(shí)都會(huì)指向同一個(gè)位置，即front=rear，如圖3.7所示。即隊(duì)列為空時(shí)，有front=0，rear=0，因此front=rear。隊(duì)滿時(shí)也有front=0，rear=0，因此front=rear。,3.2 隊(duì)列的順序存儲(chǔ)及實(shí)現(xiàn),為了區(qū)分這隊(duì)空還是隊(duì)滿，通常有兩個(gè)方法：（1）增加一個(gè)標(biāo)志位。設(shè)這個(gè)標(biāo)志位為flag，初始時(shí)，有flag=0；當(dāng)入隊(duì)列成功，則flag=1；出隊(duì)列成功，有flag=0。則隊(duì)列為空的判斷條件為：front=rear&&flag=0，隊(duì)列滿的判斷條件為：front=rear&&flag=1。（2）少用一個(gè)存儲(chǔ)單元。隊(duì)空的判斷條件為front=rear，隊(duì)滿的判斷條件為front=(rear+1)%QueueSize。那么，入隊(duì)的操作語(yǔ)句為：rear=（rear+1）%QueueSize，Qrear=x。出隊(duì)的操作語(yǔ)句為：front=（front+1）%QueueSize。少用一個(gè)存儲(chǔ)單元的順序循環(huán)隊(duì)列隊(duì)滿情況如圖3.8所示。,3.2 隊(duì)列的順序存儲(chǔ)及實(shí)現(xiàn),順序循環(huán)隊(duì)列類型描述如下： #define QueueSize 100/*隊(duì)列的容量*/ typedef struct DataType dataQueueSize; int front,rear; /*隊(duì)頭指針和隊(duì)尾指針*/ CirQueue; 其中，data用來(lái)存儲(chǔ)隊(duì)列中的元素，front和rear分別表示隊(duì)頭指針和隊(duì)尾指針。,3.2 隊(duì)列的順序存儲(chǔ)及實(shí)現(xiàn),3.2.4 順序循環(huán)隊(duì)列的基本運(yùn)算 順序循環(huán)隊(duì)列的基本運(yùn)算算法實(shí)現(xiàn)如下。 （1）置空隊(duì)列。 void InitQueue(CirQueue *Q) /*順序循環(huán)隊(duì)列的初始化*/ Q ->front=Q ->rear=0; ,3.2 隊(duì)列的順序存儲(chǔ)及實(shí)現(xiàn),（2）判斷隊(duì)列是否為空int QueueEmpty(CirQueue *Q) return Q ->front = Q ->rear ;(3)判對(duì)滿int QueueFull(CirQueue *Q) return (Q ->rear+1)%QueueSize = Q ->front ;,3.2 隊(duì)列的順序存儲(chǔ)及實(shí)現(xiàn),（4）入隊(duì) int EnQueue(CirQueue *Q , DataType x) if(QueueFull(Q) printf(“Queue overflow”); else Q->dataQ->rear=x; Q->rear=(Q->rear+1)%QueueSize; ,3.2 隊(duì)列的順序存儲(chǔ)及實(shí)現(xiàn),（5）取隊(duì)頭元素 DataType GetFront (CirQueue *Q) if(QueueEmpty(Q) printf(“Queue empty”); exit(0); else return Q->dataQ->front; ,3.2 隊(duì)列的順序存儲(chǔ)及實(shí)現(xiàn),（6）出隊(duì)列DataType DeQueue(CirQueue *Q) DataType x; if(QueueEmpty(Q) printf(“Queue empty”); exit(0); else x=Q->dataQ->front; /*將要?jiǎng)h除的元素賦值給x*/ Q->front=(Q->front+1)%QueueSize; return x; ,3.2 隊(duì)列的順序存儲(chǔ)及實(shí)現(xiàn),3.2.3 順序循環(huán)隊(duì)列舉例 P77,3.3 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)及實(shí)現(xiàn),采用鏈?zhǔn)酱鎯?chǔ)的隊(duì)列被稱為鏈?zhǔn)疥?duì)列或鏈隊(duì)列。3.3.1 鏈?zhǔn)疥?duì)列的表示1鏈?zhǔn)疥?duì)列 鏈?zhǔn)疥?duì)列通常用鏈表實(shí)現(xiàn)。一個(gè)鏈隊(duì)列顯然需要兩個(gè)分別指示隊(duì)頭和隊(duì)尾的指針（分別稱為隊(duì)頭指針和隊(duì)尾指針）才能唯一確定。這里，與單鏈表一樣，為了操作上的方便，我們給鏈隊(duì)列添加一個(gè)頭結(jié)點(diǎn)，并令隊(duì)頭指針front指向頭結(jié)點(diǎn)，用隊(duì)尾指針rear指向最后一個(gè)結(jié)點(diǎn)。,3.3 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)及實(shí)現(xiàn),鏈?zhǔn)疥?duì)列的類型描述如下：/*結(jié)點(diǎn)類型定義*/typedef struct QNode DataType data; struct QNode * next; QueueNode;/*隊(duì)列類型定義*/typedef struct QueueNode * front; /隊(duì)頭指針 QueueNode * rear; /隊(duì)尾指針LinkQueue; /隊(duì)列類型LinkQueue Q; /定義一鏈對(duì)列Q,3.3 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)及實(shí)現(xiàn),一個(gè)不帶頭結(jié)點(diǎn)的鏈?zhǔn)疥?duì)列和帶頭結(jié)點(diǎn)的鏈隊(duì)列分別如圖3.12、圖3.13所示。,3.3 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)及實(shí)現(xiàn),對(duì)于帶頭結(jié)點(diǎn)的鏈?zhǔn)疥?duì)列，當(dāng)隊(duì)列為空時(shí)，隊(duì)頭指針front和隊(duì)尾指針rear都指向頭結(jié)點(diǎn)。如圖3.14所示。 鏈?zhǔn)疥?duì)列中，插入和刪除操作只需要移動(dòng)隊(duì)頭指針和隊(duì)尾指針，這兩種操作的指針變化如圖3.13、圖3.16和圖3.17所示。圖3.13表示在隊(duì)列中插入元素a的情況，圖3.16表示隊(duì)列中插入了元素a，b，c之后的情況，圖3.17表示元素a出隊(duì)列的情況。,3.3 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)及實(shí)現(xiàn),3.3.2 鏈?zhǔn)疥?duì)列的基本運(yùn)算鏈?zhǔn)疥?duì)列的基本運(yùn)算算法實(shí)現(xiàn)如下。（1）初始化隊(duì)列。void InitQueue(LinkQueue *Q) /*初始化鏈?zhǔn)疥?duì)列*/ Q->front=(QueueNode*)malloc(sizeof(QueueNode); Q->rear =Q->front; Q ->rear->next=NULL;/*把頭結(jié)點(diǎn)的指針域置為null*/,3.3 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)及實(shí)現(xiàn),（2）判斷隊(duì)列是否為空。int QueueEmpty(LinkQueue *Q) return Q->rear=Q->front; /頭尾指針相等隊(duì)列為空,3.3 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)及實(shí)現(xiàn),（3）將元素x入隊(duì)。先為新結(jié)點(diǎn)申請(qǐng)一個(gè)空間，然后將x賦給數(shù)據(jù)域，并使原隊(duì)尾元素結(jié)點(diǎn)的指針域指向新結(jié)點(diǎn)，隊(duì)尾指針指向新結(jié)點(diǎn)，從而將結(jié)點(diǎn)加入隊(duì)列中。操作過(guò)程如圖3.20所示。,將元素x入隊(duì)的算法實(shí)現(xiàn)如下。void EnQueue(LinkQueue *Q, DataType x)/*將元素x插入到鏈?zhǔn)疥?duì)列尾部*/ QueueNode *p=(QueueNode*)malloc(sizeof(QueueNode); p->data=x; /將元素值賦值給結(jié)點(diǎn)的數(shù)據(jù)域 p->next=NULL; /將結(jié)點(diǎn)的指針域置為空 Q->rear->next=p;/將原來(lái)隊(duì)列的隊(duì)尾指針指向p Q->rear=p;/將隊(duì)尾指針指向p,3.3 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)及實(shí)現(xiàn),3.3 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)及實(shí)現(xiàn),（4）取隊(duì)頭元素。DataType GetFront (LinkQueue *Q) if(QueueEmpty(Q) printf(“Queue underflow”); exit(0); else return Q->front->next-data;,3.3 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)及實(shí)現(xiàn),（5）出隊(duì)列。DataType DeQueue(LinkQueue *Q) QueueNode *p; if(QueueEmpty(Q) /判斷鏈?zhǔn)疥?duì)列是否為空 return 0; else p=Q->front;/使指針p指向頭結(jié)點(diǎn) Q->front=Q->front->next; /頭指針指向原隊(duì)列頭結(jié)點(diǎn) free(p); /釋放原頭結(jié)點(diǎn) return(Q->front->data); /返回原對(duì)頭結(jié)點(diǎn)的數(shù)據(jù) ,3.3 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)及實(shí)現(xiàn),3.3 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)及實(shí)現(xiàn),2鏈?zhǔn)窖h(huán)隊(duì)列 將鏈?zhǔn)疥?duì)列的首尾相連就構(gòu)成了鏈?zhǔn)窖h(huán)隊(duì)列。在鏈?zhǔn)窖h(huán)隊(duì)列中，可以只設(shè)置隊(duì)尾指針，如圖3.18所示。當(dāng)隊(duì)列為空時(shí)，如圖3.19所示，隊(duì)列LQ為空的判斷條件為L(zhǎng)Q.rear->next=LQ.rear。,3.3.3 鏈?zhǔn)疥?duì)列舉例 【例3_7】P81,3.3 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)及實(shí)現(xiàn),入隊(duì)列圖,出隊(duì)列圖,隊(duì)列是只允許在表的一端進(jìn)行插入操作，在另一端進(jìn)行刪除操作的線性表。 隊(duì)列有兩種存儲(chǔ)方式：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。采用順序存儲(chǔ)結(jié)構(gòu)的 隊(duì)列稱為順序隊(duì)列，采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的隊(duì)列稱為鏈?zhǔn)疥?duì)列。 順序隊(duì)列存在“假溢出”的問(wèn)題，順序隊(duì)列的“假溢出”不是因?yàn)榇鎯?chǔ)空間不足而產(chǎn)生的，為了避免“假溢出”，可用循環(huán)隊(duì)列表示順序隊(duì)列。 為了區(qū)分循環(huán)隊(duì)列的隊(duì)空還是隊(duì)滿，有3種方案：設(shè)置一個(gè)標(biāo)志位，少用一個(gè)存儲(chǔ)單元，設(shè)置一個(gè)計(jì)數(shù)器。 循環(huán)隊(duì)列P75，例題P80,3.4 小結(jié),1棧 1>棧的定義： 棧是限定僅在表的一端進(jìn)行插入和刪除操作的線性表。 我們把插入和刪除的一端稱為棧頂（TOP），另一端稱為棧底（BOTTOM）,不包含任何元素的棧稱為空棧。棧又稱為后進(jìn)先出（Last in first out）的線性表，簡(jiǎn)稱LIFO結(jié)構(gòu)。 2>棧的存儲(chǔ)結(jié)構(gòu) 由于棧也是線性表，因此線性表的存儲(chǔ)結(jié)構(gòu)對(duì)棧也使用，通常有順序棧和鏈棧兩種存儲(chǔ)結(jié)構(gòu)，這兩種存儲(chǔ)結(jié)構(gòu)的不同，即使得實(shí)現(xiàn)棧的基本運(yùn)算的算法也有所不同。 （1）順序存儲(chǔ)結(jié)構(gòu) 其實(shí)棧的順序存儲(chǔ)還是挺方便的，因?yàn)樗粶?zhǔn)棧頂進(jìn)出元素，所以不存在線性表插入和刪除時(shí)需要移動(dòng)元素的問(wèn)題。不過(guò)它有一個(gè)很大,3.4 小結(jié),的缺陷，就是必須事先確定數(shù)組存儲(chǔ)空間大小，不夠用了，就需要編程手段來(lái)擴(kuò)展數(shù)組的容量，非常麻煩， （2）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 如果棧的使用過(guò)程中元素變化不可預(yù)測(cè)，有時(shí)很小，有時(shí)非常大，那么最好是用鏈?！敬鎯?chǔ)空間不固定可伸縮】。2 隊(duì)列 1>隊(duì)列的定義 隊(duì)列(queue)是只允許在一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作的線性表。 隊(duì)列是一種先進(jìn)先出(first in first out)的線性表，簡(jiǎn)稱FIFO。允許插入的一端稱為隊(duì)尾（rear），允許刪除的一端稱為隊(duì)頭(Front)。 隊(duì)列是一種運(yùn)算受限的線性表，它的運(yùn)算限制與棧不同，是兩頭都有,3.4 小結(jié),限制，插入只能在表的一端進(jìn)行(只進(jìn)不出)，而刪除只能在表的另一端進(jìn)行(只出不進(jìn))。 2>隊(duì)列的存儲(chǔ)結(jié)構(gòu) 隊(duì)列也是線性表，所以有兩種存儲(chǔ)方式，順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。 （1）順序存儲(chǔ)結(jié)構(gòu)（順序隊(duì)列） 缺點(diǎn)，存儲(chǔ)空間不夠用的時(shí)候需要開(kāi)發(fā)人員通過(guò)編程手段來(lái)擴(kuò)展數(shù)組容量。 衍生循環(huán)隊(duì)列：頭尾相接的順序存儲(chǔ)結(jié)構(gòu)成為循環(huán)隊(duì)列。 （2）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（鏈隊(duì)） 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，其實(shí)也就是線性表的單鏈表，只不過(guò)它只能尾進(jìn)頭出而已，我們把它簡(jiǎn)稱為鏈隊(duì)列。,3.4 小結(jié),總結(jié)： 棧（stack）是限定在表的一端進(jìn)行插入和刪除操作的線性表。 隊(duì)列（queue）是只允許在一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作的線性表。它們均可使用線性表的順序存儲(chǔ)結(jié)構(gòu)來(lái)實(shí)現(xiàn)，但都存在著順序存儲(chǔ)的一些弊端（空間不夠用）。因此它們各自有各級(jí)的技巧來(lái)解決這個(gè)問(wèn)題， 對(duì)于棧來(lái)說(shuō)，如果是兩個(gè)相同數(shù)據(jù)類型的棧，則可以用數(shù)組的兩端作為棧底的方法來(lái)讓兩個(gè)棧共享數(shù)據(jù)，這就可以最大化地利用數(shù)組的空間。 對(duì)于隊(duì)列來(lái)說(shuō)，為了避免數(shù)組插入和刪除時(shí)需要移動(dòng)數(shù)據(jù)，于是就引入了循環(huán)隊(duì)列，使得隊(duì)頭和隊(duì)尾可以在數(shù)組中循環(huán)變化。解決了移動(dòng)數(shù)據(jù)的時(shí)間損耗。 他們也都可以通過(guò)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)來(lái)實(shí)現(xiàn)，實(shí)現(xiàn)原則上與線性表基本相同。,3.4 小結(jié),例如，一個(gè)算術(shù)表達(dá)式為 9 - (2+4*7)/5+3# 這種算術(shù)表達(dá)式中的運(yùn)算符總是出現(xiàn)在兩個(gè)操作數(shù)之間，這種算術(shù)表達(dá)式被稱為中綴表達(dá)式。計(jì)算機(jī)編譯系統(tǒng)在計(jì)算一個(gè)算術(shù)表達(dá)式之前，要將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，然后對(duì)后綴表達(dá)式進(jìn)行計(jì)算。后綴表達(dá)式就是算術(shù)運(yùn)算符出現(xiàn)在操作數(shù)之后，并且不含括號(hào)。 計(jì)算機(jī)在求算術(shù)表達(dá)式的值時(shí)分為兩個(gè)步驟： （1）將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式； （2）依據(jù)后綴表達(dá)式計(jì)算表達(dá)式的值。,3.5 棧和隊(duì)列的典型應(yīng)用,1將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式 要將一個(gè)算術(shù)表達(dá)式的中綴形式轉(zhuǎn)化為相應(yīng)的后綴形式，首先了解下算術(shù)四則運(yùn)算的規(guī)則。算術(shù)四則運(yùn)算的規(guī)則是： （1）先乘除，后加減； （3）同級(jí)別的運(yùn)算從左到右進(jìn)行計(jì)算； （2）先括號(hào)內(nèi)，后括號(hào)外。 上面的算術(shù)表達(dá)式轉(zhuǎn)換為后綴表達(dá)式為： 9247 *+5/-3 +,3.5 棧和隊(duì)列的典型應(yīng)用,轉(zhuǎn)換后的后綴表達(dá)式具有以下兩個(gè)特點(diǎn)： （1）后綴表達(dá)式與中綴表達(dá)式的操作數(shù)出現(xiàn)順序相同，只是運(yùn)算符先后順序改變了； （2）后綴表達(dá)式不出現(xiàn)括號(hào)。 正因?yàn)楹缶Y表達(dá)式的以上特點(diǎn)，所以編譯系統(tǒng)不必考慮運(yùn)算符的優(yōu)先關(guān)系。僅需要從左到右依次掃描后綴表達(dá)式的各個(gè)字符，遇到運(yùn)算符時(shí)，直接對(duì)運(yùn)算符前面的兩個(gè)操作數(shù)進(jìn)行運(yùn)算即可。,3.5 棧和隊(duì)列的典型應(yīng)用,如何將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式呢？ 我們約定#作為后綴表達(dá)式的結(jié)束標(biāo)志。則中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的算法描述如下： （1）初始化棧，并將#入棧； （2）當(dāng)讀到數(shù)字時(shí)，直接將其入隊(duì)列 ，并讀入下一字符； （3）當(dāng)讀到運(yùn)算符時(shí)，將棧中所有優(yōu)先級(jí)高于或等于該運(yùn)算符的運(yùn)算符彈出，并入隊(duì)列，再將當(dāng)前運(yùn)算符入棧； （4）當(dāng)讀入左括號(hào)時(shí)，即入棧； （5）當(dāng)讀入右括號(hào)時(shí)，將靠近棧頂?shù)牡谝粋€(gè)左括號(hào)上面的運(yùn)算符全部依次彈出， 送至隊(duì)列中，在刪除棧中的左括號(hào)。,3.5 棧和隊(duì)列的典型應(yīng)用,運(yùn)算符的優(yōu)先關(guān)系如表3.1所示。 表3.1 運(yùn)算符的優(yōu)先關(guān)系,3.5 棧和隊(duì)列的典型應(yīng)用,初始化一個(gè)空棧，用來(lái)對(duì)運(yùn)算符進(jìn)行出棧和入棧操作。中綴表達(dá)式9 - (2+4*7)/5+3#轉(zhuǎn)換為后綴表達(dá)式的具體過(guò)程如圖P84所示（為了便于描述，在要轉(zhuǎn)換表達(dá)式的末尾加一個(gè)#作為結(jié)束標(biāo)記）。,3.5 棧和隊(duì)列的典型應(yīng)用,2求后綴表達(dá)式的值 將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式后，就可以計(jì)算利用后綴表達(dá)式的值了。計(jì)算后綴表達(dá)式的值的規(guī)則如下：依次讀入后綴表達(dá)式中的每個(gè)字符，如果是操作數(shù)，則將操作數(shù)進(jìn)入棧；如果是運(yùn)算符，則將處于棧頂?shù)膬蓚€(gè)操作數(shù)出棧，然后利用當(dāng)前運(yùn)算符進(jìn)行運(yùn)算，將運(yùn)行結(jié)果入棧，直到整個(gè)表達(dá)式處理完畢。 利用上述規(guī)則，后綴表達(dá)式的9247 *+5/-3 +的值的運(yùn)算過(guò)程如圖P85所示。,3.5 棧和隊(duì)列的典型應(yīng)用,