第三講堆棧和隊(duì)列

堆棧和隊(duì)列都是特殊的線性表，他們的邏輯關(guā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)展開：

(一)順序堆棧

?? 具有順序儲(chǔ)存結(jié)構(gòu)的堆棧稱為順序堆棧，順序堆棧和順序表的數(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ì)順序堆棧類如下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)酱鎯?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)蕉褩ｎ惖脑O(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)匹配問題（eclipse中就很好）都是使用堆棧的特殊性來(lái)設(shè)計(jì)算法，具體的問題大家可以和我一起交流！

?

下面講講隊(duì)列，隊(duì)列的特點(diǎn)就是從隊(duì)尾插入、隊(duì)頭刪除，也是一種特殊的線性表，隊(duì)列的操作和堆棧一樣主要有：入隊(duì)列、出隊(duì)列、取隊(duì)頭數(shù)據(jù)元素、是否為空，隊(duì)列的接口類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ì)列存在假溢出問題，就是一個(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ì)列沒有滿，這就是假溢出問題，出現(xià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)越界而引起的溢出的假溢出問題，解決順序循環(huán)隊(duì)列的隊(duì)列滿和隊(duì)列空狀態(tài)判斷問題通常三種方法：

? ?1．少用一個(gè)儲(chǔ)存空間，以隊(duì)尾rear加1等于隊(duì)頭front為隊(duì)列滿的判斷條件，即此時(shí)隊(duì)列滿的判斷條件為：(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ì)列滿的判斷條件是：

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ì)列滿的條件是：count>0 && rear= =front，隊(duì)列空的條件是：count= =0；

上面三種方法很明顯最好的是第三種使用計(jì)數(shù)器的方法，采用這種計(jì)數(shù)器的辦法可以設(shè)計(jì)順序循環(huán)隊(duì)列的類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ì)列已滿！”);

}

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;

}

}