專業(yè)課-數(shù)據(jù)結(jié)構(gòu)棧和隊列

第3章棧和隊列3.1棧3.2棧的應(yīng)用舉例3.3棧與遞歸的實現(xiàn)3.4隊列2022/12/19第3章13.1棧(Stack)1.定義：限定只在表的一端(表尾)進行插入和刪除操作的線性表特點:后進先出(LIFO)允許插入和刪除

的一端稱為棧頂

(top)，另一端稱

為棧底(bottom)

2022/12/19第3章2表尾表頭2.棧的表示和實現(xiàn)1）順序?！獥５捻樞虼鎯Y(jié)構(gòu)2）鏈?！獥５逆準酱鎯Y(jié)構(gòu)3）靜態(tài)分配整型指針2022/12/19第3章31）順序?！獥５捻樞虼鎯Y(jié)構(gòu)限定在表尾進行插入和刪除操作的順序表類型定義：p46typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;SqStacks;2022/12/19第3章4說明：base稱為棧底指針，始終指向棧底； 當base==NULL時，表明棧結(jié)構(gòu)不存在。top為棧頂指針

a.top的初始值指向棧底，即top=baseb.空棧：當top=base時為?？盏臉擞?/p>

c.當棧非空時，top的位置：指向當前棧頂元素的下一個位置stacksize——當前?？墒褂玫淖畲笕萘?022/12/19第3章52022/12/19第3章6

進棧示例basebasebasebasebasestacksize2022/12/19第3章7退棧示例

basebasebasebasebase幾點說明：?？諚l件：s.top==s.base此時不能出棧棧滿條件：s.top-s.base>=s.stacksize進棧操作：*s.top++=e;或*s.top=e;s.top++;退棧操作：e=*--s.top；或s.top--；e=*s.top；當棧滿時再做進棧運算必定產(chǎn)生空間溢出，簡稱“上溢”;當?？諘r,再做退棧運算也將產(chǎn)生溢出，簡稱為“下溢”。2022/12/19第3章8基本操作的實現(xiàn)

棧的初始化操作p47 StatusInitStack(SqStack&S)

取棧頂元素p47 StatusGetTop(SqStackS,SElemType&e)

進棧操作p47 StatusPush(SqStack&S,SElemTypee)

