0-1開課

數據結構與算法DATASTRUCTURE&ALGORITHM天津理工大學計算機科學與工程學院第三章棧和隊列1棧的定義及操作特性2棧的實現及應用3隊列的定義及操作特性4隊列的實現及應用3.1棧的邏輯結構棧的定義棧的邏輯特性棧的抽象數據類型定義棧的定義棧：限定僅在一端進行插入和刪除操作的線性表（a1,…,an-1,an）棧頂（top）：允許插入和刪除的一端稱為棧頂棧底（bottom）：另一端稱為棧底插入位置：1~n+1刪除位置：1~n線性表插入位置：n+1刪除位置：n棧棧底棧頂棧的操作特性插入：入棧、進棧、壓棧刪除：出棧、彈棧a插入刪除bc棧的操作特性：后進先出（Last

InFirstOut，LIFO）條件判斷

此時執行出棧操作，哪個元素可以出棧呢？空棧：不含任何數據元素的棧

abc例：有三個元素按a、b、c的次序依次進棧，且每個元素只允許進一次棧，則可能的出棧序列有多少種？情況一出棧：cbaab情況二出棧：bca能否得到如下出棧序列？出棧：cabc棧的操作特性棧只是對插入和刪除操作的位置進行了限制并沒有限定插入和刪除操作進行的時間棧的抽象數據類型定義ADTStack{數據對象:D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}數據關系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}基本操作：}ADTInitStack：棧的初始化DestroyStack：棧的銷毀Push：入棧Pop：出棧GetTop：取棧頂元素Empty：判空Push操作需要指明插入位置嗎？相對于其他數據結構，棧的基本操作是確定的3.2棧的存儲與實現棧的順序存儲—順序棧棧的鏈式存儲—鏈棧順序棧的存儲結構順序棧：棧的順序存儲結構

012345678如何表示棧頂：設變量top存儲棧頂元素所在的下標如何表示棧底：用數組的一端作為棧底topabc如何改造數組實現棧的順序存儲？順序棧的存儲結構定義typedefstruct{data[];/*存放棧元素的數組*/

inttop;

/*棧頂位置，棧頂元素在數組中的下標*/}SeqStack;#defineStackSize100/*假定棧元素最多100個*/StackSizetypedefintDataType;

/*定義棧元素的數據類型，假設為int型*/DataType

012

…

StackSize-1topabc、游標棧頂指針順序棧的實現定義一個順序棧：SeqStack*s;順序棧的實現——初始化初始化一個空棧，成功返回1，否則返回0

012

…

StackSize-1topintInitStack(SeqStack*&s)

{s=(SeqStack*)malloc(sizeof(SeqStack));//申請存儲空間if(s!=NULL){/*將順序棧置空*/ s->top=-1;

return1;}

else{

printf("內存空間申請失敗，程序運行終止!\n");

return0;}}棧的初始化要完成哪些工作？順序棧的實現——判空判斷棧是否為空，如果棧為空，返回1；否則，返回0

012

…

StackSize-1abctopintEmpty(SeqStack*S){if(S->top==-1)return1;elsereturn0;}棧空：top=-1判空的算法是什么?順序棧的實現——入棧在棧頂插入一個元素x，如果插入成功，棧頂增加一個元素；否則返回失敗信息

012

…

StackSize-1topabcx入棧的算法是什么?棧滿：top=StackSize-1intPush(SeqStack*&S,DataTypex){

S->top++;

S->data[S->top]=x;

return1;}if(S->top==StackSize-1){

printf("上溢錯誤，插入失敗\n");return0;

}什么情況下無法入棧？時間復雜度？刪除棧頂元素，如果刪除成功，返回被刪元素值；否則返回失敗信息

012

…

