《數(shù)據(jù)結(jié)構(gòu)》-第三章 棧與隊列

第3章棧與隊列第3章棧與隊列學習目的要求:棧的基本概念和棧的基本運算。棧在計算機中的應用。隊列的基本概念和隊列的基本運算。隊列在計算機中的應用。3.1棧3.2隊列第3章棧與隊列3.1棧3.1.1棧的定義

棧（Stack）又稱堆棧，是一種特殊的線性表，它限定線性表中元素的插入和刪除操作只能在線性表的一端進行。允許插入和刪除的一端為變化的一端，稱為棧頂（top），棧頂?shù)牡谝粋€元素稱為棧頂元素，棧的另一端稱為棧底（bottom）。向一個棧插入新元素又稱為進棧或入棧，它是把該元素放到棧頂元素的上面，使之成為新的棧頂元素。從一個棧刪除一個元素又稱為出棧或退棧，它是把棧頂元素刪除掉，使其下面的相鄰元素成為新的棧頂元素。所以又把棧稱為后進先出表（LastInFirstOut），簡稱為LIFO表。3.1棧（1）InitStack()初始化操作，建立一個空棧S。（2）GetTop(&S，&x)取棧頂元素操作，若棧S不空，則取棧頂元素，用x返回棧頂元素。（3）Push(&S，x)進棧操作，在S棧的棧頂壓入一個元素x。（4）Pop(&S，&x)出棧操作，刪除已存在且非空的棧S的棧頂元素，用x返回棧頂元素。（5）Empty(&S)判斷一個棧是否為空，若S為空棧，返回一個真值。3.1棧棧常用的基本操作:3.1.2棧的順序存儲結(jié)構(gòu)及其運算棧的順序存儲結(jié)構(gòu)，簡稱順序棧，它是利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素。例如，用數(shù)組element存放棧中的數(shù)據(jù)元素，數(shù)組最大容量為MAXLEN，top為棧頂指針，element[top]為棧頂元素

。3.1棧進棧時，棧頂指針上移，top加1；出棧時，棧頂指針下移，top減1。

top=-1，棧為空。從空棧中再刪除一個元素，棧將溢出，稱為“下溢”。

top=0，棧中有一個元素。

top=MAXLEN-1，棧滿。向棧中再插入一個元素，棧也將溢出，稱為“上溢”。3.1棧3.1.2棧的順序存儲結(jié)構(gòu)及其運算對于順序棧，入棧時，必須首先判斷棧是否滿了，若棧滿，不能入棧；出棧時，必須判斷棧是否為空，若為空，不能出棧。3.1棧3.1.3棧的鏈式存儲結(jié)構(gòu)及其運算棧的鏈式存儲結(jié)構(gòu)簡稱為鏈棧，它是一種特殊的單鏈表，也是一種動態(tài)存儲結(jié)構(gòu)，不用預先分配存儲空間。3.1棧datanexttop^…棧底棧頂1.進棧首先要向系統(tǒng)申請一個結(jié)點的存儲空間;將新元素的值寫入新結(jié)點的數(shù)據(jù)域中；然后修改棧頂指針。3.1棧p->data=x;p->next=top;top=p;2.出棧先取出棧頂元素的值再修改棧頂指針釋放原棧頂結(jié)點。3.1棧p=top;x=top->data;top=top->next;free(p);練習對于下面的每一步畫出棧中元素及棧頂指針示意圖： （1）空棧 （2）元素a，b，c進棧 （3）元素d，e，f進棧 （4）刪除元素f和e

