第03章 棧和隊(duì)列

葉核亞數(shù)據(jù)結(jié)構(gòu)（Java版）

（第2版）數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）第0章Java程序設(shè)計(jì)基礎(chǔ)第1章緒論 第2章線性表第3章棧與隊(duì)列第4章串第5章數(shù)組和廣義表第6章樹和二叉樹第7章圖第8章查找第9章排序第10章綜合應(yīng)用設(shè)計(jì)第11章Java開發(fā)運(yùn)行環(huán)境第3章棧和隊(duì)列3.1棧3.2隊(duì)列目的：使用?；蜿?duì)列求解應(yīng)用問題。要求：掌握棧和隊(duì)列抽象數(shù)據(jù)類型，以及順 序和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)；理解對(duì)于怎 樣的應(yīng)用問題，需要使用棧或隊(duì)列， 以及怎樣使用。重點(diǎn)：棧和隊(duì)列的設(shè)計(jì)和應(yīng)用。難點(diǎn)：棧或隊(duì)列的使用場(chǎng)合，以及如何使用 棧和隊(duì)列求解應(yīng)用問題。數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》3.1棧3.1.1棧抽象數(shù)據(jù)類型3.1.2順序棧3.1.3鏈?zhǔn)綏?.1.4棧的應(yīng)用數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》3.1.1棧抽象數(shù)據(jù)類型棧（stack）是一種特殊的線性表，其插入和刪除操作只允許在線性表的一端進(jìn)行。publicinterfaceSStack<E>{

boolean

isEmpty();//判斷是否空棧

boolean

push(Eelement);//入棧Epop(); //出棧Eget();//取棧頂元素值}數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》3.1.2順序棧publicclassSeqStack<E>implementsSStack<E>{

privateObjectvalue[];

privateinttop;//棧頂元素下標(biāo)}數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》3.1.3鏈?zhǔn)綏ublicclassLinkedStack<E>implementsSStack<E>{privateNode<E>top;}數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》3.1.4棧的應(yīng)用棧是嵌套調(diào)用機(jī)制的實(shí)現(xiàn)基礎(chǔ)使用棧以非遞歸方式實(shí)現(xiàn)遞歸算法數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》例3.1判斷表達(dá)式中圓括號(hào)是否匹配數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》例3.2使用棧計(jì)算表達(dá)式的值。中綴表達(dá)式1+2*(3-4)+5數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》1.將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》2.后綴表達(dá)式求值數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》3.2隊(duì)列3.2.1隊(duì)列抽象數(shù)據(jù)類型3.2.2順序隊(duì)列3.2.3鏈?zhǔn)疥?duì)列3.2.4隊(duì)列的應(yīng)用數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》3.2.1隊(duì)列抽象數(shù)據(jù)類型隊(duì)列（queue）是一種特殊的線性表，其插入和刪除操作分別在線性表的兩端進(jìn)行。publicinterfaceQQueue<E>{//隊(duì)列接口

boolean

isEmpty();//判斷隊(duì)列是否為空

boolean

enqueue(Eelement);//入隊(duì)Edequeue(); //出隊(duì)}

數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》3.2.2順序隊(duì)列順序隊(duì)列，假溢出數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》2.順序循環(huán)隊(duì)列front=(front+1)%length;rear=(rear+1)%length;數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》3.順序循環(huán)隊(duì)列類publicclassSeqQueue<E>implementsQQueue<E>{

privateObjectvalue[];

privateint

front,rear;//隊(duì)列頭尾下標(biāo)}數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》3.2.3鏈?zhǔn)疥?duì)列publicclassLinkedQueue<E>implementsQQueue<E>{ //鏈?zhǔn)疥?duì)列類

privateNode<E>front,rear;}數(shù)據(jù)結(jié)構(gòu)（Java版）（