數(shù)據(jù)結構林業(yè)信息學院第3章棧和隊列

2023年4月15日

北京林業(yè)大學信息學院李冬梅

數(shù)據(jù)結構

2023年4月15日

北京林業(yè)大學信息學院3.1

棧3.2棧的應用3.3棧與遞歸3.4隊列3.5隊列的應用教學內容

2023年4月15日

北京林業(yè)大學信息學院第3章棧和隊列掌握棧和隊列的特點，并能在相應的應用問題中正確選用熟練掌握棧的兩種存儲結構的基本操作實現(xiàn)算法，特別應注意棧滿和棧空的條件熟練掌握循環(huán)隊列和鏈隊列的基本操作實現(xiàn)算法，特別注意隊滿和隊空的條件理解遞歸算法執(zhí)行過程中棧的狀態(tài)變化過程

教學目標

2023年4月15日

北京林業(yè)大學信息學院棧（Stack）1.定義2.邏輯結構3.存儲結構4.運算規(guī)則5.實現(xiàn)方式隊列（Queue）1.定義2.邏輯結構3.存儲結構4.運算規(guī)則5.實現(xiàn)方式

2023年4月15日

北京林業(yè)大學信息學院3.1棧1.定義用順序?；蜴湕４鎯?，但以順序棧更常見3.存儲結構與線性表相同，仍為一對一關系2.邏輯結構只能在表的一端（棧頂）進行插入和刪除運算的線性表

2023年4月15日

北京林業(yè)大學信息學院只能在棧頂運算，且訪問結點時依照后進先出（LIFO）或先進后出（FILO）的原則4.運算規(guī)則關鍵是編寫入棧和出棧函數(shù)，具體實現(xiàn)依順序棧或鏈棧的不同而不同基本操作有入棧、出棧、讀棧頂元素值、建棧、判斷棧滿、?？盏?.實現(xiàn)方式

2023年4月15日

北京林業(yè)大學信息學院棧是一種特殊的線性表，它只能在表的一端（棧頂）進行插入和刪除運算棧與一般線性表的區(qū)別：僅在于運算規(guī)則不同“進”＝壓入=PUSH（)“出”＝彈出=POP()一般線性表

邏輯結構：一對一存儲結構：順序表、鏈表運算規(guī)則：隨機、順序存取棧邏輯結構：一對一存儲結構：順序棧、鏈棧運算規(guī)則：后進先出棧與一般線性表的區(qū)別

2023年4月15日

北京林業(yè)大學信息學院“進”＝壓入=PUSH（)“出”＝彈出=POP()

2023年4月15日

北京林業(yè)大學信息學院a1a2……an順序棧Sai……表頭表尾棧底base棧頂top低地址高地址寫入：v[i]=ai讀出：x=v[i]壓入：PUSH(an+1)彈出：POP(x)前提：一定要預設棧頂指針top！低地址高地址v[i]a1a2

aian

……順序表V[n]

……an+1順序棧與順序表

2023年4月15日

北京林業(yè)大學信息學院順序棧的表示空棧base==top

是棧空標志stacksize=4topAbasebasetopABABCtopbasetopbaseABCDbasetop3120top指示真正的棧頂元素之上的下標地址棧滿時的處理方法：1、報錯,返回操作系統(tǒng)。2、分配更大的空間，作為棧的存儲空間,將原棧的內容移入新棧。

2023年4月15日

北京林業(yè)大學信息學院#defineMAXSIZE100typedefstruct{

SElemType*base; SElemType*top; intstacksize;}SqStack;順序棧的表示

2023年4月15日

北京林業(yè)大學信息學院構造一個空棧步驟：(1)分配空間并檢查空間是否分配失敗，若失敗則返回錯誤順序棧初始化basestacksizetops(2)設置棧底和棧頂指針

S.top=S.base;(3)設置棧大小

2023年4月15日

