第三章堆棧和隊列

第三章堆棧和隊列中國礦業(yè)大學(xué)（北京）2010年春季主講：李佳靜lijj@主要內(nèi)容知識點棧與隊列的特征棧與遞歸循環(huán)隊列重點難點棧的操作遞歸循環(huán)隊列棧與隊列的綜合應(yīng)用內(nèi)容安排3.1棧的類型定義3.2棧類型的實現(xiàn)3.3棧的應(yīng)用舉例3.4隊列的類型定義3.5隊列類型的實現(xiàn)棧(stack)的類型定義3.1棧的類型定義棧是操作受限制的線性表定義：僅在表尾進行插入或刪除操作的線性表；概念：棧頂：在棧頂操作，是表尾，通常用top表示；棧底：bottom，是表頭；空棧:空表；通常棧底固定，棧頂移動。棧(stack)示意圖a1a2a3an…棧頂top棧底

bottom表頭表尾3.1棧的類型定義棧操作示例(1/2)base空棧a進棧b進棧aabtopbasetopbasetop3.1棧的類型定義棧操作示例(1/2)toptopabcdee進棧abcdef進棧溢出abde出棧cbasebasebasetop3.1棧的類型定義3.1棧的類型定義

ADTStack

{

數(shù)據(jù)對象：

D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}

數(shù)據(jù)關(guān)系：

R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

約定an

端為棧頂，a1端為棧底。

基本操作：

}ADTStack3.1棧的類型定義InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTravers(S,visit())3.1棧的類型定義InitStack(&S)

操作結(jié)果：構(gòu)造一個空棧SDestroyStack(&S)

初始條件：棧S已存在。

操作結(jié)果：棧S被銷毀3.1棧的類型定義InitStack(&S)

操作結(jié)果：構(gòu)造一個空棧SDestroyStack(&S)

初始條件：棧S已存在。

操作結(jié)果：棧S被銷毀StackEmpty(S)

初始條件：棧S已存在。

操作結(jié)果：若棧S為空棧，則返回TRUE，否則FALE。3.1棧的類型定義StackLength(S)

初始條件：棧S已存在。

操作結(jié)果：返回S的元素個數(shù)，即棧的長度。3.1棧的類型定義GetTop(S,&e)

初始條件：棧S已存在且非空。

操作結(jié)果：用e返回S的棧頂元素。a1a2an……3.1棧的類型定義ClearStack(&S)

初始條件：棧S已存在。

操作結(jié)果：將S清為空棧3.1棧的類型定義Push(&S,e)

初始條件：棧S已存在。

操作結(jié)果：插入元素e為新的棧頂元素。a1a2ane……3.1棧的類型定義Pop(&S,&e)

初始條件：棧S已存在且非空。

操作結(jié)果：刪除S的棧頂元素，并用e返回其值。a1a2anan-1

……3.1棧的類型定義內(nèi)容安排3.1棧的類型定義3.2棧類型的實現(xiàn)順序棧鏈棧3.3棧的應(yīng)用舉例3.4隊列的類型定義3.5隊列類型的實現(xiàn)棧的順序存儲表示//-----棧的順序存儲表示

-----

#defineSTACK_INIT_SIZE100;

#defineSTACKINCREMENT10;

typedefstruct{

SElemType

*base;

SElemType

*top;

intstacksize;

}

SqStack;

類似于線性表的順序映象實現(xiàn)，指向表尾的指針可以作為棧頂指針。3.2棧類型的實現(xiàn)InitStack在順序棧中的實現(xiàn)

StatusInitStack(SqStack&S){//構(gòu)造一個空棧SS.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));

if(!S.base)exit(OVERFLOW);//存儲分配失敗

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

returnOK;}3.2棧類型的實現(xiàn)Push在順序棧中的實現(xiàn)

StatusPush(SqStack&S,SElemTypee){if(S.top-S.base>=S.stacksize){//棧滿，追加存儲空間

S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*

sizeof(ElemType));

if(!S.base)exit(OVERFLOW);//存儲分配失敗

S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;

}

*S.top++=e;

returnOK;}3.2棧類型的實現(xiàn)Pop在順序棧中的實現(xiàn)StatusPop(SqStack&S,SElemType&e){//若棧不空，則刪除S的棧頂元素，

//用e返回其值，并返回OK；

//否則返回ERROR

if

(S.top

==

S.base)

returnERROR;

e=*--S.top;

returnOK;}3.2棧類型的實現(xiàn)鏈棧棧頂指針∧a1an注意:鏈棧中指針的方向an-13.2棧類型的實現(xiàn)內(nèi)容安排3.1棧的類型定義3.2棧類型的實現(xiàn)3.3棧的應(yīng)用舉例3.4隊列的類型定義3.5隊列類型的實現(xiàn)例一數(shù)制轉(zhuǎn)換算法基于原理：

