第03章 棧和隊列

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

（第2版）數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）第0章Java程序設計基礎第1章緒論 第2章線性表第3章棧與隊列第4章串第5章數(shù)組和廣義表第6章樹和二叉樹第7章圖第8章查找第9章排序第10章綜合應用設計第11章Java開發(fā)運行環(huán)境第3章棧和隊列3.1棧3.2隊列目的：使用?；蜿犃星蠼鈶脝栴}。要求：掌握棧和隊列抽象數(shù)據(jù)類型，以及順 序和鏈式存儲結(jié)構(gòu)實現(xiàn)；理解對于怎 樣的應用問題，需要使用?；蜿犃校? 以及怎樣使用。重點：棧和隊列的設計和應用。難點：?；蜿犃械氖褂脠龊希约叭绾问褂?棧和隊列求解應用問題。數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》3.1棧3.1.1棧抽象數(shù)據(jù)類型3.1.2順序棧3.1.3鏈式棧3.1.4棧的應用數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》3.1.1棧抽象數(shù)據(jù)類型棧（stack）是一種特殊的線性表，其插入和刪除操作只允許在線性表的一端進行。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;//棧頂元素下標}數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》3.1.3鏈式棧publicclassLinkedStack<E>implementsSStack<E>{privateNode<E>top;}數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》3.1.4棧的應用棧是嵌套調(diào)用機制的實現(xiàn)基礎使用棧以非遞歸方式實現(xiàn)遞歸算法數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》例3.1判斷表達式中圓括號是否匹配數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》例3.2使用棧計算表達式的值。中綴表達式1+2*(3-4)+5數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》1.將中綴表達式轉(zhuǎn)換為后綴表達式數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》2.后綴表達式求值數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》3.2隊列3.2.1隊列抽象數(shù)據(jù)類型3.2.2順序隊列3.2.3鏈式隊列3.2.4隊列的應用數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》3.2.1隊列抽象數(shù)據(jù)類型隊列（queue）是一種特殊的線性表，其插入和刪除操作分別在線性表的兩端進行。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;//隊列頭尾下標}數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）》3.2.3鏈式隊列publicclassLinkedQueue<E>implementsQQueue<E>{ //鏈式隊列類

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