StackSize-1abctop順序棧的實現——出棧出棧的算法是什么?棧空：top=-1intPop(SeqStack*S,DataType&e){e=S->data[S->top];S->top--;

return1;}if(S->top==-1){

printf("棧空！出棧操作失敗！\n");return0;

}什么情況下無法出棧？取棧頂元素的實現？鏈棧的存儲結構定義鏈棧：棧的鏈接存儲結構firsta1a2an∧ai棧頂topanan-1a1∧firsta1a2an∧aiA：為方便操作，用鏈頭作為棧頂A：鏈棧無須加頭結點單鏈表是如何存儲線性表的？用鏈表的哪一端作為棧頂？鏈棧需要加頭結點嗎？單鏈表為什么加頭結點？鏈棧的存儲結構定義棧頂topanan-1a1∧typedefstructLNode{data;/*存放棧元素的數據域*/

structLNode*next;/*存放下一個結點的地址*/}LNode;LNode*top;typedefintDataType;/*棧元素的數據類型，假設為int型*/

DataType鏈棧的實現——入棧topanan-1a1∧xstopintPush(LNode*&top,DataTypex){

LNode*s=(Node*)malloc(sizeof(LNode));if(s){s->data=x;s->next=top;top=s; return1;}else{printf("內存空間不足!\n"); return0; }}入棧的算法是什么？鏈棧的入棧操作為什么不用判斷是否棧滿？鏈棧的實現——出棧intPop(LNode*&top,DataType&e){

e=top->data;

return1;}topanan-1a1∧topp

if(top==NULL){printf("棧空，刪除失敗\n");return0;}LNode*p=top;top=top->next;free(p);top=NULL空棧出棧的算法是什么？什么情況下無法刪除？鏈棧的實現——取棧頂intPop(LNode*top,DataType&e){

e=top->data;

return1;}topanan-1a1∧topp

if(top==NULL){printf("下溢錯誤，刪除失敗\n");return0;}LNode*p=top;top=top->next;free(p);top=NULL空棧在實際問題的處理過程中，有些數據具有后到先處理的特點【問題】中綴表達式求值：根據算符優先法對表達式求值，所討論的算術運算符包括：+、-、*、/、%、^(乘方)和括號()。運算規則為：運算符的優先級為:()→^→＊、/、%→+、-；有括號時先算括號內的，后算括號外的，多層括號由內向外進行；乘方連續出現時先算最右面的。【想法】自左向右掃描表達式，當掃描到某運算符時不能馬上計算，因后面可能還有更高的運算，需先保存，根據后面運算符優先級決定處理順序。用棧保存運算符、運算數如何保存已經掃描過尚未處理的運算符、運算數，按正確優先級計算？3.3棧的應用舉例【分析】表達式作為一個串存儲，如表達式“3*2^(4+2*2-1*3)-5”,其求值過程為：自左向右掃描表達式，當掃描到3*2時不能馬上計算，因后面可能還有更高的運算，正確的處理過程是：需要兩個棧：對象棧OPND和算符棧OPTR;自左至右掃描表達式,若當前字符是運算對象，入OPND棧;對運算符，若這個運算符比棧頂運算符高則入棧，繼續向后處理，若這個運算符比棧頂運算符低則從OPND棧出棧兩個數，從OPTR棧出棧一運算符進行運算，并將其運算結果入OPND棧，繼續處理當前字符，直到遇到結束符中綴表達式求值【算法】中綴表達式求值3*2^(4+2*2-1*3)-5求值過程中綴表達式求值中綴表達式轉換為后綴表達式在實際問題的處理過程中，有些數據具有后到先處理的特點【問題】后綴表達式中運算符在運算數的后面，如2+4*5的后綴表達式為245*+。后綴表達式中已經考慮了算法的優先級，沒有括號，只有運算數和運算符，越放在前面的運算符優先級越高。為了處理方便，編譯程序常把中綴表達式轉換成等價的后綴表達式。【分析】中綴表達式轉換成后綴表達式時，運算數之間的相對次序是不變的，故從左向右掃描算術表達式，將遇到的運算數直接存放到后綴表達式中，但遇到的每一個運算符，需要按照算符優先級改變相對次序，同時還要去除括號。用棧保存運算符如何保存已經掃描過尚未處理的運算符，按正確優先級計算？【算法】假設用postex[]字符數組存儲轉換后的后綴表達式，轉換過程中用來存儲運算符的臨時棧為OPTR，初始時為空，則將輸入的中綴表達式轉換成后綴表達式的過程為：（1）將棧OPTR初始化為空，將定界符#壓入棧底，設m=0；（2）自左向右掃描從鍵盤輸入的表達式，對每一個字符執行下述操作，直到遇到定界符。若當前運算符優先級比OPTR棧頂運算符優先級低，則將OPTR棧頂元素出棧，存放到postex[m]中且m++；若當前運算符優先級與OPTR棧頂運算符優先級相同，則將OPTR棧頂元素出棧，繼續處理下一字符；若當前字符是運算符，并且該運算符優先級比OPTR棧頂運算符優先級高，則將該運算符入OPTR棧，繼續處理下一字符；若當前字符是運算數，將其存放到postex[m]中且m++，繼續處理下一字符；將’\0’存入postex[m]，postex數組存儲的即為轉換后的后綴表達式。中綴表達式轉換為后綴表達式3.4隊列的邏輯結構隊列：只允許在表的一端進行插入操作，在另一端進行刪除操作（a1,a2,…,an-1,an）隊尾：允許插入的一端，相應地，位于隊尾的元素稱為隊尾元素a1

