棧是一種常用的數據結構，在生活中經常遇到這樣的例子，如鐵路調度站。本節將詳細介紹堆棧的實現過程。

算法點撥(順序棧)

棧是一種重要的數據結構。從數據結構的角度看，棧也是線性表，其特殊性在于棧的基本操作是線性表操作的子集，它們是操作受限的線性表，因此可以稱為限定性的數據結構。其操作是限定在表尾進行插入和刪除操作，允許操作的一端稱為棧頂。棧的結構如圖11.09所示：

圖11.09 棧的結構

實現棧首先需要實現一個棧內元素，關鍵代碼如下：

Java代碼

public class Stack {

private int maxSize;

private int stackArray[];

private int top=-1;

public Stack(int s){ //構造方法

maxSize=s;

stackArray=new int[maxSize];

}

}

說明：

上述代碼中，公共成員stackArray用于儲存棧中的數據，top用于存儲下一個數據元素的指針。對于棧的操作，無非是進行數據元素的入棧與出棧。

1．查找棧中元素

在進行棧中元素查找時，通常根據棧中元素的數據查找節點。要實現棧中元素的查找，首先需要解決的問題就是遍歷棧中的所有元素。可以從棧頂開始，利用循環的方式向下查找，只要不到棧底就可循環查找。

2．入棧操作

入棧操作前面說過，只能在棧頂操作。先將top指針向后移動一個單位，然后將想要入棧的數據元素放到原來top指針所指向的元素位置即可。這樣就實現了對棧的入棧操作。操作流程如圖11.10所示：

圖11.10 入棧操作示意圖

3．出棧操作

出棧操作和入棧操作的限定差不多，只是將整個過程反過來進行。先將數據元素釋放掉，然后在進行指針的操作，將棧頂指針top向前移動一個位置，使其位置在其原來所指向的位置。將棧頂元素的指針域的指針的指向位置變為原來元素的指向位置。出棧的操作流程如圖11.11所示

圖11.11 刪除節點示意圖

算法實現

棧是限定僅在表尾進行插入或刪除操作的線性表。因此對棧來說，表尾端有其特殊含義。

例11.3 實現棧的算法

首先需要實現自定義的數據元素類，該類的實現方法可以參看本節算法點撥中的代碼。

定義數據元素之后，開始棧的操作編程了。在類中，采用了push，pop，isEmpty，isfull，等方法進行入棧，出棧，判斷棧是否為空，判斷棧是否滿和對棧進行輸出。

向棧中添加數據的代碼如下：

Java代碼

public void push(int j){ //入棧方法

stackArray[++top]=j; //棧頂指針后移

}

對棧進行出棧的操作的代碼如下：

Java代碼

public int pop(){ //出棧方法

return stackArray[top--]; //棧頂指針前移

}

對棧是否為空和是否已滿以及輸出的判斷代碼如下：

Java代碼

public boolean isEmpty(){ //判斷棧是否為空

return (top==-1);

}

public boolean isFull(){ //判斷棧是否為滿

return (top==maxSize-1);

}

public void s(int d){ //輸出棧中內容

System.out.println("棧序列：");

for(int i=0;i

System.out.print(stackArray[i]+" ");

}

}

為了檢查創建棧操作的正確性，特別創建了一個名稱為StackTest的類，測試棧的入棧和出棧的操作，其關鍵代碼如下：

Java代碼

package stack;

public class StackTest {

public static void main(String[] args) {

int i=0;

Stack s=new Stack(20);

if(!s.isFull()){ //判斷棧是否滿，沒滿則調用入棧方法

s.push(100);i++;

s.push(23);i++;

s.push(45);i++;

s.push(78);i++;

s.s(i);

}

System.out.println("\n");

System.out.println("出棧序列：");

while(!s.isEmpty()){ //判斷棧是否為空，非空則調用出棧方法

int k=s.pop();

System.out.print(k+" ");

}

}

}

運行上面的代碼后，在控制臺輸出的信息如圖11.12所示。

圖11.12 運行測試類后在控制臺輸出的棧中的數據

算法點撥(兩棧共享空間)

在一個程序中如果需要同時使用具有相同數據類型的兩個棧時，我們覺得最直接的辦法就是，同時開辟出兩塊空間，建立兩個棧，但是這樣有時會出現，一個棧已經棧滿溢出了，而另一個棧確實空余出大量的存儲空間，這樣會造成大量存儲空間的浪費。現在我們可以找一種解決的方法，那就是：兩棧共享空間。我們使用一個數組來存儲兩個棧，讓一個棧的棧底為數組的始端，另一個棧的棧底為數組的末端，每個棧的棧頂都向中間延伸。兩棧共享空間的結構如圖11.13所示：

圖11.13 棧的結構

實現棧首先需要實現一個棧內元素，關鍵代碼如下：

Java代碼

public class Stack {

private int maxSize;

private int stackArray[];

private int top=-1;

public Stack(int s){ //構造方法

maxSize=s;

stackArray=new int[maxSize];

}

}

說明：