北京林業(yè)大學信息學院StatusInitStack(SqStack&S){

S.base=newSElemType[MAXSIZE]；

if(!S.base) returnOVERFLOW;

S.top=S.base; S.stackSize=MAXSIZE; returnOK;}順序棧初始化

2023年4月15日

北京林業(yè)大學信息學院判斷順序棧是否為空boolStackEmpty(SqStackS){ if(S.top==S.base)returntrue;elsereturnfalse;}basetop3120

2023年4月15日

北京林業(yè)大學信息學院求順序棧的長度intStackLength(SqStackS){ returnS.top–S.base;}basetopAB

2023年4月15日

北京林業(yè)大學信息學院StatusClearStack(SqStackS){ if(S.base)S.top=S.base; returnOK;}清空順序棧basetop3120

2023年4月15日

北京林業(yè)大學信息學院StatusDestroyStack(SqStack&S){ if(S.base) { deleteS.base;

S.stacksize=0; S.base=S.top=NULL; }returnOK;}銷毀順序棧

2023年4月15日

北京林業(yè)大學信息學院(1)判斷是否棧滿，若滿則出錯(2)元素e壓入棧頂(3)棧頂指針加1順序棧進棧StatusPush(SqStack&S,SElemTypee){ if(S.top-S.base==S.stacksize)//棧滿

returnERROR;

*S.top++=e; returnOK;}*S.top=e;S.top++;ABCtopbase

2023年4月15日

北京林業(yè)大學信息學院(1)判斷是否棧空，若空則出錯(2)獲取棧頂元素e(3)棧頂指針減1順序棧出棧StatusPop(SqStack&S,SElemType&e){ if(S.top==S.base)//棧空

returnERROR;

e＝*--S.top; returnOK;}--S.top;e=*S.top;ABCtopbase

2023年4月15日

北京林業(yè)大學信息學院判斷是否空棧，若空則返回錯誤否則通過棧頂指針獲取棧頂元素取順序棧棧頂元素StatusGetTop(SqStackS,SElemType&e){ if(S.top==S.base) returnERROR; //?？?/p>

e=*(S.top–1); returnOK;}

e=*(S.top--);???ABCtopbase

2023年4月15日

北京林業(yè)大學信息學院435612中到了12順序不能實現(xiàn)；135426可以實現(xiàn)。1.如果一個棧的輸入序列為123456，能否得到435612和135426的出棧序列？練習

2023年4月15日

北京林業(yè)大學信息學院練習Ａ．iＢ．n-iＣ．n-i+1Ｄ．不確定Ｃ2.若已知一個棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，若p1=n，則pi為

2023年4月15日

北京林業(yè)大學信息學院練習Ａ．top不變Ｂ．top=0Ｃ．top++

Ｄ．top--D3.在一個具有n個單元的順序棧中，假設以地址高端作為棧底，以top作為棧頂指針，則當作進棧處理時，top的變化為

2023年4月15日

北京林業(yè)大學信息學院考研試題b[0]t[0]t[1]b[1]0m-1V雙棧共享一個?？臻g優(yōu)點：互相調劑，靈活性強，減少溢出機會

2023年4月15日

北京林業(yè)大學信息學院將編號為0和1的兩個棧存放于一個數(shù)組空間V[m]中，棧底分別處于數(shù)組的兩端。當?shù)?號棧的棧頂指針top[0]等于-1時該棧為空，當?shù)?號棧的棧頂指針top[1]等于m時該棧為空。兩個棧均從兩端向中間增長（如下圖所示）?？佳性囶}bot[0]top[0]top[1]bot[1]0m-1V

2023年4月15日

