第03章 棧和隊列

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

（第2版）數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）第0章Java程序設(shè)計基礎(chǔ)第1章緒論 第2章線性表第3章棧與隊列第4章串第5章數(shù)組和廣義表第6章樹和二叉樹第7章圖第8章查找第9章排序第10章綜合應(yīng)用設(shè)計第11章Java開發(fā)運(yùn)行環(huán)境第3章棧和隊列3.1棧3.2隊列目的：使用?；蜿犃星蠼鈶?yīng)用問題。要求：掌握棧和隊列抽象數(shù)據(jù)類型，以及順 序和鏈?zhǔn)酱鎯Y(jié)構(gòu)實現(xiàn)；理解對于怎 樣的應(yīng)用問題，需要使用?；蜿犃?， 以及怎樣使用。重點：棧和隊列的設(shè)計和應(yīng)用。難點：棧或隊列的使用場合，以及如何使用 棧和隊列求解應(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ī)制的實現(xiàn)基礎(chǔ)使用棧以非遞歸方式實現(xiàn)遞歸算法數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》例3.1判斷表達(dá)式中圓括號是否匹配數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》例3.2使用棧計算表達(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隊列3.2.1隊列抽象數(shù)據(jù)類型3.2.2順序隊列3.2.3鏈?zhǔn)疥犃?.2.4隊列的應(yīng)用數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》3.2.1隊列抽象數(shù)據(jù)類型隊列（queue）是一種特殊的線性表，其插入和刪除操作分別在線性表的兩端進(jìn)行。publicinterfaceQQueue<E>{//隊列接口

boolean

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

boolean

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

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

privateObjectvalue[];

privateint

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

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