數(shù)據(jù)結(jié)構(gòu)第六次課-棧和隊(duì)列B

每課一貼：原來(lái)很簡(jiǎn)單

有一個(gè)人去應(yīng)征工作，隨手將走廊上的紙屑撿起來(lái)，放進(jìn)了垃圾桶，被路過(guò)的口試官看到了，因此他得到了這份工作。原來(lái)獲得賞識(shí)很簡(jiǎn)單，養(yǎng)成好習(xí)慣就可以了。

住在田邊的青蛙對(duì)住在路邊的青蛙說(shuō)：「你這里太危險(xiǎn)，搬來(lái)跟我住吧！路邊的青蛙說(shuō)：「我已經(jīng)習(xí)慣了，懶得搬了?！箮滋旌螅镞叺那嗤苋ヌ酵愤叺那嗤埽瑓s發(fā)現(xiàn)他已被車(chē)子壓死，暴尸在馬路。原來(lái)掌握命運(yùn)的方法很簡(jiǎn)單，遠(yuǎn)離懶惰就可以了。1數(shù)據(jù)結(jié)構(gòu)第六次課-棧和隊(duì)列B共34頁(yè)，您現(xiàn)在瀏覽的是第1頁(yè)!2.邏輯結(jié)構(gòu)與同線(xiàn)性表相同，仍為一對(duì)一關(guān)系。3.運(yùn)算規(guī)則只能在棧頂運(yùn)算，且訪(fǎng)問(wèn)結(jié)點(diǎn)時(shí)依照后進(jìn)先出（LIFO）或先進(jìn)后出（FILO）的原則。4.出棧順序：定義限定只能在表的一端進(jìn)行插入和刪除運(yùn)算的線(xiàn)性表（只能在棧頂操作）上次課內(nèi)容回顧2數(shù)據(jù)結(jié)構(gòu)第六次課-棧和隊(duì)列B共34頁(yè)，您現(xiàn)在瀏覽的是第2頁(yè)!討論：有無(wú)通用的判別原則？有。在可能的輸出序列中，不存在這樣的輸入序列i，j，k，能同時(shí)滿(mǎn)足入棧順序i，j，k和出棧順序k，i，j。例4一個(gè)棧的輸入序列為12345，若在入棧的過(guò)程中允許出棧，則可能得到的出棧序列有多少種，分別是什么？3數(shù)據(jù)結(jié)構(gòu)第六次課-棧和隊(duì)列B共34頁(yè)，您現(xiàn)在瀏覽的是第3頁(yè)!回文游戲：順讀與逆讀字符串一樣（不含空格）dadtop1.讀入字符串2.壓入棧3.原串字符與出棧字符依次比較若不等，非回文若直到?？斩枷嗟?，則是回文有沒(méi)有更簡(jiǎn)潔的辦法呢？(讀入字符串，壓入n/2個(gè)字符,n為字符個(gè)數(shù))多進(jìn)制輸出：字符串：“madamImadam”“上海自來(lái)水來(lái)自海上”例把十進(jìn)制數(shù)159轉(zhuǎn)換成八進(jìn)制數(shù)(159)10=(237)81598198280237余7余3余2toptop7top73top7324數(shù)據(jù)結(jié)構(gòu)第六次課-棧和隊(duì)列B共34頁(yè)，您現(xiàn)在瀏覽的是第4頁(yè)!多進(jìn)制輸出：importjava.util.*;classT{publicstaticvoidmain(String[]args){System.out.println(toOctal(159));}publicstaticStringtoOctal(inta){Stringstr="";Stacks=newStack();while(a!=0){s.push(a%8);a=a/8;}while(!s.empty()){str+=s.pop();}returnstr;}}例把十進(jìn)制數(shù)159轉(zhuǎn)換成八進(jìn)制數(shù)5數(shù)據(jù)結(jié)構(gòu)第六次課-棧和隊(duì)列B共34頁(yè)，您現(xiàn)在瀏覽的是第5頁(yè)!表達(dá)式表示法算術(shù)表達(dá)式中最常見(jiàn)的表示法形式有中綴、前綴和后綴表示法。中綴表示法是書(shū)寫(xiě)表達(dá)式的常見(jiàn)方式，而前綴和后綴表示法主要用于計(jì)算機(jī)科學(xué)領(lǐng)域。中綴表示法Syntax:operand1operatoroperand2Example:(A+B)*C-D/(E+F)前綴表示法-波蘭表示法（Polishnotation，PN）Syntax:operatoroperand1operand2Example:-*+ABC/D+EF后綴表示法-逆波蘭表示法（ReversePolishNotation，RPN）Syntax:operand1operand2operatorExample:AB+C*DEF+/-無(wú)操作符優(yōu)先級(jí)問(wèn)題，求值簡(jiǎn)單6數(shù)據(jù)結(jié)構(gòu)第六次課-棧和隊(duì)列B共34頁(yè)，您現(xiàn)在瀏覽的是第6頁(yè)!轉(zhuǎn)換算法：1.讀入運(yùn)算對(duì)象（數(shù)據(jù)），直接輸出2.遇到‘(’運(yùn)算符進(jìn)棧3.遇到‘)’運(yùn)算符，則棧內(nèi)的最上一個(gè)‘(’以上的所有運(yùn)算符退棧，‘(’也退棧4.讀入運(yùn)算符，進(jìn)入運(yùn)算棧4.1后進(jìn)棧的運(yùn)算符>先進(jìn)棧的運(yùn)算符，運(yùn)算符進(jìn)棧(優(yōu)先級(jí)比較)4.2后進(jìn)棧的運(yùn)算符<=先進(jìn)棧的運(yùn)算符，將棧內(nèi)的運(yùn)算符退棧輸出，再進(jìn)棧7數(shù)據(jù)結(jié)構(gòu)第六次課-棧和隊(duì)列B共34頁(yè)，您現(xiàn)在瀏覽的是第7頁(yè)!后綴表達(dá)式求值對(duì)后綴表達(dá)式求值比直接對(duì)中綴表達(dá)式求值簡(jiǎn)單。在后綴表達(dá)式中，不需要括號(hào)，而且操作符的優(yōu)先級(jí)也不再起作用了?？梢杂萌缦滤惴▽?duì)后綴表達(dá)式求值：初始化一個(gè)空堆棧從左到右讀入后綴表達(dá)式如果字符是一個(gè)操作數(shù)，把它壓入堆棧。如果字符是個(gè)操作符，彈出兩個(gè)操作數(shù)，執(zhí)行操作，然后把結(jié)果壓入堆棧。到后綴表達(dá)式末尾，從堆棧中彈出結(jié)果。若后綴表達(dá)式格式正確，那么堆棧應(yīng)該為空。8數(shù)據(jù)結(jié)構(gòu)第六次課-棧和隊(duì)列B共34頁(yè)，您現(xiàn)在瀏覽的是第8頁(yè)!1.順序棧的一般定義//堆棧接口publicinterfaceStack{publicintgetSize();publicbooleanisEmpty();publicvoidpush(Objecte);publicObjectpop()throwsStackEmptyException;publicObjectpeek()throwsStackEmptyException;}二.基本操作的程序?qū)崿F(xiàn)9數(shù)據(jù)結(jié)構(gòu)第六次課-棧和隊(duì)列B共34頁(yè)，您現(xiàn)在瀏覽的是第9頁(yè)!

privatevoidexpandSpace(){Object[]a=newObject[elements.length*2];for(inti=0;i<elements.length;i++)a[i]=elements[i];elements=a;}publicObjectpop()throwsStackEmptyException{if(getSize()<1)thrownewStackEmptyException(“錯(cuò)誤，堆?？铡?;Objectobj=elements[top];elements[top--]=null;returnobj;}publicObjectpeek()throwsStackEmptyException{if(getSize()<1)thrownewStackEmptyException(“錯(cuò)誤，堆?？铡?;returnelements[top];}}10數(shù)據(jù)結(jié)構(gòu)第六次課-棧和隊(duì)列B共34頁(yè)，您現(xiàn)在瀏覽的是第10頁(yè)!補(bǔ)充1：若入棧動(dòng)作使地址向高端增長(zhǎng)，稱(chēng)為“向上生成”的棧；若入棧動(dòng)作使地址向低端增長(zhǎng)，稱(chēng)為“向下生成”的棧；top=0123450?？?/p>

對(duì)于向上生成的棧入?？谠E：堆棧指針top先壓后加（v[top++]=x）；出?？谠E：堆棧指針top先減后彈（y=v[--top])

。

對(duì)于向下生成的棧若約定top指向棧頂元素的后一個(gè)位置入棧口訣：堆棧指針top先壓后減（v[top--]=x）；出?？谠E：堆棧指針top先加后彈（y=v[++top])

