?
第三講堆棧和隊(duì)列
堆棧和隊(duì)列都是特殊的線(xiàn)性表，他們的邏輯關(guān)系完全相同，差別是線(xiàn)性表的插入和刪除操作不受限制，而堆棧只能在棧頂插入和刪除，隊(duì)列只能在隊(duì)尾插入、隊(duì)頭刪除，堆棧和隊(duì)列都可以分別用順序儲(chǔ)存結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，堆棧的操作主要有入棧、出棧、取棧頂元素、是否為空，可以設(shè)計(jì)通用接口Stack..ava如下：
?
/**
?* @author 張鈺
?*
?*/
public interface Stack {
??? public void push(Object obj) throws Exception;//把數(shù)據(jù)元素obj插入堆棧
??? public Object pop()throws Exception;//出棧，刪除棧頂元素并返回
??? public Object getTop()throws Exception;//獲取棧頂元素
??? public boolean notEmpty();//判斷是否為空
}
下面就不同的結(jié)構(gòu)展開(kāi)：
(一)順序堆棧
?? 具有順序儲(chǔ)存結(jié)構(gòu)的堆棧稱(chēng)為順序堆棧，順序堆棧和順序表的數(shù)據(jù)成員是相同的，只是順序堆棧的入棧和出棧操作只能在當(dāng)前棧頂進(jìn)行，其結(jié)構(gòu)可以參考下圖：
棧底??????????????????????????????? 棧頂
satck???????????????????????????????????????? top=5???????????? maxStackSize-1
?
stack表示順序堆棧儲(chǔ)存數(shù)據(jù)的數(shù)組，a0、a1等表示已經(jīng)入棧的數(shù)據(jù)，a0比a1先入棧，maxStackSize表示順序堆棧數(shù)組stack的最大元素個(gè)數(shù)，top表示順序堆棧的stack的當(dāng)前棧頂?shù)南聵?biāo)，設(shè)計(jì)順序堆棧類(lèi)如下SeqStack.java：
?
?
/**
?* @author 張鈺
?*
?*/
public class SeqStack implements Stack {
?
?????? /*
?????? ?* @see Stack#push(java.lang.Object)
?????? ?*/
??? final int defaultSize=10;
??? int top;
??? Object[] stack;
??? int maxStackSize;
??? public SeqStack(){
??? ?????? initiate(defaultSize);
??? }
??? public SeqStack(int sz){
??? ?????? initiate(sz);
??? }
?????? private void initiate(int sz) {
????????????? // 初始化
????????????? maxStackSize=sz;
????????????? top=0;
????????????? stack=new Object[maxStackSize];
?????? }
?????? public void push(Object obj) throws Exception {
????????????? // 插入堆棧
???????? if(top==maxStackSize){
??????? ?????? ?throw new Exception("堆棧已滿(mǎn)！");
???????? }
???????? stack[top]=obj;
???????? top++;
?????? }
?
?????? /*
?????? ?* @see Stack#pop()
?????? ?*/
?????? public Object pop() throws Exception {
????????????? // 出棧
????????????? if(top==0){
???????????????????? throw new Exception("堆棧已空！");
????????????? }
????????????? top--;
????????????? return stack[top];
?????? }
?
?????? /*
?????? ?* @see Stack#getTop()
?????? ?*/
?????? public Object getTop() throws Exception {
????????????? // 獲取棧頂數(shù)據(jù)
????????????? if(top==0){
???????????????????? throw new Exception("堆棧已空！");
????????????? }
????????????? return stack[top-1];
?????? }
?
?????? /*
?????? ?* @see Stack#notEmpty()
?????? ?*/
?????? public boolean notEmpty() {
????????????? // 判斷是否為空
????????????? return (top>0);
?????? }
?
}
(二) 鏈?zhǔn)蕉褩?/span>
鏈?zhǔn)蕉褩＞哂墟準(zhǔn)酱鎯?chǔ)結(jié)構(gòu)，用節(jié)點(diǎn)構(gòu)造鏈，，每個(gè)節(jié)點(diǎn)由兩個(gè)域組成，一個(gè)是存放數(shù)據(jù)元素的域element，另一個(gè)是存放下一個(gè)節(jié)點(diǎn)的對(duì)象引用域也就是指針域next,堆棧有兩端，插入數(shù)據(jù)和刪除元素的一端為棧頂，另一端為棧底，鏈?zhǔn)蕉褩６疾粠ь^節(jié)點(diǎn)（大家可以思考一下為什么？），鏈?zhǔn)蕉褩ｎ?lèi)的設(shè)計(jì)LinStack.java：
public class LinStack implements Stack{
Node head;//堆棧頭
int size;//節(jié)點(diǎn)個(gè)數(shù)
public void LinStack(){
head=null;
size=0;
}
public void push(Object obj){//入棧
head=new Node(obj,head);//新節(jié)點(diǎn)為棧頂
}
public Object pop() throws Exception{ //出棧
if(size==0){
throw new Exception(“堆棧已空”);
}
Object obj=head.element;//取原棧頂元素
head=head.next;//原棧頂節(jié)點(diǎn)脫鏈
Size--;
Return obj;
}
public Boolean notEmpty(){
return head!=null; //是否空
}
public Object getTop(){
return head.element; //取棧頂元素
}
}
，堆棧由于其操作的特殊性而存在，在很多地方能起到獨(dú)特的作用，比喻中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式，編譯軟件中的括號(hào)匹配問(wèn)題（eclipse中就很好）都是使用堆棧的特殊性來(lái)設(shè)計(jì)算法，具體的問(wèn)題大家可以和我一起交流！
?
下面講講隊(duì)列，隊(duì)列的特點(diǎn)就是從隊(duì)尾插入、隊(duì)頭刪除，也是一種特殊的線(xiàn)性表，隊(duì)列的操作和堆棧一樣主要有：入隊(duì)列、出隊(duì)列、取隊(duì)頭數(shù)據(jù)元素、是否為空，隊(duì)列的接口類(lèi)Queue.java可以設(shè)計(jì)如下：
/**
?* @author 張鈺
?*
?*/
?
public interface Queue{
public void append(Object obj) throws Exception;
public Object delete()throws Exception;
public Object getFront() throws Exception;
public Boolean notEmpty();
}
(三)順序隊(duì)列
具有順序結(jié)構(gòu)的隊(duì)列就叫順序隊(duì)列，順序隊(duì)列存在假溢出問(wèn)題，就是一個(gè)隊(duì)列最大存儲(chǔ)為6個(gè)元素，現(xiàn)在有a0 a1 a2 a3 a4 a5六個(gè)元素入隊(duì)列了，然后又有a0 a1 a2三個(gè)元素出隊(duì)列了，這樣剩下的三個(gè)元素占據(jù)的還是隊(duì)列的后三個(gè)位置，這時(shí)候要是有新的元素入隊(duì)列就會(huì)出現(xiàn)數(shù)組越界，而事實(shí)上隊(duì)列沒(méi)有滿(mǎn)，這就是假溢出問(wèn)題，出現(xiàn)問(wèn)題的原因就是隊(duì)尾rear和隊(duì)頭front的值不能由所定義數(shù)組下界值自動(dòng)轉(zhuǎn)化成上界值而產(chǎn)生的，解決的辦法就是把順序隊(duì)列所使用的儲(chǔ)存空間構(gòu)造成一個(gè)邏輯上首尾相連的循環(huán)隊(duì)列，當(dāng)隊(duì)尾rear和隊(duì)頭front達(dá)到maxSize-1后，再自加1自動(dòng)到0，這樣就不會(huì)出現(xiàn)隊(duì)列數(shù)組頭部已空但隊(duì)尾因數(shù)組下標(biāo)越界而引起的溢出的假溢出問(wèn)題，解決順序循環(huán)隊(duì)列的隊(duì)列滿(mǎn)和隊(duì)列空狀態(tài)判斷問(wèn)題通常三種方法：
? ?1．少用一個(gè)儲(chǔ)存空間，以隊(duì)尾rear加1等于隊(duì)頭front為隊(duì)列滿(mǎn)的判斷條件，即此時(shí)隊(duì)列滿(mǎn)的判斷條件為：(rear+1)%maxSize=front，隊(duì)列空的條件為：rear=front；
?? 2．設(shè)置一個(gè)標(biāo)志位，添加一個(gè)標(biāo)志位，設(shè)標(biāo)志位為tag，初始時(shí)置tag=0，每當(dāng)入隊(duì)列操作成功時(shí)就置tag=1，出隊(duì)列操作成功時(shí)標(biāo)志tag=0，那么此時(shí)隊(duì)列滿(mǎn)的判斷條件是：
rear= =front && tag= =1，隊(duì)列空的判斷條件是：rear==front && tag= =0；
?? 3．設(shè)置一個(gè)計(jì)數(shù)器，添加一個(gè)計(jì)數(shù)器count，初始count=0，每當(dāng)入隊(duì)列操作成功時(shí)count加1，每當(dāng)出隊(duì)列操作成功count減1，這樣計(jì)數(shù)器不僅有標(biāo)示功能還有計(jì)數(shù)功能，此時(shí)判斷隊(duì)列滿(mǎn)的條件是：count>0 && rear= =front，隊(duì)列空的條件是：count= =0；
上面三種方法很明顯最好的是第三種使用計(jì)數(shù)器的方法，采用這種計(jì)數(shù)器的辦法可以設(shè)計(jì)順序循環(huán)隊(duì)列的類(lèi)SeqQueue.java如下：
?? public class SeqQueue implements Queue{
????? static final int defaultSize=10;
????? int front;
????? int rear;
????? int count;
????? int maxSize;
????? Object[] data;
????? public SeqQueue(){
???? initiate(defaultSize);
}
public SeqQueue(int sz){
?initiate(sz);
}
public void initiate(int sz){
? maxSize=sz;
? front=rear=0;
? count=0;
? data=new Object[sz];
}
public void append(Object obj) throws Exception{
?? if(count>0 && front= =rear){
throw new Exception(“隊(duì)列已滿(mǎn)！”);
}
data[rear]=obj;
rear=(rear+1)%maxSize;
count++
}
public Object delelte() throws Exception{
???????? if(count= =0){
??? throw new Exception(“隊(duì)列已空！”);
}
Object temp=data[front];
front=(front+1)%maxSize;
count- -
return temp;
}
public Object getFront() throws Exception{
??? if(count= =0){
??? throw new Exception(“隊(duì)列已空”);
}
return data[front];
}
public Boolean notEmpty(){
?? return count!=0;
}
}
以上就是順序隊(duì)列的java表示，大家可以自己做些例子測(cè)試一下，隊(duì)列還有一種就是鏈?zhǔn)疥?duì)列，鏈?zhǔn)疥?duì)列就是具有鏈?zhǔn)浇Y(jié)構(gòu)的隊(duì)列，鏈?zhǔn)疥?duì)列通常設(shè)計(jì)成不帶頭節(jié)點(diǎn)的結(jié)構(gòu)，結(jié)合以前的鏈?zhǔn)奖砜梢院苋菀自O(shè)計(jì)出鏈?zhǔn)疥?duì)列的類(lèi)，這個(gè)任務(wù)就留給大家了，如果有什么疑問(wèn)的話(huà)可以到我們的論壇咨詢(xún)(http://www.easyjf.com/bbs)，隊(duì)列就是一種從隊(duì)尾進(jìn)入隊(duì)頭刪除的特殊的順序表，設(shè)計(jì)時(shí)還考慮了一種優(yōu)先級(jí)隊(duì)列，就是給隊(duì)列中的每個(gè)元素添加一個(gè)優(yōu)先級(jí)標(biāo)示，出隊(duì)列時(shí)按優(yōu)先級(jí)從高到低的順序進(jìn)行，這就是優(yōu)先級(jí)隊(duì)列，在系統(tǒng)進(jìn)程管理中的應(yīng)用很廣泛，這個(gè)優(yōu)先級(jí)隊(duì)列這里不做過(guò)多的闡述，有興趣的同學(xué)可以研究研究，也可以和我一起探討！下一講：串！
(注：本文作者,EasyJF開(kāi)源團(tuán)隊(duì) 天意，轉(zhuǎn)載請(qǐng)保留作者聲明！)