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