N=(Ndivd)×d+Nmodd例如：（1348)10=(2504)8

，其運算過程如下：3.3棧的應(yīng)用舉例voidconversion(){InitStack(S);

scanf("%d",N);

while(N){

Push(S,N%8);N=N/8;

}

while(!StackEmpty(S)){

Pop(S,e);

printf("%d",e);

}}//conversion編程實現(xiàn)3.3棧的應(yīng)用舉例例二、括號匹配的檢驗假設(shè)在表達式中正確的格式為：（［］（））或［（［］［］）］不正確的格式為［（］）或（［（））或（（）］)則檢驗括號是否匹配的方法可用“期待的急迫程度”這個概念來描述。3.3棧的應(yīng)用舉例用期待的急迫程度描述括號匹配即后出現(xiàn)的“左括弧”，它等待與其匹配的“右括弧”出現(xiàn)的“急迫”心情要比先出現(xiàn)的左括弧高對“左括弧”來說，后出現(xiàn)的比先出現(xiàn)的“優(yōu)先”等待檢驗對“右括弧”來說，每個出現(xiàn)的右括弧要去找在它之前“最后”出現(xiàn)的那個左括弧去匹配顯然，必須將先后出現(xiàn)的左括弧依次保存，為了反映這個優(yōu)先程度，保存左括弧的結(jié)構(gòu)用棧最合適這樣對出現(xiàn)的右括弧來說，只要"棧頂元素"相匹配即可。如果在棧頂?shù)哪莻€左括弧正好和它匹配，就可將它從棧頂刪除3.3棧的應(yīng)用舉例算法的設(shè)計思想1）凡出現(xiàn)左括弧，則進棧；2）凡出現(xiàn)右括弧首先檢查棧是否空若棧空，則表明該“右括弧”多余否則和棧頂元素比較,若相匹配，則“左括弧出?！?，否則表明不匹配。3）表達式檢驗結(jié)束時，若?？?，則表明表達式中匹配正確,否則表明“左括弧”有余。3.3棧的應(yīng)用舉例編程實現(xiàn)3.3棧的應(yīng)用舉例Statusmatching(charexp[]){intstate=1;while(i<=Length(exp)&&state){switchexp[i]{case'('||'['

:{Push(S,exp[i]);i++;break;}case')'

:{if(！StackEmpty(S)&&GetTop(S)='('）

{Pop(S,e);i++;}else{state=0;}break;}case‘]'

:{if(！StackEmpty(S)&&GetTop(S)=‘['）

{Pop(S,e);i++;}else{state=0;}break;}}if(StackEmpty(S)&&state)returnOK;…...內(nèi)容安排3.1棧的類型定義3.2棧類型的實現(xiàn)3.3棧的應(yīng)用舉例3.4隊列的類型定義3.5隊列類型的實現(xiàn)隊列(Queue)的定義隊列：隊列是一種只允許在表的一端插入，在另一端刪除的存取受限的線性表。概念：隊尾rear：插入端，線性表的表尾。隊頭front：刪除端，線性表的表頭3.4隊列的類型定義隊列(Queue)圖示FIFO（FirstInFirstOut）（先進先出表）a1a2a3an-1出隊列入隊列隊頭隊尾……3.4隊列的類型定義隊列舉例例如，在一個局域網(wǎng)上有一臺共享的網(wǎng)絡(luò)打印機，網(wǎng)上每個用戶都可以將數(shù)據(jù)發(fā)送給網(wǎng)絡(luò)打印機進行輸出為了保證不丟失數(shù)據(jù)，操作系統(tǒng)為網(wǎng)絡(luò)的打印機生成一個"作業(yè)隊列“每個申請輸出的“作業(yè)”應(yīng)按先來后到的順序排隊打印機從作業(yè)隊列中逐個提取作業(yè)進行打印3.4隊列的類型定義隊列的類型定義

ADTQueue{

數(shù)據(jù)對象：

D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}

數(shù)據(jù)關(guān)系：

R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

約定其中a1

端為隊列頭，an

端為隊列尾基本操作：}

ADTQueue3.4隊列的類型定義隊列的基本操作

InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q,&e)ClearQueue(&Q)DeQueue(&Q,&e)EnQueue(&Q,e)QueueTravers(Q,visit())3.4隊列的類型定義

InitQueue(&Q)

操作結(jié)果：構(gòu)造一個空隊列Q

DestroyQueue(&Q)

初始條件：隊列Q已存在。

操作結(jié)果：隊列Q被銷毀，不再存在。3.4隊列的類型定義

QueueEmpty(Q)

初始條件：隊列Q已存在。

操作結(jié)果：若Q為空隊列，則返回TRUE，否則返回FALSE3.4隊列的類型定義

QueueLength(Q)

初始條件：隊列Q已存在。