a2

…

an棧a1

a2

…

an隊列隊頭隊尾隊頭：允許刪除的一端，相應地，位于隊頭的元素稱為隊頭元素隊列的操作特性插入：入隊、進隊隊列的操作特性：先進先出（FirstInFirstOut，FIFO）a入隊出隊bc例：有三個元素按a、b、c的次序依次入隊，且每個元素只允許進一次隊，則出隊序列是什么？答：出隊序列只有一種情況：abc刪除：出隊空隊列：不含任何數據元素的隊列

任何時候執行出隊操作，一定是哪個元素呢？隊列的抽象數據類型定義ADTQueue{數據對象:D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}數據關系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}基本操作：}ADT與棧類似，隊列的基本操作是確定的InitQueue：隊列的初始化DestroyQueue：隊列的銷毀EnQueue：入隊DeQueue：出隊GetQueue：取隊頭元素Empty：判空3.5隊列的存儲與實現隊列的順序存儲—順序隊列

—循環隊列棧隊列的鏈式存儲—鏈式隊列棧順序隊列順序隊列：隊列的順序存儲結構存儲方式用一段地址連續的存儲單元依次存儲隊列中數據元素設置兩個指示變量front,rear分別指示隊頭、隊尾元素的下標位置an……a3a2a1frontrear約定：隊頭front指向隊頭元素，隊尾rear指向隊尾元素的下一個位置順序隊列的存儲結構定義typedefstruct{

data[];

/*存放隊列元素的數組*/

intfront,rear;

/*下標，隊頭元素和隊尾元素的位置*/}SeqQueue;#defineMaxSiz100

/*定義數組的最大長度*/

MaxSizetypedefintDataType;

/*隊列元素的數據類型，假設為int型*/DataType入隊：

元素入隊

rear+1frontrear空隊列rearfront入隊A

B

rearrearrearrearC

rearrearD

rearrear出隊

frontrear

frontrear入隊

E

rearrearF

出隊：

元素出隊

front+1整個隊列向數組下標較大方向移動單向移動性假溢出：數組空間發生上溢，但數組的低端還有空閑空間隊列的單向移動性會產生什么問題？循環隊列01234a3a4rearfronta5a6if(rear+1>4)

rear=0;else

