第三講
堆棧和隊列
堆棧和隊列都是特殊的線性表，他們的邏輯關系完全相同，差別是線性表的插入和刪除操作不受限制，而堆棧只能在棧頂插入和刪除，隊列只能在隊尾插入、隊頭刪除，堆棧和隊列都可以分別用順序儲存結構和鏈式存儲結構，堆棧的操作主要有入棧、出棧、取棧頂元素、是否為空，可以設計通用接口
Stack..ava
如下：
?
/**
?* @author
張鈺
?*
?*/
public interface Stack {
??? public void push(Object obj) throws Exception;//
把數據元素
obj
插入堆棧
??? public Object pop()throws Exception;//
出棧，刪除棧頂元素并返回
??? public Object getTop()throws Exception;//
獲取棧頂元素
??? public boolean notEmpty();//
判斷是否為空
}
下面就不同的結構展開：
(
一
)
順序堆棧
??
具有順序儲存結構的堆棧稱為順序堆棧，順序堆棧和順序表的數據成員是相同的，只是順序堆棧的入棧和出棧操作只能在當前棧頂進行，其結構可以參考下圖：
棧底
???????????????????????????????
棧頂
satck???????????????????????????????????????? top=5???????????? maxStackSize-1
?
stack
表示順序堆棧儲存數據的數組，
a0
、
a1
等表示已經入棧的數據，
a0
比
a1
先入棧，
maxStackSize
表示順序堆棧數組
stack
的最大元素個數，
top
表示順序堆棧的
stack
的當前棧頂的下標，設計順序堆棧類如下
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 {
????????????? //
獲取棧頂數據
????????????? if(top==0){
???????????????????? throw new Exception("
堆棧已空！
");
????????????? }
????????????? return stack[top-1];
?????? }
?
?????? /*
??????
?* @see Stack#notEmpty()
??????
?*/
?????? public boolean notEmpty() {
????????????? //
判斷是否為空
????????????? return (top>0);
?????? }
?
}
(
二
)
鏈式堆棧
鏈式堆棧具有鏈式存儲結構，用節點構造鏈，，每個節點由兩個域組成，一個是存放數據元素的域
element
，另一個是存放下一個節點的對象引用域也就是指針域
next,
堆棧有兩端，插入數據和刪除元素的一端為棧頂，另一端為棧底，鏈式堆棧都不帶頭節點（大家可以思考一下為什么？），鏈式堆棧類的設計
LinStack.java
：
public class LinStack implements Stack{
Node head;//
堆棧頭
int size;//
節點個數
public void LinStack(){
head=null;
size=0;
}
public void push(Object obj){//
入棧
head=new Node(obj,head);//
新節點為棧頂
}
public Object pop() throws Exception{ //
出棧
if(size==0){
throw new Exception(“
堆棧已空
”);
}
Object obj=head.element;//
取原棧頂元素
head=head.next;//
原棧頂節點脫鏈
Size--;
Return obj;
}
public Boolean notEmpty(){
return head!=null; //
是否空
}
public Object getTop(){
return head.element; //
取棧頂元素
}
}
，堆棧由于其操作的特殊性而存在，在很多地方能起到獨特的作用，比喻中綴表達式轉換成后綴表達式，編譯軟件中的括號匹配問題（
eclipse
中就很好）都是使用堆棧的特殊性來設計算法，具體的問題大家可以和我一起交流！
?
下面講講隊列，隊列的特點就是從隊尾插入、隊頭刪除，也是一種特殊的線性表，隊列的操作和堆棧一樣主要有：入隊列、出隊列、取隊頭數據元素、是否為空，隊列的接口類
Queue.java
可以設計如下：
/**
?* @author
張鈺
?*
?*/
?
public interface Queue{
public void append(Object obj) throws Exception;
public Object delete()throws Exception;
public Object getFront() throws Exception;
public Boolean notEmpty();
}
(
三
)
順序隊列
具有順序結構的隊列就叫順序隊列，順序隊列存在假溢出問題，就是一個隊列最大存儲為
6
個元素，現在有
a0 a1 a2 a3 a4 a5
六個元素入隊列了，然后又有
a0 a1 a2
三個元素出隊列了，這樣剩下的三個元素占據的還是隊列的后三個位置，這時候要是有新的元素入隊列就會出現數組越界，而事實上隊列沒有滿，這就是假溢出問題，出現問題的原因就是隊尾
rear
和隊頭
front
的值不能由所定義數組下界值自動轉化成上界值而產生的，解決的辦法就是把順序隊列所使用的儲存空間構造成一個邏輯上首尾相連的循環隊列，當隊尾
rear
和隊頭
front
達到
maxSize-1
后，再自加
1
自動到
0
，這樣就不會出現隊列數組頭部已空但隊尾因數組下標越界而引起的溢出的假溢出問題，解決順序循環隊列的隊列滿和隊列空狀態判斷問題通常三種方法：
?
?1
．少用一個儲存空間，以隊尾
rear
加
1
等于隊頭
front
為隊列滿的判斷條件，即此時隊列滿的判斷條件為：
(rear+1)%maxSize=front
，隊列空的條件為：
rear=front
；
?? 2
．設置一個標志位，添加一個標志位，設標志位為
tag
，初始時置
tag=0
，每當入隊列操作成功時就置
tag=1
，出隊列操作成功時標志
tag=0
，那么此時隊列滿的判斷條件是：
rear= =front && tag= =1
，隊列空的判斷條件是：
rear==front && tag= =0
；
?? 3
．設置一個計數器，添加一個計數器
count
，初始
count=0
，每當入隊列操作成功時
count
加
1
，每當出隊列操作成功
count
減
1
，這樣計數器不僅有標示功能還有計數功能，此時判斷隊列滿的條件是：
count>0 && rear= =front
，隊列空的條件是：
count= =0
；
上面三種方法很明顯最好的是第三種使用計數器的方法，采用這種計數器的辦法可以設計順序循環隊列的類
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
表示，大家可以自己做些例子測試一下，隊列還有一種就是鏈式隊列，鏈式隊列就是具有鏈式結構的隊列，鏈式隊列通常設計成不帶頭節點的結構，結合以前的鏈式表可以很容易設計出鏈式隊列的類，這個任務就留給大家了，如果有什么疑問的話可以到我們的論壇咨詢
(http://www.easyjf.com/bbs)
，隊列就是一種從隊尾進入隊頭刪除的特殊的順序表，設計時還考慮了一種優先級隊列，就是給隊列中的每個元素添加一個優先級標示，出隊列時按優先級從高到低的順序進行，這就是優先級隊列，在系統進程管理中的應用很廣泛，這個優先級隊列這里不做過多的闡述，有興趣的同學可以研究研究，也可以和我一起探討！下一講：串！