。top=6123450?？?1數(shù)據(jù)結(jié)構(gòu)第六次課-棧和隊(duì)列B共34頁(yè)，您現(xiàn)在瀏覽的是第11頁(yè)!3.2隊(duì)列隊(duì)列的定義及特點(diǎn)定義：隊(duì)列是限定只能在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線(xiàn)性表隊(duì)尾(rear)——允許插入的一端隊(duì)頭(front)——允許刪除的一端隊(duì)列特點(diǎn)：先進(jìn)先出(FIFO)a1a2a3…….an入隊(duì)出隊(duì)隊(duì)頭front隊(duì)尾rear隊(duì)列Q=(a1,a2,……,an)12數(shù)據(jù)結(jié)構(gòu)第六次課-棧和隊(duì)列B共34頁(yè)，您現(xiàn)在瀏覽的是第12頁(yè)!隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)：用一維數(shù)組實(shí)現(xiàn)sq[M]front=-1rear=-1123450隊(duì)空123450frontJ1,J1,J3入隊(duì)J1J2J3rearrear123450J4,J5,J6入隊(duì)J4J5J6front設(shè)兩個(gè)指針front,rear,約定：rear指示隊(duì)尾元素；front指示隊(duì)頭元素前一位置初值front=rear=-1

空隊(duì)列條件：front==rear入隊(duì)列：sq[++rear]=x;出隊(duì)列：x=sq[++front];rearrearfrontrear123450J1,J2,J3出隊(duì)J1J2J3frontfrontfront隊(duì)列會(huì)滿(mǎn)嗎？這樣操作有沒(méi)有問(wèn)題？13數(shù)據(jù)結(jié)構(gòu)第六次課-棧和隊(duì)列B共34頁(yè)，您現(xiàn)在瀏覽的是第13頁(yè)!012345rearfrontJ4J5J6012345rearfrontJ9J8J7J4J5J6012345rearfront初始狀態(tài)J4,J5,J6出隊(duì)J7,J8,J9入隊(duì)隊(duì)空：front==rear隊(duì)滿(mǎn)：front==rear真溢出假溢出14數(shù)據(jù)結(jié)構(gòu)第六次課-棧和隊(duì)列B共34頁(yè)，您現(xiàn)在瀏覽的是第14頁(yè)!J2J3 J1J4