rear++;循環隊列：隊列采用順序存儲，并且數組是頭尾相接的循環結構程序技巧：求模（正余數）使得數組下標循環rear=(rear+1)%5012345CDEFfrontrear如何解決假溢出？如何使數組下標循環？循環隊列的實現——初始化01234rearfrontintInitQueue(SeqQueue*&Q){Q=(SeqQueue*)malloc(sizeof(SeqQueue));//申請存儲空間if(Q!=NULL){//隊列置空Q->front=Q->rear=0;return1;}else{printf("申請存儲空間失敗,程序運行終止!\n"); return0;}}循環隊列：隊列采用順序存儲，并且數組是頭尾相接的循環結構設置隊頭、隊尾兩個位置指針循環隊列的實現——判空01234a2rearfront隊空的判定條件：front=rearintEmpty(SeqQueue*Q){

if(Q->rear==Q->front)return1;elsereturn0;}如何判斷循環隊列的隊空？隊空和隊滿a6a2a4a5rearfront隊空的判定條件：front=rear隊滿的判定條件：front=rearx01234如何判斷循環隊列的隊滿？01234a6a2a4a5rearfront隊空的判定條件：front=rear隊滿的判定條件：front=rear數組中有一個空閑單元01234a1a2a4a5rearfront(rear+1)%MaxSize=front隊空和隊滿如何確定不同的隊空、隊滿的判定條件？循環隊列的實現——入隊intEnQueue(SeqQueue*Q,DataTypex){

Q->data[Q->rear]=x;return1;}01234a3a4rearfrontQ->rear=(Q->rear+1)%QueueSize;if((Q->rear+1)%MaxSize==Q->front){printf("隊滿,入隊操作失敗!\n");return0;}x入隊的算法是什么？時間復雜度是多少？循環隊列的實現——出隊intDeQueue(SeqQueue*Q,DataType&e){

e=Q->data[Q->front];return1;}Q->front=(Q->front+1)%MaxSize;if(Q->rear

==Q->front){printf(“隊空,

出隊操作失敗!\n");return0;}取隊頭元素的實現a2a3a4rearfront出隊的算法是什么？刪除隊頭元素，如果刪除成功，返回被刪元素值；否則給出失敗信息鏈隊列的存儲結構鏈隊列：隊列的鏈接存儲結構firsta1a2an∧aiA：鏈頭作為隊頭，出隊時間為O(1)

鏈尾作為隊尾，入隊時間為O(n)rearfront設置隊尾指針rear用鏈表的哪一端作為隊頭？哪一端作為隊尾？鏈隊列的存儲結構鏈隊列：隊列的鏈接存儲結構-通常將隊頭和隊尾兩個指針合起來∧∧frontrear鏈隊列需要加頭結點嗎？鏈隊列的存儲結構定義typedefstructLNode

/*定義鏈隊列的結點結構*/{

data;structLNode*next;}LNode;typedefstruct/*定義鏈隊列*/{LNode*front,*rear;}LinkQueue;typedefintDataType;/*定義隊列元素的數據類型，假設為int型*/DataType

定義一鏈隊列

LinkQueue*Q;隊頭結點：

Q->front->next隊尾結點：Q->rear隊尾結點數據：

Q->rear->data鏈隊列的實現——初始化intInitQueue(LinkQueue*&Q){

LNode*p;

Q=(LinkQueue*)malloc(sizeof(LinkQueue));/*創建鏈隊結點*/

p=(LNode*)malloc(sizeof(LNode)); /*申請頭結點存儲空間*/

if

(p!=NULL)

{p->next=NULL; /*頭結點指針域置空*/

Q->front=Q->rear=p;

return1;

}

else

{printf("初始化失敗!\n"); /*初始化失敗*/ return0;

}}∧∧frontrear初始化要做什么？鏈隊列的實現——入隊xs∧Q->rear=s;Q->front=s;intEnQueue(LinkQueue*Q,DataTypex){

LNode*s=(LNode*)malloc(sizeof(LNode));/*申請結點空間*/if(!p){printf("申請隊列結點空間失敗，程序運行終止!\n"); return0; }else{s->data=x;s->next=NULL;

Q->rear->next=s;Q->rear=s;

return1;}

}a1a2an∧aifrontrear入隊的算法是什么？沒有頭結點會怎樣？時間復雜度是多少？p邊界情況：隊列中只有一個元素a1a2an∧frontrear判斷隊空？(Q->front=Q->rear),若已空，下溢刪除隊頭結點P(P=Q->front->next):Q->front->next=P->next3)剛刪除結點是否鏈隊列最后一個結點？若Q->rear=P，表明P是隊列中唯一結點，刪除P后，隊列應為空：Q->rear=Q->front4)釋放P結點空間分析：鏈隊列的實現——出隊出隊的算法是什么？pa1a2an∧frontrearintDeQueue(LinkQueue*Q,DataType&e){LNode*p;

if(Q->front==Q->rear)/*空隊列*/{printf("隊列為空，出隊操作失敗!\n");return0;}p=Q->fornt->next;e=p->data;/*p指向隊頭結點*/Q->front->next=p->next;/*刪除隊頭結點*/

if(Q->rear==p)Q->rear=Q->front;