退棧操作p47 StatusPop(SqStack&S,SElemType&e)2022/12/19第3章9棧的初始化操作p47StatusInitStack(SqStack&S){

S.base=(SElemType)malloc(STACK_INIT_SIZE*sizeof(ElemType)); if(!S.base)return(OVERFLOW); S.top=S.base; S.stacksize=STACK_INIT_SIZE; returnOK;}2022/12/19第3章10取棧頂元素p47StatusGetTop(SqStackS,SElemType&e){ if(S.top==S.base)returnERROR; e=*(S.top-1); returnOK;}2022/12/19第3章11進棧操作p47StatusPush(SqStack&S,SElemTypee){if(S.top-S.base>=S.stacksize){S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));if(!S.base)return(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;/**S.top=e;S.top=S.top+1;returnOK;}2022/12/19第3章12退棧操作p47StatusPop(SqStack&S,SElemType&e){ if(S.top==S.base)returnERROR; e=*--S.top;/*S.top=S.top-1;e=*S.top; returnOK;}2022/12/19第3章132）鏈?！獥５逆準酱鎯Y(jié)構(gòu)不帶頭結(jié)點的單鏈表，其插入和刪除操作僅限制在表頭位置上進行。鏈表的頭指針即棧頂指針。類型定義：

typedefstructSNode{ SElemTypedata; structSNode*next; }SNode,*LinkStack; LinkStacks;2022/12/19第3章14鏈棧示意圖p47圖3.3棧空條件：s=NULL棧滿條件：無/無FreeMemory可申請2022/12/19第3章15進棧操作：StatusPush_L(LinkStack&s，SElemTypee){p=(LinkStack)malloc(sizeof(SNode));if(!p)exit(Overflow);p->data=e;p->next=s;s=p;returnOK;}2022/12/19第3章16退棧操作StatusPop_L(LinkStack&s,SElemType&e){if(!s)returnERROR;e=s->data;p=s;s=s->next;free(p);returnOK;}2022/12/19第3章173）靜態(tài)分配整型指針定義#defineMAXSIZE100typedefstruct{SElemTypebase[MAXSIZE];inttop;}SqStack;SqStacks;2022/12/19第3章18初始化statusInitStack(SqStack&s){s.top=0;returnOK;}2022/12/19第3章19進棧StatusPush(SqStack&s,SElemTypee){if(s.top==MAXSIZE)returnERROR;s.base[s.top]=e;s.top++;returnOK;}2022/12/19第3章20退棧StatusPop(SqStack&s,SElemType&e){if(s.top==0)returnERROR;s.top--;e=s.base[s.top];returnOK;}2022/12/19第3章21取棧頂元素StatusGetTop(SqStacks,SElemType&e){ if(s.top==0)returnERROR; e=s.base[s.top-1]; returnOK;}2022/12/19第3章223.2棧的應(yīng)用1.數(shù)制轉(zhuǎn)換p48算法3.12.行編輯程序p50算法3.23.表達式求值p52～p542022/12/19第3章231.數(shù)制轉(zhuǎn)換p48十進制N和其它進制數(shù)的轉(zhuǎn)換是計算機實現(xiàn)計的基本問題，基于下列原理:N=(ndivd)*d+nmodd(其中:div為整除運算,mod為求余運算)例如(1348)10=(2504)8，其運算過程如下： nndiv8nmod821021252022022/12/19第3章24低位高位算法3.1要求：輸入一個非負十進制整數(shù)，輸出任意進制數(shù)voidConversion(){InitStack(s);scanf("%d,%d",&N,&base);N1=N;while(N1){Push(s,N1%base);N1=N1/base;}while(!(StackEmpty(s)){Pop(s,e);if(e>9)printf("%c",e+55);elseprintf("%c",e+48);}printf("\n");}2022/12/19第3章252.行編輯程序p50算法3.2voidlineedit(){initstack(s);ch=getchar();while(ch!=eof){while(ch!=eof&&ch!=‘\n’){switch(ch){case‘#’:pop(s,c);case‘@’:clearstack(s);default:push(s,ch);}ch=getchar();}

把從棧底到棧頂?shù)臈?nèi)字符傳送到調(diào)用過程的數(shù)據(jù)區(qū);clearstack(s);if(ch!=eof)ch=getchar();}destroystack(s);}2022/12/19第3章263.表達式求值p52～p54算符間的優(yōu)先級關(guān)系p52～p53

先括弧內(nèi)后括弧外左括號：比括號內(nèi)的算符的優(yōu)先級低比括號外的算符的優(yōu)先級高右括號：比括號內(nèi)的算符的優(yōu)先級低 比括號外的算符的優(yōu)先級高#：優(yōu)先級總是最低為實現(xiàn)算符優(yōu)先算法，可使用兩個工作棧：

OPND棧：存數(shù)據(jù)或運算結(jié)果

OPTR棧：存運算符2022/12/19第3章27算法思想：1.初態(tài)：置OPND棧為空；將“#”作為OPTR棧的棧底元素2.依次讀入表達式中的每個字符

1）若是操作數(shù)，則進入OPND棧；

2）若是運算符，則與OPTR棧的棧頂運算符進行優(yōu)先權(quán)（級）的比較：

若讀入運算符的優(yōu)先權(quán)高，則進入OPTR棧；若讀入運算符的優(yōu)先權(quán)低，則OPTR退棧（退出原有的棧頂元素），OPND棧退出兩個元素（先退出b，再退出a），中間結(jié)果再進入OPND棧；若讀入“）”，OPTR棧的原有棧的棧頂元素若為“（”，則OPTR退出“（”；若讀入“#”，OPTR棧棧頂元素也為“#”，則OPTR棧退出“#”，結(jié)束。例：3*（7-2）2022/12/19第3章283.4隊列1.定義2.鏈隊列——隊列的鏈式存儲結(jié)構(gòu)3.循環(huán)隊列——隊列的順序存儲結(jié)構(gòu)2022/12/19第3章291.定義是限定在表的一端進行刪除，在表的另一端進

行插入操作的線性表。允許刪除的一端叫做隊頭(front)，允許插入的一端叫做隊尾(rear)。特性：FIFO(FirstInFirstOut)圖示p592022/12/19第3章30表頭表尾2.鏈隊列——隊列的鏈式存儲結(jié)構(gòu)實質(zhì)是帶頭結(jié)點的線性鏈表兩個指針：隊頭指針Q.front指向頭結(jié)點隊尾指針Q.rear指向尾結(jié)點初始態(tài)：隊空條件頭指針和尾指針均指向頭結(jié)點

Q.front=Q.rear2022/12/19第3章311）鏈隊列的類型定義p61typedefstructQNode{ //元素結(jié)點

QElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{//特殊結(jié)點QueuePtrfront; //隊頭指針

QueuePtrrear; //隊尾指針

}LinkQueue;LinkQueueQ;Q.front——指向鏈頭結(jié)點Q.rear——指向鏈尾結(jié)點2022/12/19第3章322）鏈隊列示意圖p61圖3.102022/12/19第3章33隊列運算指針變化狀況2022/12/19第3章34空隊列3）基本操作與實現(xiàn)初始化p62

StatusInitQueue(LinkQueue&Q)銷毀隊列p62

StatusDestroyQueue(LinkQueue&Q)入隊p62

StatusEnQueue(LinkQueue&Q,QElemTypee)出隊p62

StatusDeQueue(LinkQueue&Q,QElemType&e)判隊空

StatusQueueEmpty(LinkQueueQ)取隊頭元素

StatusGetHead(LinkQueueQ,QElemType&e)2022/12/19第3章35鏈隊列初始化StatusInitQueue(LinkQueue&Q){

Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q.front)exit(OVERFLOW); Q.front->next=NULL; returnOK;}2022/12/19第3章36鏈隊列的銷毀StatusDestroyQueue(LinkQueue&Q){ while(Q.front){Q.rear=Q.front->next; free(Q.front);Q.front=Q.rear; } returnOK;}2022/12/19第3章37鏈隊列的插入（入隊）StatusEnQueue(LinkQueue&Q,QElemTypee){p=(QueuePtr)malloc(sizeof(QNode)); if(!p)exit(OVERFLOW); p->data=e; p->next=NULL; Q.rear->next=p; Q.rear=p; returnOK;}2022/12/19第3章38鏈隊列的刪除（出隊）StatusDeQueue(LinkQueue&Q,ElemType&e){if(Q.front==Q.rear)returnERROR; p=Q.front->next; e=p->data; Q.front->next=p->next; if(Q.rear==p)Q.rear=Q.front; free(p); returnOK;}2022/12/19第3章39判斷鏈隊列是否為空StatusQueueEmpty(LinkQueueQ){ if(Q.front==Q.rear)returnTRUE; returnFALSE;}2022/12/19第3章40取鏈隊列的第一個元素結(jié)點StatusGetHead(LinkQueueQ,QElemType&e){ if(QueueEmpty(Q))returnERROR; e=Q.front->next->data; returnOK;}2022/12/19第3章413.循環(huán)隊列——隊列的順序存儲結(jié)構(gòu)順序隊列：——用一組地址連續(xù)的存儲單元依次存放從隊列頭到隊列尾的元素設(shè)兩個指針：——Q.front指向隊列頭元素；——Q.rear指向隊列尾元素的下一個位置初始狀態(tài)（空隊列）：Q.front=Q.rear=0隊列的真滿與假滿2022/12/19第3章42類型定義p64#defineMAXSIZE100typedefstruct{QElemType*base;intfront;intrear;}SqQueue;SqQueueQ;2022/12/19第3章432022/12/19第3章44隊列的進隊和出隊

進隊時，將新元素按Q.rear指示位置加入，再將隊尾指針增1，Q.rear=Q.rear+1。出隊時，將下標為Q.front的元素取出，再將

隊頭指針增1，Q.front=Q.front+1。

隊滿時再進隊將溢出出錯；隊空時再出隊作隊空處理。上圖為“假滿”循環(huán)隊列(CircularQueue)存儲隊列的數(shù)組被當作首尾相接的表處理。隊頭、隊尾指針加1時從maxsize-1直接進到0，可用語言的取模(余數(shù))運算實現(xiàn)。隊頭指針進1:Q.front=(Q.front+1)%MAXSIZE

隊尾指針進1:Q.rear=(Q.rear+1)%MAXSIZE;隊列初始化：Q.front=Q.rear=0;隊空條件：Q.front==Q.rear;隊滿條件：(Q.rear+1)%MAXSIZE==Q.front隊列長度：(Q.rear-Q.front+MAXSIZE)%MAXSIZE2022/12/19第3章45循環(huán)隊列的進隊和出隊2022/12/19第3章46說明不能用動態(tài)分配的一維數(shù)組來實現(xiàn)循環(huán)隊列，初始化時必須設(shè)定一個最大隊列長度。循環(huán)隊列中要有一個元素空間浪費掉

——p63約定隊列頭指針在隊列尾指針的下一位置上為“滿”的標志解決Q.front=Q.rear不能判別隊列“空”還是“滿”的其他辦法：使用一個計數(shù)器記錄隊列中元素的總數(shù)（即隊列長度）設(shè)一個標志變量以區(qū)別隊列是空或滿2022/12/19第3章47基本操作初始化p64StatusInitQueue(SqQueue&Q)求隊列的長度p64intQueueLength(SqQueueQ)入隊p65StatusEnQueue(SqQueue&Q,QElemTypee)出隊p65StatusDeQueue(SqQueue&Q,QElemType&e)判隊空StatusQueueEmpty(SqQueueQ)取隊頭元素StatusGetHead(SqQueueQ,QElemType&e)2022/12/19第3章48StatusInitQueue(SqQueue&Q){

Q.base=(QElemTye)malloc(MAXQSIZE*sizeof(QElemType)); if(!Q.base)exit(OVERFLOW); Q.front=Q.rear=0; returnOK;}2022/12/19第3章49intQueueLength(SqQ