J5rearfrontfrontfrontfrontJ6J5J7J8J9例1：一循環(huán)隊(duì)列如下圖所示，若先刪除4個(gè)元素，接著再插入4個(gè)元素，請(qǐng)問(wèn)隊(duì)頭和隊(duì)尾指針?lè)謩e指向哪個(gè)位置?front解：由圖可知，隊(duì)頭和隊(duì)尾指針的初態(tài)分別為front=1和rear=6。frontrear刪除4個(gè)元素后front=5；再插入4個(gè)元素后，r=(6+4)%6=4front入隊(duì)：rear=(rear+1)%M;出隊(duì)：front=(front+1)%M;15數(shù)據(jù)結(jié)構(gòu)第六次課-棧和隊(duì)列B共34頁(yè)，您現(xiàn)在瀏覽的是第15頁(yè)!基本運(yùn)算如下：⑴

置空隊(duì)

分配空間，頭尾指針賦值，計(jì)數(shù)賦0⑵

入隊(duì)

順序表插入，調(diào)整頭尾指針

計(jì)數(shù)賦＋＋⑶

出隊(duì)

順序表刪除，調(diào)整頭尾指針

計(jì)數(shù)賦――⑷

判隊(duì)空

隊(duì)列中數(shù)據(jù)數(shù)目為0。