北京林業(yè)大學信息學院typedefstruct{ inttop[2],bot[2];//棧頂和棧底指針

SElemType*V;//棧數(shù)組

intm;//棧最大可容納元素個數(shù)}DblStack;數(shù)據(jù)結構定義如下考研試題

2023年4月15日

北京林業(yè)大學信息學院voidDblpush(DblStack&s,SElemTypex,inti)；//把x插入到棧i的棧intDblpop(DblStack&s,inti,SElemType&x)；

//退掉位于棧i棧頂?shù)脑豬ntIsEmpty(DblStacks,inti)

；//判棧i空否,空返回1,否則返回0intIsFull(DblStacks)

；//判棧滿否,滿返回1,否則返回0試編寫判斷棧空、棧滿、進棧和出棧四個算法的函數(shù)(函數(shù)定義方式如下）考研試題

2023年4月15日

北京林業(yè)大學信息學院b[0]t[0]t[1]b[1]0m-1V?？眨簍op[i]==bot[i]i表示棧的編號棧滿：top[0]+1==top[1]或top[1]-1==top[0]提示

2023年4月15日

北京林業(yè)大學信息學院鏈棧的表示運算是受限的單鏈表，只能在鏈表頭部進行操作，故沒有必要附加頭結點。棧頂指針就是鏈表的頭指針

typedefstructStackNode{SElemTypedata;structStackNode*next;}StackNode,*LinkStack;LinkStackS;

datanext棧頂棧底∧S

2023年4月15日

北京林業(yè)大學信息學院鏈棧的初始化voidInitStack(LinkStack&S){

S=NULL;}∧S

2023年4月15日

北京林業(yè)大學信息學院判斷鏈棧是否為空StatusStackEmpty(LinkStackS)

{

if(S==NULL)returnTRUE;

elsereturn

FALSE;

}

2023年4月15日

北京林業(yè)大學信息學院鏈棧進棧StatusPush(LinkStack&S,SElemTypee)

{

p=newStackNode;//生成新結點p

if(!p)exit(OVERFLOW);

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

returnOK;}p∧S

2023年4月15日

北京林業(yè)大學信息學院鏈棧進棧p∧SeStatusPush(LinkStack&S,SElemTypee)

{

p=newStackNode;//生成新結點p

if(!p)exit(OVERFLOW);

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

returnOK;}

2023年4月15日

北京林業(yè)大學信息學院鏈棧進棧p∧SeStatusPush(LinkStack&S,SElemTypee)

{

p=newStackNode;//生成新結點p

if(!p)exit(OVERFLOW);

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

returnOK;}

2023年4月15日

北京林業(yè)大學信息學院鏈棧進棧p∧SeSStatusPush(LinkStack&S,SElemTypee)

{

p=newStackNode;//生成新結點p

if(!p)exit(OVERFLOW);

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

returnOK;}

2023年4月15日

北京林業(yè)大學信息學院鏈棧出?！腟Ae=‘A’StatusPop(LinkStack&S,SElemType&e){if(S==NULL)returnERROR;

e=S->data;p=S;S=S->next;deletep;returnOK;}

2023年4月15日

北京林業(yè)大學信息學院鏈棧出?！腟Ae=‘A’pStatusPop(LinkStack&S,SElemType&e){if(S==NULL)returnERROR;

e=S->data;p=S;S=S->next;deletep;returnOK;}

2023年4月15日

北京林業(yè)大學信息學院鏈棧出?！腟Ae=‘A’pSStatusPop(LinkStack&S,SElemType&e){if(S==NULL)returnERROR;

e=S->data;p=S;S=S->next;deletep;returnOK;}

2023年4月15日

北京林業(yè)大學信息學院鏈棧出棧StatusPop(LinkStack&S,SElemType&e){if(S==NULL)returnERROR;

e=S->data;p=S;S=S->next;deletep;returnOK;}∧e=‘A’S

2023年4月15日

北京林業(yè)大學信息學院取鏈棧棧頂元素SElemTypeGetTop(LinkStackS){

if(S==NULL)

exit(1)；

elsereturnS–>data;}

2023年4月15日

北京林業(yè)大學信息學院3.2棧的應用例1：數(shù)制轉換（十轉N）用棧暫存低位值例2：括號匹配的檢驗用棧暫存左括號例3：表達式求值用棧暫存運算符例4：迷宮求解用棧實現(xiàn)遞歸調用簡化了程序設計的問題

2023年4月15日

北京林業(yè)大學信息學院迷宮求解

2023年4月15日

北京林業(yè)大學信息學院從入口出發(fā)，按某一方向向未走過的前方探索若能走通，則到達新點，否則試探下一方向;若所有的方向均沒有通路，則沿原路返回前一點，換下一個方向再繼續(xù)試探直到所有可能的通路都探索到，或找到一條通路，或無路可走又返回到入口點。求解思想：回溯法迷宮求解

2023年4月15日

北京林業(yè)大學信息學院需要解決的問題：1、表示迷宮的數(shù)據(jù)結構2、試探方向3、棧的設計4、防止重復到達某點，避免發(fā)生死循環(huán)迷宮求解

2023年4月15日

北京林業(yè)大學信息學院1、表示迷宮的數(shù)據(jù)結構表示一個m行n列迷宮：用maze[m][n]表示，0≤i<m,0≤j<nmaze[i][j]=0通路maze[i][j]=1不通改進：用maze[m+2][n+2]表示且maze[i][j]=1，i=0或m＋1,j=0或n＋1入口坐標為（1，1），出口坐標為（m，n）

迷宮求解

2023年4月15日

北京林業(yè)大學信息學院012345678901111111111110010001012100100010131000011001410111000015100010000161010001001710111011018110001000191111111111

2023年4月15日

北京林業(yè)大學信息學院迷宮的定義：#definem8

/*迷宮的實際行*/#definen8

/*迷宮的實際列*/intmaze[m+2][n+2];2、試探方向表示位置的類型PosType定義如下：typedefstruct{ intx，y;}PosType;迷宮求解

2023年4月15日

北京林業(yè)大學信息學院試探順序規(guī)定為：從正東沿順時針方向與點(x，y)相鄰的4個點及坐標(x,y)(x,y+1)(x,y-1)(x+1,y)(x-1,y)迷宮求解

2023年4月15日

北京林業(yè)大學信息學院3、棧的設計棧中每個元素的組成：通道塊在路徑上的序號坐標位置前進方向（東為1，南為2，西為3，北為4）棧元素的類型定義：typedefstruct{intord;PosTypeseat;intdi;}SElemType;迷宮求解

2023年4月15日

北京林業(yè)大學信息學院4、防止重復到達某點走過不通之處要加以標記（MarkPrint操作）迷宮求解算法思想及算法參見P51迷宮求解

2023年4月15日

北京林業(yè)大學信息學院表達式求值算術四則運算規(guī)則(1)先乘除,后加減(2)從左算到右(3)先括號內,后括號外

2023年4月15日

北京林業(yè)大學信息學院表達式常數(shù)標識符操作數(shù)(operand)運算符(operator)界限符(delimiter)算術邏輯關系括號結束符

2023年4月15日

北京林業(yè)大學信息學院>><<<>>>><<<>>>>>><>>>>>><>><<<<<=>>>>x>><<<<<=xx表3.1算符間的優(yōu)先關系

2023年4月15日

北京林業(yè)大學信息學院【算法思想】（1）初始化OPTR棧和OPND棧，將“#”壓入OPTR（2）依次讀入字符ch，循環(huán)執(zhí)行（3）至（5）（3）取出OPTR的棧頂元素，當OPTR的棧頂元素和ch均為“#”時，表達式求值完畢，OPND棧頂元素為表達式的值設定兩棧：OPND-----操作數(shù)或運算結果OPTR------運算符（4）if(ch是操作數(shù))則ch進OPND，讀入下一字符ch（5）else比較OPTR棧頂元素和ch的優(yōu)先級case‘<’:運算符ch進OPTR，讀入下一字符chcase‘=’:脫括號（彈出左括號），讀入下一字符chcase‘<’:棧頂運算符退棧、計算，結果進OPND

2023年4月15日

北京林業(yè)大學信息學院OperandTypeEvaluateExpression(){InitStack(OPND);ch=getchar();while(ch!='#'||GetTop(OPTR)!='#'){if(!In(ch,OP)){Push(OPND,ch);ch=getchar();}//ch不是運算符則進棧

elseswitch(Precede(GetTop(OPTR),ch)){//比較優(yōu)先權

case'<'://當前字符ch壓入OPTR棧，讀入下一字符chPush(OPTR,ch);ch=getchar();break;case'>'://彈出OPTR棧頂?shù)倪\算符運算，并將運算結果入棧

Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b));break;case'='://脫括號并接收下一字符

Pop(OPTR,x);ch=getchar();break;}//switch}//whilereturnGetTop(OPND);}//EvaluateExpression

2023年4月15日

北京林業(yè)大學信息學院OPTROPNDINPUTOPERATE3*(7-2)#Push(opnd,’3’)

#*(7-2)#3#Push(optr,’*’)#,*3(7-2)#Push(optr,’(’)#,*,(37-2)#Push(opnd,’7’)#,*,(3,7-2)#Push(optr,’-’)#,*,(,－3,72)#Push(opnd,’2’)#,*,(,－3,7,2)#Operate(7-2)#,*,(3,5)#Pop(optr)#,*3,5#Operate(3*5)#15#GetTop(opnd)

2023年4月15日

北京林業(yè)大學信息學院3.3棧與遞歸遞歸的定義若一個對象部分地包含它自己,或用它自己給自己定義,則稱這個對象是遞歸的；若一個過程直接地或間接地調用自己,則稱這個過程是遞歸的過程。

2023年4月15日

北京林業(yè)大學信息學院當多個函數(shù)構成嵌套調用時,遵循后調用先返回棧

2023年4月15日

北京林業(yè)大學信息學院以下三種情況常常用到遞歸方法遞歸定義的數(shù)學函數(shù)具有遞歸特性的數(shù)據(jù)結構可遞歸求解的問題

2023年4月15日

北京林業(yè)大學信息學院1.遞歸定義的數(shù)學函數(shù):階乘函數(shù):

2階Fibonaci數(shù)列:

2023年4月15日

北京林業(yè)大學信息學院樹

2.具有遞歸特性的數(shù)據(jù)結構:RootLchildRchild廣義表

A=(a,A)3.可遞歸求解的問題:迷宮問題Hanoi塔問題

2023年4月15日

北京林業(yè)大學信息學院分治法：對于一個較為復雜的問題，能夠分解成幾個相對簡單的且解法相同或類似的子問題來求解1、能將一個問題轉變成一個新問題，而新問題與原問題的解法相同或類同，不同的僅是處理的對象，且這些處理對象是變化有規(guī)律的2、可以通過上述轉化而使問題簡化3、必須有一個明確的遞歸出口，或稱遞歸的邊界用分治法求解遞歸問題必備的三個條件

2023年4月15日

北京林業(yè)大學信息學院分治法求解遞歸問題算法的一般形式：

voidp(參數(shù)表){if（遞歸結束條件）可直接求解步驟；-----基本項

elsep（較小的參數(shù)）；------歸納項

}longFact(longn){if(n==0)return1;//基本項

elsereturnn*Fact(n-1);//歸納項}

2023年4月15日

北京林業(yè)大學信息學院返回2

參數(shù)2計算2*Fact(1)返回1

參數(shù)1計算1*Fact(0)返回1

參數(shù)0直接定值=1參數(shù)傳遞遞歸調用結果返回回歸求值if(n==0)return1;elsereturnn*Fact(n-1);求解階乘n!的過程主程序

main:Fact(4)返回24參數(shù)4計算4*Fact(3)返回6

參數(shù)3計算3*Fact(2)

2023年4月15日

北京林業(yè)大學信息學院設有一個遞歸算法如下:intX(intn){if(n<=3)return1;elsereturnX(n-2)+X(n-4)+1}則計算X(X(8))時需要計算X函數(shù)

次.D練習A.8 B.9C.16 D.18

2023年4月15日

北京林業(yè)大學信息學院在印度圣廟里，一塊黃銅板上插著三根寶石針。主神梵天在創(chuàng)造世界時，在其中一根針上穿好了由大到小的64片金片，這就是漢諾塔。僧侶不停移動這些金片，一次只移動一片，小片必在大片上面。當所有的金片都移到另外一個針上時，世界將會滅亡。

漢諾塔

2023年4月15日

北京林業(yè)大學信息學院規(guī)則:(1)每次只能移動一個圓盤(2)圓盤可以插在A,B和C中的任一塔座上(3)任何時刻不可將較大圓盤壓在較小圓盤之上Hanoi塔問題ABC

2023年4月15日

北京林業(yè)大學信息學院Hanoi塔問題

n=1，則直接從A移到C。否則(1)用

C柱做過渡，將

A的(n-1)個移到

B(2)將

A最后一個直接移到

C(3)用

A做過渡，將

B的

(n-1)個移到

C

2023年4月15日

北京林業(yè)大學信息學院#include<iostream.h>intc=0;voidmove(charx,intn,charz){cout<<++c<<","<<n<<","<<x<<","<<z<<endl;}voidHanoi(intn,charA,charB,charC){if(n==1)move(A,1,C);else{Hanoi(n-1,A,C,B);move(A,n,C);Hanoi(n-1,B,A,C);}}voidmain(){Hanoi(3,'a','b','c');}跟蹤程序，給出下列程序的運行結果，以深刻地理解遞歸的調用和返回過程

2023年4月15日

北京林業(yè)大學信息學院3,a,b,c遞歸調用樹2,a,c,b2,b,a,ca-3->c

2023年4月15日

北京林業(yè)大學信息學院調用前,系統(tǒng)完成:(1)將實參,返回地址等傳遞給被調用函數(shù)(2)為被調用函數(shù)的局部變量分配存儲區(qū)(3)將控制轉移到被調用函數(shù)的入口調用后,系統(tǒng)完成:(1)保存被調用函數(shù)的計算結果(2)釋放被調用函數(shù)的數(shù)據(jù)區(qū)(3)依照被調用函數(shù)保存的返回地址將控制轉移到調用函數(shù)函數(shù)調用過程

2023年4月15日

北京林業(yè)大學信息學院“層次”主函數(shù)第1次調用第i次調用0層1層i層“遞歸工作棧”“工作記錄”實在參數(shù),局部變量,返回地址遞歸函數(shù)調用的實現(xiàn)

2023年4月15日

北京林業(yè)大學信息學院程序的具體執(zhí)行過程參見：“Hanoi塔執(zhí)行過程.ppt”

2023年4月15日

北京林業(yè)大學信息學院空間效率時間效率O(2n)與遞歸樹的結點數(shù)成正比與遞歸樹的深度成正比O(n)遞歸算法的效率分析

2023年4月15日

北京林業(yè)大學信息學院1234f(1)=1f(1)+1+f(1)=3f(2)+1+f(2)=7f(3)+1+f(3)=15f(n)=2f(n-1)+1f(n-1)=2f(n-2)+1f(n-2)=2f(n-3)+1......f(3)=2f(2)+1f(2)=2f(1)+120f(n)=21f(n-1)+2021f(n-1)=22f(n-2)+2122f(n-2)=23f(n-3)+22......2n-3f(3)=2n-2f(2)+2n-32n-2f(2)=2n-1f(1)+2n-2f(n)=20+21+…+2n-2+2n-1f(1)=2n-1遞歸算法的效率分析

2023年4月15日

北京林業(yè)大學信息學院64片金片移動次數(shù)：264-1=15假如每秒鐘一次，共需多長時間呢？一年大約有31536926秒，移完這些金片需要５８００多億年世界、梵塔、廟宇和眾生都已經灰飛煙滅

……!

2023年4月15日

北京林業(yè)大學信息學院優(yōu)點：結構清晰，程序易讀缺點：每次調用要生成工作記錄，保存狀態(tài)信息，入棧；返回時要出棧，恢復狀態(tài)信息。時間開銷大。遞歸的優(yōu)缺點遞歸非遞歸

2023年4月15日

北京林業(yè)大學信息學院3.4隊列

隊列是一種先進先出(FIFO)的線性表.它只允許在表的一端進行插入,而在另一端刪除元素a1a2a3an...入隊列隊頭隊尾

2023年4月15日

北京林業(yè)大學信息學院a1a2a3an...隊頭隊尾出隊列

2023年4月15日

北京林業(yè)大學信息學院a1a2a3an...隊頭隊尾出隊列

2023年4月15日

北京林業(yè)大學信息學院a1a2a3an...隊頭隊尾出隊列

2023年4月15日

北京林業(yè)大學信息學院設棧S和隊列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5和e6依次通過S，一個元素出棧后即進入Q，若6個元素出隊的序列是e2、e4、e3、e6、e5和e1，則棧S的容量至少應該是（）。（A）2（B）3（C）4（D）6練習B

2023年4月15日

北京林業(yè)大學信息學院數(shù)據(jù)對象:數(shù)據(jù)關系:基本操作:

(1)

InitQueue(&Q)//構造空隊列

(2)DestroyQueue(&Q)//銷毀隊列

(3)ClearQueue(&S)//清空隊列

(4)QueueEmpty(S)//判空.空--TRUE,ADTQueue{隊列的抽象數(shù)據(jù)類型

2023年4月15日

北京林業(yè)大學信息學院(5)QueueLength(Q)//取隊列長度

(6)GetHead(Q,&e)//取隊頭元素,(7)EnQueue(&Q,e)//入隊列

(8)DeQueue(&Q,&e)//出隊列

(9)QueueTraverse(Q,visit())//遍歷}ADTQueue隊列的抽象數(shù)據(jù)類型

2023年4月15日

北京林業(yè)大學信息學院#defineM100//最大隊列長度Typedefstruct{QElemType*base;//初始化的動態(tài)分配存儲空間

intfront;//頭指針

intrear;//尾指針}SqQueue;

隊列的順序表示－－用一維數(shù)組base[M]

2023年4月15日

北京林業(yè)大學信息學院隊列的順序表示－－用一維數(shù)組base[M]Q.front012345Q.rearQ.frontQ.rearJ1J2J3Q.frontQ.rearJ3Q.frontQ.rearJ5J6front=rear=0空隊標志：front==rear入隊：base[rear++]=x;出隊：x=base[front++];

2023年4月15日

北京林業(yè)大學信息學院Q.frontQ.rearJ5J6Q.front012345Q.rearJ5J6J1J2J3J4存在的問題設數(shù)組大小為Mfront=0rear=M時再入隊——真溢出front0rear=M時再入隊——假溢出

2023年4月15日

北京林業(yè)大學信息學院解決的方法－－循環(huán)隊列10Q.rearQ.front......base[0]接在base[M-1]之后若rear+1==M則令rear=0;實現(xiàn)：利用“模”運算入隊：

base[rear]=x;rear=(rear+1)%M;出隊：

x=base[front];front=(front+1)%M;

2023年4月15日

北京林業(yè)大學信息學院J4J5J6012345rearfrontJ9J8J7J7,J8,J9入隊隊空：front==rear隊滿：front==rear解決方案：1.另外設一個標志以區(qū)別隊空、隊滿2.少用一個元素空間：隊空：front==rear

隊滿：(rear+1)%M==frontJ4J5J6012345rearfront012345frontJ4,J5,J6出隊rear

2023年4月15日

北京林業(yè)大學信息學院循環(huán)隊列#defineMAXQSIZE100//最大隊列長度Typedefstruct{QElemType*base;//初始化的動態(tài)分配存儲空間

intfront;//頭指針

intrear;//尾指針}SqQueue;

2023年4月15日

北京林業(yè)大學信息學院StatusInitQueue(SqQueue&Q){

Q.base=newQElemType[MAXQSIZE]

if(!Q.base)exit(OVERFLOW);

Q.front=Q.rear=0;returnOK;}循環(huán)隊列初始化

2023年4月15日

北京林業(yè)大學信息學院求循環(huán)隊列的長度intQueueLength(SqQueueQ){

return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;

}

2023年4月15日

北京林業(yè)大學信息學院StatusEnQueue(SqQueue&Q,QElemTypee){if((Q.rear+1)%MAXQSIZE==Q.front)returnERROR;

Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;returnOK;}循環(huán)隊列入隊

2023年4月15日

北京林業(yè)大學信息學院StatusDeQueue(LinkQueue&Q,QElemType&e){if(Q.front==Q.rear)returnERROR;

e=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;returnOK;}循環(huán)隊列出隊

2023年4月15日

北京林業(yè)大學信息學院...datanext隊頭隊尾Q.frontQ.rear鏈隊列

2023年4月15日

北京林業(yè)大學信息學院typedefstructQNode{QElemTypedata;structQnode*next;}Qnode,*QueuePtr;typedefstruct{QueuePtrfront;//隊頭指針

QueuePtrrear;//隊尾指針}LinkQueue;

鏈隊列

2023年4月15日

北京林業(yè)大學信息學院(a)空隊列(b)元素x入隊列(d)元素x出隊列(c)元素y入隊列鏈隊列

2023年4月15日

北京林業(yè)大學信息學院StatusInitQueue(LinkQueue&Q){

Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);

Q.front->next=NULL;returnOK;}鏈隊列初始化

2023年4月15日

北京林業(yè)大學信息學院StatusDestroyQueue(LinkQueue&Q){while(Q.front){

Q.rear=Q.front->next;free(Q.front);Q.front=Q.rear;}returnOK;}銷毀鏈隊列

2023年4月15日

北京林業(yè)大學信息學院StatusQueueEmpty(LinkQueueQ){return(Q.front==Q.rear);}判斷鏈隊列是否為空

2023年4月15日

北京林業(yè)大學信息學院StatusGetHead(LinkQueueQ,QElemType&e){if(Q.front==Q.rear)returnERROR;

e=Q.front->next->data;returnOK;}求鏈隊列的隊頭元素

2023年4月15日

北京林業(yè)大學信息學院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;}鏈隊列入隊p

2023年4月15日

北京林業(yè)大學信息學院StatusDeQueue(LinkQueue&Q,QElemType&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;}鏈隊列出隊p

2023年4月15日

北京林業(yè)大學信息學院【例】汽車加油站

隨著城市里汽車數(shù)量的急速增長，汽車加油站也漸漸多了起來。通常汽車加油站的結構基本上是：入口和出口為單行道，加油車道可能有若干條。每輛車加油都要經過三段路程，第一段是在入口處排隊等候進入加油車道；第二段是在加油車道排隊等候加油；第三段是進入出口處排隊等候離開。實際上，這三段都是隊列結構。若用算法模擬這個過程，就需要設置加油車道數(shù)加2個隊列。3.5隊列的應用

2023年4月15日

北京林業(yè)大學信息學院【例】模擬打印機緩沖區(qū)

在主機將數(shù)據(jù)輸出到打印機時，會出現(xiàn)主機速度與打印機的打印速度不匹配的問題。這時主機就要停下來等待打印機。顯然，這樣會降低主機的使用效率。為此人們設想了一種辦法：為打印機設置一個打印數(shù)據(jù)緩沖區(qū)，當主機需要打印數(shù)據(jù)時，先將數(shù)據(jù)依次寫入這個緩沖區(qū)，寫滿后主機轉去做其他的事情，而打印機就從緩沖區(qū)中按照先進先出的原則依次讀取數(shù)據(jù)并打印，這樣做即保證了打印數(shù)據(jù)的正確性，又提高了主機的使用效率。由此可見，打印機緩沖區(qū)實際上就是一個