（5）元素g進棧3.1.4棧的應用舉例棧是計算機軟件中應用最廣泛的數(shù)據(jù)結(jié)構(gòu)之一。1.算術(shù)表達式的計算進行表達式運算時，必須設(shè)置兩個棧：一個棧用于存放運算符，一個棧用于存放操作數(shù)。在表達式運算過程中，編譯程序?qū)λ阈g(shù)表達式從左向右進行掃描，遇到操作數(shù)，就把操作數(shù)放入操作數(shù)棧，遇到運算符時，把該運算符與運算符棧的棧頂比較。如果該運算符優(yōu)先級高于棧頂運算符的優(yōu)先級，就把該運算符進棧，否則退棧。退棧后，在操作數(shù)棧中退出兩個元素，其中先退出的元素在運算符右邊，后退出的元素在運算符左邊，然后用運算符棧中退出的棧頂元素進行運算，運算結(jié)果存入操作數(shù)棧中。反復進行上述操作，直到掃描結(jié)束。3.1棧例3.1用棧求表達式6-8/4+3*5的值。3.1棧步驟操作數(shù)棧運算符棧說明開始@開始時操作數(shù)棧為空，運算符棧為@16@掃描到“6”，進入操作數(shù)棧26@-掃描到“-”，進入運算符棧368@-掃描到“8”，進入操作數(shù)棧468@-/掃描到“/”，進入運算符棧5684@-/掃描到“4”，進入操作數(shù)棧66@-掃描到“+”，“/”、“8”、“4”退棧762@-8/4=2進操作數(shù)棧掃描到“+”運算符優(yōu)先級低于棧頂運算符“/”，“/”退棧。操作數(shù)棧中退出兩個元素4和8，先退出的放在運算符右邊，后退的放在左邊步驟操作數(shù)棧運算符棧說明8@繼續(xù)，“-”、“6”、“2”退棧94@6-2=4進操作數(shù)棧104@+“+”進入運算符棧1143@+掃描到“3”，進入操作數(shù)棧1243@+*掃描到“*”，進入到運算符棧13435@+*掃描到“5”，進入操作數(shù)棧144@+掃描完，“*”、“3”、“5”退棧15415@+3*5=15進操作數(shù)棧16@“+”、“4”、“15”退棧1719@4+15=19進操作數(shù)棧1819兩個@相遇，置運算符棧為空，運算結(jié)束，表達式的值為19“+”運算符優(yōu)先級與運算符“-”相同，“/”退棧。求表達式6-8/4+3*5的值（續(xù)）操作數(shù)：直接輸出，用空格間隔開來。運算符：與棧頂運算符比較，運算級別高的進棧；相同或低的出棧。括號：遇到左括號，進棧；右括號，退棧，退到左括號為止。例3.2將中綴表達式2*(3+5)/(6–4)轉(zhuǎn)換成等價的后綴表達式。3.1棧2.中綴表達式轉(zhuǎn)換成等價的后綴表達式①②③后綴表達式：235+*64-/3.函數(shù)遞歸的實現(xiàn)函數(shù)直接或間接地調(diào)用自己的算法，叫做遞歸算法。3.1棧例3.3求n!1n=0n!=n*(n-1)!n>0遞歸函數(shù)的執(zhí)行過程如下:

（1）系統(tǒng)首先為遞歸調(diào)用建立一個工作棧，在該工作棧中存放參數(shù)、局部變量和調(diào)用后的返回地址等信息;

（2）在每次遞歸調(diào)用之前，把本次算法中所使用的參數(shù)、局部變量的當前值和調(diào)用后的返回地址等壓入棧頂;

（3）在每次執(zhí)行遞歸調(diào)用結(jié)束之后，又把棧頂元素彈出，分別賦給相應的參數(shù)和局部變量，以便使它們恢復到調(diào)用前的狀態(tài)，然后返回由返回地址所指定的位置;

（4）繼續(xù)執(zhí)行后續(xù)指令。例3.4求4!3.1棧3.1棧例3.5Hanoi塔問題4321ABC14ABC1322ABC132434321ABC4將A上的N－1個挪到B上將A上第N個挪到C上將B上的N－1個挪到C上3.2隊列3.2.1隊列的定義隊列（queue）也是一種特殊的線性表，它僅允許在表的一端進行插入，在表的另一端進行刪除。允許插入的一端稱為隊尾（rear），允許刪除的一端稱為隊首（front）。隊列又稱為先進先出表（FirstInFirstOut，簡稱FIFO）。隊列的基本操作可以歸納為以下幾種:

（1）InitQueue()

初始化一個空隊列Q；（2）GetFront(&Q，&y)

取隊列Q的隊頭元素，y返回其值，但隊列Q狀態(tài)不變；（3）EnQuene(&Q，x)

若隊列Q還有空間，將元素x插入到隊尾；（4）DelQueue(&Q，&y)

若隊列Q不為空，刪除隊列Q的隊頭元素，y返回其值；（5）Empty(&Q)

判斷隊列Q是否為空，若為空返回一個真值，否則返回一個假值。3.2隊列3.2.2隊列的順序存儲結(jié)構(gòu)及其運算1.順序隊列（sequentialqueue）順序隊列與順序表一樣，用一個一維數(shù)組來存放數(shù)據(jù)元素。在內(nèi)存中，用一組連續(xù)的存儲單元順序存放隊列中各元素。例如，用數(shù)組element存放隊列元素，數(shù)組最大容量為MAXLEN，隊首指針為front，隊尾指針為rear。隊首指針front指向隊列中第一個元素的前一個位置。隊尾指針rear指向隊列中最后一個元素的位置。3.2隊列空隊列

front＝

rear隊滿

rear＝MAXLEN-1添加一個元素

rear＝

rear+1刪除一個元素

front＝

front+13.2隊列（1）入隊3.2隊列首先要判斷是否隊滿。若發(fā)生隊滿，應返回隊滿信息0。若隊不滿，則插入元素。q->rear++;q->element[q->rear]=x;q->rear==MAXLEN-1（2）出隊3.2隊列首先要判斷是否隊空。若隊空，應返回隊空值0。若隊非空，則刪除元素。q->front++;x=q->element[q->front];q->front==q->rear順序隊列存在“假溢出”問題：尾指針rear指向最后一個元素，但前面有元素已經(jīng)出隊，這時要插入元素，仍然發(fā)生溢出，而實際上隊列并未滿。2.循環(huán)隊列循環(huán)隊列將首尾相連，即將element［0］與element［MAXLEN-1］連接起來，形成一個環(huán)形表。3.2隊列在循環(huán)隊列中，當rear=front時，不能判定循環(huán)隊列是空隊還是滿隊。因此規(guī)定：

front=rear是循環(huán)隊列空的標志。

(rear+1)%MAXLEN=front是循環(huán)隊列滿的標志。所以，在循環(huán)隊列滿時，隊列中實際上還有一個空閑單元，以防止空隊與滿隊的標志發(fā)生沖突。（1）入隊3.2隊列首先要判斷是否隊滿。若隊滿，應返回隊滿信息0。若隊不滿，則插入新元素。(cq->rear+1)%MAXLEN==cq->frontcq->rear=(cq->rear+1)%MAXLEN;cq->element[cq->rear]=x;（2）出隊3.2隊列首先要判斷是否隊空。若隊為空，應返回隊空信息0。若隊不為空，則將隊首元素存入x中。cq->rear==cq->frontcq->front=(cq->front+1)%MAXLEN;x=cq->element[cq->front];3.2.3隊列的鏈式存儲結(jié)構(gòu)及其運算3.2隊列隊列的鏈式存儲結(jié)構(gòu)稱為鏈隊列（linkedqueue）。隊列頭指針front指向隊列表頭結(jié)點，隊列尾指針指向隊列的尾結(jié)點。隊列空的條件是front=rear（1）入隊3.2隊列首先要向系統(tǒng)申請一個結(jié)點的存儲空間;

將新元素的值寫入新結(jié)點的數(shù)據(jù)域中；然后修改鏈隊列尾指針。p->data=x;p->next=NULL;rear->next=p;rear=p;（2）出隊3.2隊列從帶表頭結(jié)點的鏈隊列中刪除隊首元素。p=front->next;front->next=p->next;x=p->data;free(p);/*如果原鏈隊列只有一個元素*/if(p->next==NULL)rear=fron