③使用計(jì)數(shù)器的循環(huán)隊(duì)列的類(lèi)型定義：Java實(shí)現(xiàn)使用計(jì)數(shù)器的循環(huán)隊(duì)列.txt16數(shù)據(jù)結(jié)構(gòu)第六次課-棧和隊(duì)列B共34頁(yè)，您現(xiàn)在瀏覽的是第16頁(yè)!鏈隊(duì)列頭結(jié)點(diǎn)^…...front隊(duì)頭隊(duì)尾rear設(shè)隊(duì)首、隊(duì)尾指針front和rear,front指向頭結(jié)點(diǎn)，rear指向隊(duì)尾17數(shù)據(jù)結(jié)構(gòu)第六次課-棧和隊(duì)列B共34頁(yè)，您現(xiàn)在瀏覽的是第17頁(yè)!討論：空隊(duì)列的特征？Q(隊(duì)尾)(隊(duì)首)fronta1a2a3^rearpfront^rear③怎樣實(shí)現(xiàn)入隊(duì)和出隊(duì)操作？入隊(duì)（尾部插入）：出隊(duì)（頭部刪除）：P74入隊(duì)、出隊(duì)Java實(shí)現(xiàn)②隊(duì)列會(huì)滿(mǎn)嗎？front==rear一般不會(huì)，因?yàn)閯h除時(shí)有free動(dòng)作。除非內(nèi)存不足！18數(shù)據(jù)結(jié)構(gòu)第六次課-棧和隊(duì)列B共34頁(yè)，您現(xiàn)在瀏覽的是第18頁(yè)!例1：回文游戲

設(shè)計(jì)思路：用棧暫存回文例2：數(shù)制轉(zhuǎn)換（十轉(zhuǎn)N）

設(shè)計(jì)思路：用棧暫存低位值例3：括號(hào)匹配的檢驗(yàn)

設(shè)計(jì)思路：用棧暫存左括號(hào)例4：表達(dá)式求值

設(shè)計(jì)思路：用棧暫存運(yùn)算符簡(jiǎn)化程序設(shè)計(jì)問(wèn)題19數(shù)據(jù)結(jié)構(gòu)第六次課-棧和隊(duì)列B共34頁(yè)，您現(xiàn)在瀏覽的是第19頁(yè)!多進(jìn)制輸出：例把十進(jìn)制數(shù)159轉(zhuǎn)換成八進(jìn)制數(shù)(159)10=(237)81598198280237余7余3余2toptop7top73top732publicclassTest{publicstaticvoidmain(Stringargs[])

{ inti=159;

StringbinStr=Integer.toBinaryString(i);

StringotcStr=Integer.toOctalString(i);

StringhexStr=Integer.toHexString(i);

System.out.println(binStr); }}20數(shù)據(jù)結(jié)構(gòu)第六次課-棧和隊(duì)列B共34頁(yè)，您現(xiàn)在瀏覽的是第20頁(yè)!例如：3*（7–2）(1)要正確求值，首先了解算術(shù)四則運(yùn)算的規(guī)則：

a.從左算到右

b.

先乘除，后加減

c.