上述代碼中，公共成員stackArray用于儲存棧中的數據，top用于存儲下一個數據元素的指針。對于棧的操作，無非是進行數據元素的入棧與出棧。

1．查找共享空間棧中元素

在進行共享空間的棧中元素查找時，首先我們先要確定我們是要查找哪一個棧中的元素，然后的操作就和順序棧基本一樣了。

2．入棧操作

兩棧共享空間的入棧操作也是我們要先確定我們要對哪一個棧進行操作。入棧操作前面我們在順序棧中已經說過，只能在棧頂操作。例如我們選擇對棧一進行操作，先將top1指針向后移動一個單位，然后將想要入棧的數據元素放到原來top1指針所指向的元素位置即可。這樣就實現了對棧的入棧操作。操作流程如圖11.14所示：

圖11.14 入棧操作示意圖

3．出棧操作

對于共享空間棧的出棧操作和入棧操作的限定差不多，只是將整個過程反過來進行。先將數據元素釋放掉，然后在進行指針的操作，將棧頂指針top1向前移動一個位置，使其位置在其原來所指向的位置。將棧頂元素的指針域的指針的指向位置變為原來元素的指向位置。出棧的操作流程如圖11.15所示

圖11.15 刪除節點示意圖

算法實現

棧是限定僅在表尾進行插入或刪除操作的線性表。因此對棧來說，表尾端有其特殊含義。

例11.4 實現棧的算法

首先需要實現自定義的數據元素類，該類的實現方法可以參看本節算法點撥中的代碼。

定義數據元素之后，開始棧的操作編程了。在類中，采用了push，pop，isEmpty，isfull，s等方法進行入棧，出棧，判斷棧是否為空，判斷棧是否滿和對棧進行輸出。

向棧中添加數據的代碼如下：

Java代碼

public int bos(int i,int x){

int top1=0,top2=stackArray.length-1;

if(top1==top2){

System.out.println("元素溢出！");

}

if(i==1){ //如果操作棧1

return stackArray[++top1]=x;

}

if(i==2){ //如果操作棧2

return stackArray[--top2]=x;

}

return x; //返回插入的數

}

對棧進行出棧的操作的代碼如下：

Java代碼

public int bpop(int i){

if(i==1){ //如果是棧1

if(top1==-1){

System.out.println("下溢！");

}

return stackArray[top1--]; //棧頂回縮一位

}

if(i==2){ //如果是棧2

if(top2==stackArray.length){

System.out.println("下溢！");

}

return stackArray[top2++]; //棧頂后退一位

}

return i;

}

算法點撥(鏈棧)

棧的鏈接存儲被稱之為鏈棧。通常我們會用單鏈表進行對棧的存儲，因此其結構特點與單鏈表的結構特點基本相同。因為只能在棧頂進行插入和刪除操作，這樣我們就可以使用單鏈表的表頭作為棧的棧頂是最為方便的。其操作流程如圖11.16所示：

圖11.16 鏈棧流程圖

1．查找鏈棧中元素

對鏈棧進行查找操作，其本質上和對鏈表的查找操作是一樣的，只是限定了其只可以從一端進行操作，從表頭查起就可以了。

2．入棧操作

對于鏈棧的入棧操作，其實就是單鏈表的操作的簡化。我們只需要考慮棧頂的操作也就是第一位置的情況。操作流程如圖11.17所示：

圖11.17 入棧操作示意圖

3．出棧操作

對于鏈棧的出棧，其操作也是很簡單的，也是基于單鏈表的基本操作，也是僅僅是對第一位置的操作，不用考慮其他位置。出棧的操作流程如圖11.18所示

圖11.18 刪除節點示意圖

算法實現

鏈棧是限定僅在表尾進行插入或刪除操作的線性表。因此對棧來說，表尾端有其特殊含義。

例11.5 實現棧的算法

首先需要實現自定義的數據元素類，該類的實現方法可以參看本節算法點撥中的代碼。

定義數據元素之后，開始棧的操作編程了。在類中，采用了push，pop，isEmpty，isfull，s等方法進行入棧，出棧，判斷棧是否為空，判斷棧是否滿和對棧進行輸出。

實現鏈表首先需要實現一個節點類，關鍵代碼如下：

Java代碼

package stack;

public class Node {

public Node next; //指向下一個元素的指針域

public int values; //存儲元素的本身數據

public Node(){

int value = 0;

values=value;

}

}

說明：

上述代碼中，公共成員Value用于儲存節點本身的數據，Next用于存儲下一個節點的指針。

對于鏈棧的操作，無非是進行節點的插入和刪除操作對棧進行出棧的操作的代碼如下：

Java代碼

package stack;

public class Lstack {

Node top=new Node();

public void lpush(){

int x=0;

Node s=new Node(); //申請一個新的節點

s.values=x;

s.next=top; //將節點s插在棧頂

top=s;

}

public int lpop(){

int x=0;

Node p=new Node();

if(top==null){

System.out.println("下溢！");

}

x=top.values; //暫存棧頂元素

p=top; //將棧頂元素摘鏈

top=top.next;

return x;

}

}