操作結(jié)果：返回Q的元素個數(shù)，即隊列的長度。3.4隊列的類型定義

GetHead(Q,&e)

初始條件：Q為非空隊列。

操作結(jié)果：用e返回Q的隊頭元素。a1a2an……3.4隊列的類型定義

ClearQueue(&Q)

初始條件：隊列Q已存在。

操作結(jié)果：將Q清為空隊列。3.4隊列的類型定義

EnQueue(&Q,e)

初始條件：隊列Q已存在。

操作結(jié)果：插入元素e為Q的新的隊尾元素。a1a2ane……3.4隊列的類型定義

DeQueue(&Q,&e)

初始條件：Q為非空隊列。

操作結(jié)果：刪除Q的隊頭元素，并用e返回其值a1a2an……

3.4隊列的類型定義內(nèi)容安排3.1棧的類型定義3.2棧類型的實現(xiàn)3.3棧的應(yīng)用舉例3.4隊列的類型定義3.5隊列類型的實現(xiàn)鏈隊列——鏈?zhǔn)接诚笱h(huán)隊列——順序映象鏈隊列——鏈?zhǔn)接诚笥面湵肀硎镜年犃泻喎Q為鏈隊列。為便于操作，一個鏈隊列需要分別指示隊頭和隊尾的兩個指針

…a2rearfronta1an∧3.5隊列類型的實現(xiàn)鏈隊示意圖(a)非空隊frontreara1an∧

…a2Q(b)空隊rearfrontQ

∧

(c)鏈隊中只有一個元素結(jié)點frontrearQa1∧

3.5隊列類型的實現(xiàn)鏈隊列的定義

typedefstructQNode{//結(jié)點類型

QElemTypedata;

structQNode*next;

}QNode,*QueuePtr;3.5隊列類型的實現(xiàn)typedefstruct{//鏈隊列類型

QueuePtrfront;//隊頭指針

QueuePtrrear;//隊尾指針}LinkQueue;a1∧an…Q.frontQ.rearQ.frontQ.rear∧空隊列3.5隊列類型的實現(xiàn)InitQueue在鏈隊列中的實現(xiàn)

StatusInitQueue(LinkQueue&Q){//構(gòu)造一個空隊列Q

Q.front=Q.rear=

(QueuePtr)malloc(sizeof(QNode));

if(!Q.front)exit(OVERFLOW);//存儲分配失敗

Q.front->next=NULL;

returnOK;}3.5隊列類型的實現(xiàn)EnQueue在鏈隊列中的實現(xiàn)

StatusEnQueue(LinkQueue&Q,QElemTypee){//插入元素e為Q的新的隊尾元素

p=(QueuePtr)malloc(sizeof(QNode));

if(!p)exit(OVERFLOW);//存儲分配失敗

p->data=e;p->next=NULL;

Q.rear->next=p;Q.rear=p;

returnOK;}3.5隊列類型的實現(xiàn)DeQueue在鏈隊列中的實現(xiàn)

StatusDeQueue(LinkQueue&Q,QElemType&e){//若隊列不空，則刪除Q的隊頭元素，

//用e返回其值，并返回OK；否則返回ERROR

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;}3.5隊列類型的實現(xiàn)循環(huán)隊列——順序映象#defineMAXQSIZE100//最大隊列長度

typedefstruct{QElemType*base;//動態(tài)分配存儲空間

intfront;//頭指針，若隊列不空，

//指向隊列頭元素

intrear;//尾指針，若隊列不空，指向

//隊列尾元素的下一個位置

}SqQueue;3.5隊列類型的實現(xiàn)隊列的順序表示約定隊頭指針指向隊列頭元素，隊尾指針指向隊尾元素的下一個位置frontJ1J2J3J4frontrearJ1J2J3J4frontrearfrontrearJ1frontrearJ1J2J3J4J6J5rear543210543210問題：如何解決“假上溢”現(xiàn)象?3.5隊列類型的實現(xiàn)循環(huán)隊列3.5隊列類型的實現(xiàn)循環(huán)隊列操作示意圖3.5隊列類型的實現(xiàn)a5a6a7a8a10a11a12a13a14a5a6a7a8a9a10a11a12a13a5a6a7a8a90123456789frontrearfrontrearrearfrontfrontrear循環(huán)隊列的狀態(tài)問題空隊列條件：Q.rear=Q.front;滿隊列條件：Q.rear=Q.front;問題：如何區(qū)別隊空和隊滿有三種方法1.犧牲一個存儲空間2.引入一個標(biāo)志變量區(qū)別空和不空3.使用計數(shù)器3.5隊列類型的實現(xiàn)InitQueue在循環(huán)隊列中的實現(xiàn)

StatusInitQueue(SqQueue&Q){//構(gòu)造一個空隊列QQ.base=(ElemType*)mal