先括號(hào)內(nèi)，后括號(hào)外由此，通常此表達(dá)式的計(jì)算順序?yàn)椋?*（7–2）=3*5=15表達(dá)式求值(這是棧應(yīng)用的典型例子)這里，表達(dá)式求值的算法是“算符優(yōu)先法”。21數(shù)據(jù)結(jié)構(gòu)第六次課-棧和隊(duì)列B共34頁(yè)，您現(xiàn)在瀏覽的是第21頁(yè)!1.中綴表達(dá)式到后綴表達(dá)式的轉(zhuǎn)換

要把表達(dá)式從中綴表達(dá)式的形式轉(zhuǎn)換成用后綴表示法表示的等價(jià)表達(dá)式，必須了解操作符的優(yōu)先級(jí)和結(jié)合性。優(yōu)先級(jí)或者說(shuō)操作符的強(qiáng)度決定求值順序；優(yōu)先級(jí)高的操作符比優(yōu)先級(jí)低的操作符先求值。如果所有操作符優(yōu)先級(jí)一樣，那么求值順序就取決于它們的結(jié)合性。操作符的結(jié)合性定義了相同優(yōu)先級(jí)操作符組合的順序（從右至左或從左至右）。Leftassociativity:A+B+C=(A+B)+CRightassociativity:A^B^C=A^(B^C)常用表達(dá)式求值方法1.中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式2.計(jì)算后綴表達(dá)式22數(shù)據(jù)結(jié)構(gòu)第六次課-棧和隊(duì)列B共34頁(yè)，您現(xiàn)在瀏覽的是第22頁(yè)!31*(5-22)+7023數(shù)據(jù)結(jié)構(gòu)第六次課-棧和隊(duì)列B共34頁(yè)，您現(xiàn)在瀏覽的是第23頁(yè)!31*(5-22)+70參看Class1.java代碼24數(shù)據(jù)結(jié)構(gòu)第六次課-棧和隊(duì)列B共34頁(yè)，您現(xiàn)在瀏覽的是第24頁(yè)!1.順序棧的一般定義publicclassStackArrayimplementsStack{privatefinalintLEN=8;//privateObject[]elements;//privateinttop;publicStackArray(){top=-1;elements=newObject[LEN];}publicintgetSize(){returntop+1;}publicbooleanisEmpty(){returntop<0;}publicvoidpush(Objecte){if(getSize()>=elements.length)expandSpace();elements[++top]=e;}二.基本操作的程序?qū)崿F(xiàn)25數(shù)據(jù)結(jié)構(gòu)第六次課-棧和隊(duì)列B共34頁(yè)，您現(xiàn)在瀏覽的是第25頁(yè)!入棧算法出棧算法^…...棧底toptopxptop^…...棧底topq鏈?；静僮鱌67Stack的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)初始化、判斷?？?、棧滿(mǎn)、入棧、出棧、取棧頂元素、銷(xiāo)毀。SLNodep=newSLNode(x,top);top=p;size++;棧非空，則Objectobj=top.getData();top=top.getNext();size--;26數(shù)據(jù)結(jié)構(gòu)第六次課-棧和隊(duì)列B共34頁(yè)，您現(xiàn)在瀏覽的是第26頁(yè)!第三章棧和隊(duì)列3.2隊(duì)（Queue）

隊(duì)的基本理論定義、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、基本運(yùn)算規(guī)則、隊(duì)的應(yīng)用2.基本操作的程序?qū)崿F(xiàn)方法27數(shù)據(jù)結(jié)構(gòu)第六次課-棧和隊(duì)列B共34頁(yè)，您現(xiàn)在瀏覽的是第27頁(yè)!ADTQueue{

數(shù)據(jù)對(duì)象：D={ai|aiElemSet,i=1,2,…,n,n0}

數(shù)據(jù)關(guān)系：R1={<ai-1,ai>|ai-1,ai

D,i=2,…,n}

基本操作：getSize();//返回隊(duì)列大小，即元素個(gè)數(shù)isEmpty();//對(duì)為空返回true,否則返回falseenqueue(e);//數(shù)據(jù)元素e入對(duì)dequeue();//對(duì)頭元素出對(duì)peek();//獲取對(duì)頭元素，但不出對(duì)}//ADTQueue隊(duì)的抽象數(shù)據(jù)類(lèi)型定義28數(shù)據(jù)結(jié)構(gòu)第六次課-棧和隊(duì)列B共34頁(yè)，您現(xiàn)在瀏覽的是第28頁(yè)!存在問(wèn)題設(shè)數(shù)組容量為M，則：當(dāng)front=-1,rear=M-1時(shí)，再有元素入隊(duì)發(fā)生溢出——真溢出當(dāng)front-1,rear=M-1時(shí)，再有元素入隊(duì)發(fā)生溢出——假溢出0M-11frontrear…...…...解決方案隊(duì)首固定，每次出隊(duì)剩余元素向下移動(dòng)——浪費(fèi)時(shí)間循環(huán)隊(duì)列基本思想：把隊(duì)列設(shè)想成環(huán)形，讓sq[0]接在sq[M-1]之后，若rear+1==M,則令rear=0;在順序隊(duì)中，當(dāng)尾指針已經(jīng)到了數(shù)組的上界，不能再有入隊(duì)操作，但其實(shí)數(shù)組中還有空位置，這就叫“假溢出”。實(shí)現(xiàn)：利用“求模”運(yùn)算入隊(duì)：rear=(rear+1)%M;sq[rear]=x;出隊(duì)：front=(front+1)%M;x=sq[front];隊(duì)滿(mǎn)、隊(duì)空判定條件？29數(shù)據(jù)結(jié)構(gòu)第六次課-棧和隊(duì)列B共34頁(yè)，您現(xiàn)在瀏覽的是第29頁(yè)!解決方案有三：①加設(shè)標(biāo)志位，讓刪除動(dòng)作使其為1,插入動(dòng)作使其為0,則可識(shí)別當(dāng)前front=rear②人為浪費(fèi)一個(gè)單元，令隊(duì)滿(mǎn)特征為front=(rear+1)%N；③使用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素個(gè)數(shù)（即隊(duì)列長(zhǎng)度）；②

選用空閑單元法：即front和rear之一指向?qū)嵲兀硪恢赶蚩臻e元素。

隊(duì)空條件:front=rear(初始化時(shí)：front=rear)隊(duì)滿(mǎn)條件：front=(rear+1)%N(N=maxsize)隊(duì)列長(zhǎng)度：L=（N＋rear－front）%N

rearJ2J3 J1J4

J5front問(wèn)2：在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿(mǎn)時(shí)共有多少個(gè)元素？問(wèn)1：左圖中隊(duì)列長(zhǎng)度L=？左圖中隊(duì)列容量maxsizeN=？n-15630數(shù)據(jù)結(jié)構(gòu)第六次課-棧和隊(duì)列B共34頁(yè)，您現(xiàn)在瀏覽的是第30頁(yè)!例2：數(shù)組Ｑ[n]用來(lái)表示一個(gè)循環(huán)隊(duì)列，f為當(dāng)前隊(duì)列頭元素的前一位置，r為隊(duì)尾元素的位置。假定隊(duì)列中元素的個(gè)數(shù)小于n，計(jì)算隊(duì)列中元素的公式為:（Ａ）r－f（Ｂ）（n＋f－r）%n（Ｃ）n＋r－f（Ｄ）（n＋r－f）%n4種公式哪種合理？當(dāng)r≥f時(shí)（A）合理；當(dāng)r<f時(shí)（C）合理；分析：綜合2種情況，以（D）的表達(dá)最為合理例3：在一個(gè)循環(huán)隊(duì)列中，若約定隊(duì)首指針指向隊(duì)首元素的前一個(gè)位置。那么，從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，其操作是先

，后

。

移動(dòng)隊(duì)首指針取出元素√rear123450J4,J5,J6入隊(duì)J4J5J6front31數(shù)