資料結構Java實作05----棧：順序棧和鍊式堆棧

一、堆棧的基本概念：

堆棧（也簡稱作棧）是一種特殊的線性表，堆棧的資料元素以及資料元素間的邏輯關系和線性表完全相同，其差别是線性表允許在任意位置進行插入和删除操作，而堆棧隻允許在固定一端進行插入和删除操作。

先進後出：堆棧中允許進行插入和删除操作的一端稱為棧頂，另一端稱為棧底。堆棧的插入和删除操作通常稱為進棧或入棧，堆棧的删除操作通常稱為出棧或退棧。

備注：棧本身就是一個線性表，是以我們之前讨論過線性表的順序存儲和鍊式存儲，對于棧來說，同樣适用。

二、堆棧的抽象資料類型：

資料集合：

堆棧的資料集合可以表示為a0,a1,…,an-1，每個資料元素的資料類型可以是任意的類類型。

操作集合：

（1）入棧push(obj)：把資料元素obj插入堆棧。

（2）出棧pop()：出棧, 删除的資料元素由函數傳回。

（3）取棧頂資料元素getTop()：取堆棧目前棧頂的資料元素并由函數傳回。

（4）非空否notEmpty()：若堆棧非空則函數傳回true，否則函數傳回false。

三、順序棧：

順序存儲結構的堆棧稱作順序堆棧。其存儲結構示意圖如下圖所示：

1、順序棧的實作：

（1）設計Stack接口

（2）實作SequenceStack類

注：棧是線性表的特例，線性表本身就是用數組來實作的。于是，順序棧也是用數組實作的。

代碼實作：

(1)Stack.java:（Stack接口）

資料結構Java實作05----棧：順序棧和鍊式堆棧

1 public interface Stack {
 2 
 3     //入棧
 4     public void push(Object obj) throws Exception;
 5 
 6     //出棧
 7     public Object pop() throws Exception;
 8 
 9     //擷取棧頂元素
10     public Object getTop() throws Exception;
11 
12     //判斷棧是否為空
13      public boolean isEmpty();
14 }

資料結構Java實作05----棧：順序棧和鍊式堆棧

(2)SequenceStack.java:

資料結構Java實作05----棧：順序棧和鍊式堆棧

1 //順序棧
 2 public class SequenceStack implements Stack {
 3 
 4     Object[] stack; //對象數組（棧用數組來實作）
 5     final int defaultSize = 10; //預設最大長度
 6     int top; //棧頂位置（的一個下标）:其實可以了解成棧的實際長度
 7     int maxSize; //最大長度
 8 
 9     //如果用無參構造的話，就設定預設長度
10     public SequenceStack() {
11         init(defaultSize);
12     }
13 
14     //如果使用帶參構造的話，就調用指定的最大長度
15     public SequenceStack(int size) {
16         init(size);
17     }
18 
19     public void init(int size) {
20         this.maxSize = size;
21         top = 0;
22         stack = new Object[size];
23     }
24 
25     //擷取棧頂元素
26     @Override
27     public Object getTop() throws Exception {
28         // TODO Auto-generated method stub
29         if (isEmpty()) {
30             throw new Exception("堆棧為空！");
31         }
32 
33         return stack[top - 1];
34     }
35 
36     //判斷棧是否為空
37     @Override
38     public boolean isEmpty() {
39         // TODO Auto-generated method stub
40         return top == 0;
41     }
42 
43     //出棧操作
44     @Override
45     public Object pop() throws Exception {
46         // TODO Auto-generated method stub
47         if (isEmpty()) {
48             throw new Exception("堆棧為空！");
49         }
50         top--;
51 
52         return stack[top];
53     }
54 
55     //入棧操作
56     @Override
57     public void push(Object obj) throws Exception {
58         // TODO Auto-generated method stub
59         //首先判斷棧是否已滿
60         if (top == maxSize) {
61             throw new Exception("堆棧已滿！");
62         }
63         stack[top] = obj;
64         top++;
65     }
66 }

資料結構Java實作05----棧：順序棧和鍊式堆棧

2、測試類：

設計一個順序棧，從鍵盤輸入十個整數壓進棧，然後再彈出棧，并列印出棧序列。

(3)Test.java:

資料結構Java實作05----棧：順序棧和鍊式堆棧

1 import java.util.Scanner;
 2 
 3 public class Test {
 4     public static void main(String[] args) throws Exception {
 5         SequenceStack stack = new SequenceStack(10);
 6 
 7         Scanner in = new Scanner(System.in);
 8         int temp;
 9         for (int i = 0; i < 10; i++) {
10             System.out.println("請輸入第" + (i + 1) + "個整數：");
11             temp = in.nextInt();
12             stack.push(temp);
13         }
14 
15         //周遊輸出
16         while (!stack.isEmpty()) {
17             System.out.println(stack.pop());
18         }
19     }
20 }

資料結構Java實作05----棧：順序棧和鍊式堆棧

運作效果：

四、Java中棧與堆的差別：

棧(stack):（線程私有）

　　是一個先進後出的資料結構，通常用于儲存方法(函數)中的參數，局部變量。在java中,所有基本類型和引用類型的引用都在棧中存儲。棧中資料的生存空間一般在目前scopes内(就是由{...}括起來的區域)。

堆(heap):（線程共享）

　　是一個可動态申請的記憶體空間(其記錄空閑記憶體空間的連結清單由作業系統維護)，C中的malloc語句所産生的記憶體空間就在堆中。在java中，所有使用new xxx()構造出來的對象都在堆中存儲，當垃圾回收器檢測到某對象未被引用，則自動銷毀該對象。是以，理論上說java中對象的生存空間是沒有限制的，隻要有引用類型指向它，則它就可以在任意地方被使用。

五、hashCode與對象之間的關系：

如果兩個對象的hashCode不相同，那麼這兩個對象肯定也不同。

如果兩個對象的hashCode相同，那麼這兩個對象有可能相同，也有可能不同。

總結一句：不同的對象可能會有相同的hashCode；但是如果hashCode不同，那肯定不是同一個對象。

代碼舉例：

資料結構Java實作05----棧：順序棧和鍊式堆棧

1 public class StringTest {
 2 
 3     public static void main(String[] args) {
 4 
 5         //s1 和 s2 其實是同一個對象。對象的引用存放在棧中，對象存放在方法區的字元串常量池
 6         String s1 = "china";
 7         String s2 = "china";
 8 
 9         //凡是用new關鍵建立的對象，都是在堆記憶體中配置設定空間。
10         String s3 = new String("china");
11 
12         //凡是new出來的對象，絕對是不同的兩個對象。
13         String s4 = new String("china");
14 
15         System.out.println(s1 == s2);  //true
16         System.out.println(s1 == s3);
17         System.out.println(s3 == s4);
18         System.out.println(s3.equals(s4));
19 
20         System.out.println("\n-----------------\n");
21       /*String很特殊，重寫從父類繼承過來的hashCode方法，使得兩個
22        *如果字元串裡面的内容相等，那麼hashCode也相等。
23        **/
24 
25         //hashCode相同
26         System.out.println(s3.hashCode());  //hashCode為94631255
27         System.out.println(s4.hashCode());  //hashCode為94631255
28 
29         //identityHashCode方法用于擷取原始的hashCode
30         //如果原始的hashCode不同，表明确實是不同的對象
31 
32         //原始hashCode不同
33         System.out.println(System.identityHashCode(s3)); //2104928456
34         System.out.println(System.identityHashCode(s4)); //2034442961
35 
36         System.out.println("\n-----------------\n");
37 
38         //hashCode相同
39         System.out.println(s1.hashCode());  //94631255
40         System.out.println(s2.hashCode());  //94631255
41 
42         //原始hashCode相同：表明确實是同一個對象
43         System.out.println(System.identityHashCode(s1));  //648217993
44         System.out.println(System.identityHashCode(s2));  //648217993
45     }
46 }

資料結構Java實作05----棧：順序棧和鍊式堆棧

上面的代碼中，注釋已經标明了運作的結果。通過運作結果我們可以看到，s3和s4的字元串内容相同，但他們是兩個不同的對象，由于String類重寫了hashCode方法，他們的hashCode相同，但原始的hashCode是不同的。

六、鍊式堆棧：

　　鍊式存儲結構的堆棧稱作鍊式堆棧。

　　與單連結清單相同，鍊式堆棧也是由一個個結點組成的，每個結點由兩個域組成，一個是存放資料元素的資料元素域data，另一個是存放指向下一個結點的對象引用（即指針）域next。

　　堆棧有兩端，插入資料元素和删除資料元素的一端為棧頂，另一端為棧底。鍊式堆棧都設計成把靠近堆棧頭head的一端定義為棧頂。

依次向鍊式堆棧入棧資料元素a0, a1, a2, ..., an-1後，鍊式堆棧的示意圖如下圖所示：　

1、設計鍊式堆棧：

(1)Node.java:結點類

資料結構Java實作05----棧：順序棧和鍊式堆棧

1 //結點類
 2 public class Node {
 3 
 4     Object element; //資料域
 5     Node next;  //指針域
 6 
 7     //頭結點的構造方法
 8     public Node(Node nextval) {
 9         this.next = nextval;
10     }
11 
12     //非頭結點的構造方法
13     public Node(Object obj, Node nextval) {
14         this.element = obj;
15         this.next = nextval;
16     }
17     
18     //獲得目前結點的後繼結點
19     public Node getNext() {
20         return this.next;
21     }
22 
23     //獲得目前的資料域的值
24     public Object getElement() {
25         return this.element;
26     }
27 
28     //設定目前結點的指針域
29     public void setNext(Node nextval) {
30         this.next = nextval;
31     }
32 
33     //設定目前結點的資料域
34     public void setElement(Object obj) {
35         this.element = obj;
36     }
37 
38     public String toString() {
39         return this.element.toString();
40     }
41 }

資料結構Java實作05----棧：順序棧和鍊式堆棧

(2)Stack.java:

資料結構Java實作05----棧：順序棧和鍊式堆棧

1 //棧接口
 2 public interface Stack {
 3 
 4     //入棧
 5     public void push(Object obj) throws Exception;
 6 
 7     //出棧
 8     public Object pop() throws Exception;
 9 
10     //獲得棧頂元素
11     public Object getTop() throws Exception;
12 
13     //判斷棧是否為空
14     public boolean isEmpty();
15 }

資料結構Java實作05----棧：順序棧和鍊式堆棧

(3)LinkStack.java:

資料結構Java實作05----棧：順序棧和鍊式堆棧

1 public class LinkStack implements Stack {
 2 
 3     Node head;  //棧頂指針
 4     int size;  //結點的個數
 5 
 6     public LinkStack() {
 7         head = null;
 8         size = 0;
 9     }
10 
11     @Override
12     public Object getTop() throws Exception {
13         // TODO Auto-generated method stub
14         return head.getElement();
15     }
16 
17     @Override
18     public boolean isEmpty() {
19         // TODO Auto-generated method stub
20         return head == null;
21     }
22 
23     @Override
24     public Object pop() throws Exception {
25         // TODO Auto-generated method stub
26         if (isEmpty()) {
27             throw new Exception("棧為空！");
28         }
29         Object obj = head.getElement();
30         head = head.getNext();
31         size--;
32         return obj;
33     }
34 
35     @Override
36     public void push(Object obj) throws Exception {
37         // TODO Auto-generated method stub
38         head = new Node(obj, head);
39         size++;
40     }

資料結構Java實作05----棧：順序棧和鍊式堆棧

(4)Test.java:測試類

資料結構Java實作05----棧：順序棧和鍊式堆棧

1 import java.util.Scanner;
 2 
 3 public class Test {
 4 
 5     public static void main(String[] args) throws Exception {
 6         //SequenceStack stack = new SequenceStack(10);
 7         LinkStack stack = new LinkStack();
 8         Scanner in = new Scanner(System.in);
 9         int temp;
10         for (int i = 0; i < 10; i++) {
11             System.out.println("請輸入第" + (i + 1) + "個整數：");
12             temp = in.nextInt();
13             stack.push(temp);
14         }
15         //周遊輸出
16         while (!stack.isEmpty()) {
17             System.out.println(stack.pop());
18         }
19     }
20 }

資料結構Java實作05----棧：順序棧和鍊式堆棧

七、堆棧的應用:

堆棧是各種軟體系統中應用最廣泛的資料結構之一。括号比對和表達式計算是編譯軟體中的基本問題，其軟體設計中都需要使用堆棧。

括号比對問題
表達式計算

1、括号比對問題：

假設算術表達式中包含圓括号，方括号，和花括号三種類型。使用棧資料結構編寫一個算法判斷表達式中括号是否正确比對，并設計一個主函數測試。

比如：

{a+[b+(c*a)/(d-e)]} 正确

([a+b)-(c*e)]+{a+b} 錯誤，中括号的次序不對

括号比對有四種情況：

1.左右括号比對次序不正确

2.右括号多于左括号

3.左括号多于右括号

4.比對正确

下面我們就通過代碼把這四種情況列舉出來。

資料結構Java實作05----棧：順序棧和鍊式堆棧

1 public class Test {
 2 
 3     //方法：将字元串轉化為字元串數組
 4     public static String[] expToStringArray(String exp) {
 5         int n = exp.length();
 6         String[] arr = new String[n];
 7         for (int i = 0; i < arr.length; i++) {
 8             arr[i] = exp.substring(i, i + 1);
 9         }
10         return arr;
11     }
12 
13     //方法：括号比對問題的檢測
14     public static void signCheck(String exp) throws Exception {
15         SequenceStack stack = new SequenceStack();
16         String[] arr = Test.expToStringArray(exp);
17         for (int i = 0; i < arr.length; i++) {
18             if (arr[i].equals("(") || arr[i].equals("[") || arr[i].equals("{")) { //當碰到都是左邊的括号的時候，統統壓進棧
19                 stack.push(arr[i]);
20             } else if (arr[i].equals(")") && !stack.isEmpty() && stack.getTop().equals("(")) { //當碰到了右小括号時，如果比對正确，就将左小括号出棧
21                 stack.pop();
22             } else if (arr[i].equals(")") && !stack.isEmpty() && !stack.getTop().equals("(")) {
23                 System.out.println("左右括号比對次序不正确！");
24                 return;
25             } else if (arr[i].equals("]") && !stack.isEmpty() && stack.getTop().equals("[")) {
26                 stack.pop();
27             } else if (arr[i].equals("]") && !stack.isEmpty() && !stack.getTop().equals("[")) {
28                 System.out.println("左右括号比對次序不正确！");
29                 return;
30             } else if (arr[i].equals("}") && !stack.isEmpty() && stack.getTop().equals("{")) {
31                 stack.pop();
32             } else if (arr[i].equals("}") && !stack.isEmpty() && !stack.getTop().equals("{")) {
33                 System.out.println("左右括号比對次序不正确！");
34                 return;
35             } else if (arr[i].equals(")") || arr[i].equals("]") || arr[i].equals("}") && stack.isEmpty()) {
36                 System.out.println("右括号多于左括号！");
37                 return;
38             }
39         }
40         if (!stack.isEmpty()) {
41             System.out.println("左括号多于右括号！");
42         } else {
43             System.out.println("括号比對正确！");
44         }
45     }
46 
47 
48     public static void main(String[] args) throws Exception {
49 
50         String str = "([(a+b)-(c*e)]+{a+b}";
51         //括号比對的檢測
52         Test.signCheck(str);
53     }
54 }

資料結構Java實作05----棧：順序棧和鍊式堆棧

上方代碼中，第50行是一個錯誤的括号表達式，于是運作結果也很明顯了。

2、表達式計算：

　　3+(6-4/2)*5=23

其字尾表達式為：3642/-5*+# (#符号為結束符)

現在要做的是：

使用鍊式堆棧，設計一個算法計算表達式，當我們輸入字尾表達式後，能輸出運作結果。

1 public class Test {
 2 
 3     //方法：使用鍊式堆棧，設計一個算法計算表達式
 4     public static void expCaculate(LinkStack stack) throws Exception {
 5         char ch; //掃描每次輸入的字元。
 6         int x1, x2, b = 0; //x1,x2:兩個操作數 ，b字元的ASCII碼
 7         System.out.println("輸入字尾表達式并以#符号結束:");
 8         while ((ch = (char) (b = System.in.read())) != '#') {
 9             //如果是數字，說明是操作數則壓入堆棧
10             if (Character.isDigit(ch)) {
11                 stack.push(new Integer(Character.toString(ch)));
12             }
13             //如果不是數字，說明是運算符
14             else {
15                 x2 = ((Integer) stack.pop()).intValue();
16                 x1 = ((Integer) stack.pop()).intValue();
17                 switch (ch) {
18                     case '+':
19                         x1 += x2;
20                         break;
21                     case '-':
22                         x1 -= x2;
23                         break;
24                     case '*':
25                         x1 *= x2;
26                         break;
27                     case '/':
28                         if (x2 == 0) {
29                             throw new Exception("分母不能為零！");
30                         } else {
31                             x1 /= x2;
32                         }
33                         break;
34                 }
35                 stack.push(new Integer(x1));
36             }
37         }
38         System.out.println("字尾表達式計算結果是：" + stack.getTop());
39     }
40 
41     public static void main(String[] args) throws Exception {
42         LinkStack stack = new LinkStack();
43         //(2+3)*(3-1)/2=5的字尾表達式為：23+31-*2/
44         //方法：鍵盤輸入字尾表達式，輸出的得到計算結果
45         Test.expCaculate(stack);
46 
47     }
48 }

資料結構Java實作05----棧：順序棧和鍊式堆棧

1 public interface Stack {
 2 
 3     //入棧
 4     public void push(Object obj) throws Exception;
 5 
 6     //出棧
 7     public Object pop() throws Exception;
 8 
 9     //擷取棧頂元素
10     public Object getTop() throws Exception;
11 
12     //判斷棧是否為空
13      public boolean isEmpty();
14 }

資料結構Java實作05----棧：順序棧和鍊式堆棧

1 //順序棧
 2 public class SequenceStack implements Stack {
 3 
 4     Object[] stack; //對象數組（棧用數組來實作）
 5     final int defaultSize = 10; //預設最大長度
 6     int top; //棧頂位置（的一個下标）:其實可以了解成棧的實際長度
 7     int maxSize; //最大長度
 8 
 9     //如果用無參構造的話，就設定預設長度
10     public SequenceStack() {
11         init(defaultSize);
12     }
13 
14     //如果使用帶參構造的話，就調用指定的最大長度
15     public SequenceStack(int size) {
16         init(size);
17     }
18 
19     public void init(int size) {
20         this.maxSize = size;
21         top = 0;
22         stack = new Object[size];
23     }
24 
25     //擷取棧頂元素
26     @Override
27     public Object getTop() throws Exception {
28         // TODO Auto-generated method stub
29         if (isEmpty()) {
30             throw new Exception("堆棧為空！");
31         }
32 
33         return stack[top - 1];
34     }
35 
36     //判斷棧是否為空
37     @Override
38     public boolean isEmpty() {
39         // TODO Auto-generated method stub
40         return top == 0;
41     }
42 
43     //出棧操作
44     @Override
45     public Object pop() throws Exception {
46         // TODO Auto-generated method stub
47         if (isEmpty()) {
48             throw new Exception("堆棧為空！");
49         }
50         top--;
51 
52         return stack[top];
53     }
54 
55     //入棧操作
56     @Override
57     public void push(Object obj) throws Exception {
58         // TODO Auto-generated method stub
59         //首先判斷棧是否已滿
60         if (top == maxSize) {
61             throw new Exception("堆棧已滿！");
62         }
63         stack[top] = obj;
64         top++;
65     }
66 }

資料結構Java實作05----棧：順序棧和鍊式堆棧

1 import java.util.Scanner;
 2 
 3 public class Test {
 4     public static void main(String[] args) throws Exception {
 5         SequenceStack stack = new SequenceStack(10);
 6 
 7         Scanner in = new Scanner(System.in);
 8         int temp;
 9         for (int i = 0; i < 10; i++) {
10             System.out.println("請輸入第" + (i + 1) + "個整數：");
11             temp = in.nextInt();
12             stack.push(temp);
13         }
14 
15         //周遊輸出
16         while (!stack.isEmpty()) {
17             System.out.println(stack.pop());
18         }
19     }
20 }

資料結構Java實作05----棧：順序棧和鍊式堆棧

1 public class StringTest {
 2 
 3     public static void main(String[] args) {
 4 
 5         //s1 和 s2 其實是同一個對象。對象的引用存放在棧中，對象存放在方法區的字元串常量池
 6         String s1 = "china";
 7         String s2 = "china";
 8 
 9         //凡是用new關鍵建立的對象，都是在堆記憶體中配置設定空間。
10         String s3 = new String("china");
11 
12         //凡是new出來的對象，絕對是不同的兩個對象。
13         String s4 = new String("china");
14 
15         System.out.println(s1 == s2);  //true
16         System.out.println(s1 == s3);
17         System.out.println(s3 == s4);
18         System.out.println(s3.equals(s4));
19 
20         System.out.println("\n-----------------\n");
21       /*String很特殊，重寫從父類繼承過來的hashCode方法，使得兩個
22        *如果字元串裡面的内容相等，那麼hashCode也相等。
23        **/
24 
25         //hashCode相同
26         System.out.println(s3.hashCode());  //hashCode為94631255
27         System.out.println(s4.hashCode());  //hashCode為94631255
28 
29         //identityHashCode方法用于擷取原始的hashCode
30         //如果原始的hashCode不同，表明确實是不同的對象
31 
32         //原始hashCode不同
33         System.out.println(System.identityHashCode(s3)); //2104928456
34         System.out.println(System.identityHashCode(s4)); //2034442961
35 
36         System.out.println("\n-----------------\n");
37 
38         //hashCode相同
39         System.out.println(s1.hashCode());  //94631255
40         System.out.println(s2.hashCode());  //94631255
41 
42         //原始hashCode相同：表明确實是同一個對象
43         System.out.println(System.identityHashCode(s1));  //648217993
44         System.out.println(System.identityHashCode(s2));  //648217993
45     }
46 }

資料結構Java實作05----棧：順序棧和鍊式堆棧

上面的代碼中，注釋已經标明了運作的結果。通過運作結果我們可以看到，s3和s4的字元串内容相同，但他們是兩個不同的對象，由于String類重寫了hashCode方法，他們的hashCode相同，但原始的hashCode是不同的。

資料結構Java實作05----棧：順序棧和鍊式堆棧

1 //結點類
 2 public class Node {
 3 
 4     Object element; //資料域
 5     Node next;  //指針域
 6 
 7     //頭結點的構造方法
 8     public Node(Node nextval) {
 9         this.next = nextval;
10     }
11 
12     //非頭結點的構造方法
13     public Node(Object obj, Node nextval) {
14         this.element = obj;
15         this.next = nextval;
16     }
17     
18     //獲得目前結點的後繼結點
19     public Node getNext() {
20         return this.next;
21     }
22 
23     //獲得目前的資料域的值
24     public Object getElement() {
25         return this.element;
26     }
27 
28     //設定目前結點的指針域
29     public void setNext(Node nextval) {
30         this.next = nextval;
31     }
32 
33     //設定目前結點的資料域
34     public void setElement(Object obj) {
35         this.element = obj;
36     }
37 
38     public String toString() {
39         return this.element.toString();
40     }
41 }

資料結構Java實作05----棧：順序棧和鍊式堆棧

1 //棧接口
 2 public interface Stack {
 3 
 4     //入棧
 5     public void push(Object obj) throws Exception;
 6 
 7     //出棧
 8     public Object pop() throws Exception;
 9 
10     //獲得棧頂元素
11     public Object getTop() throws Exception;
12 
13     //判斷棧是否為空
14     public boolean isEmpty();
15 }

資料結構Java實作05----棧：順序棧和鍊式堆棧

1 public class LinkStack implements Stack {
 2 
 3     Node head;  //棧頂指針
 4     int size;  //結點的個數
 5 
 6     public LinkStack() {
 7         head = null;
 8         size = 0;
 9     }
10 
11     @Override
12     public Object getTop() throws Exception {
13         // TODO Auto-generated method stub
14         return head.getElement();
15     }
16 
17     @Override
18     public boolean isEmpty() {
19         // TODO Auto-generated method stub
20         return head == null;
21     }
22 
23     @Override
24     public Object pop() throws Exception {
25         // TODO Auto-generated method stub
26         if (isEmpty()) {
27             throw new Exception("棧為空！");
28         }
29         Object obj = head.getElement();
30         head = head.getNext();
31         size--;
32         return obj;
33     }
34 
35     @Override
36     public void push(Object obj) throws Exception {
37         // TODO Auto-generated method stub
38         head = new Node(obj, head);
39         size++;
40     }

資料結構Java實作05----棧：順序棧和鍊式堆棧

1 import java.util.Scanner;
 2 
 3 public class Test {
 4 
 5     public static void main(String[] args) throws Exception {
 6         //SequenceStack stack = new SequenceStack(10);
 7         LinkStack stack = new LinkStack();
 8         Scanner in = new Scanner(System.in);
 9         int temp;
10         for (int i = 0; i < 10; i++) {
11             System.out.println("請輸入第" + (i + 1) + "個整數：");
12             temp = in.nextInt();
13             stack.push(temp);
14         }
15         //周遊輸出
16         while (!stack.isEmpty()) {
17             System.out.println(stack.pop());
18         }
19     }
20 }

資料結構Java實作05----棧：順序棧和鍊式堆棧

1 public class Test {
 2 
 3     //方法：将字元串轉化為字元串數組
 4     public static String[] expToStringArray(String exp) {
 5         int n = exp.length();
 6         String[] arr = new String[n];
 7         for (int i = 0; i < arr.length; i++) {
 8             arr[i] = exp.substring(i, i + 1);
 9         }
10         return arr;
11     }
12 
13     //方法：括号比對問題的檢測
14     public static void signCheck(String exp) throws Exception {
15         SequenceStack stack = new SequenceStack();
16         String[] arr = Test.expToStringArray(exp);
17         for (int i = 0; i < arr.length; i++) {
18             if (arr[i].equals("(") || arr[i].equals("[") || arr[i].equals("{")) { //當碰到都是左邊的括号的時候，統統壓進棧
19                 stack.push(arr[i]);
20             } else if (arr[i].equals(")") && !stack.isEmpty() && stack.getTop().equals("(")) { //當碰到了右小括号時，如果比對正确，就将左小括号出棧
21                 stack.pop();
22             } else if (arr[i].equals(")") && !stack.isEmpty() && !stack.getTop().equals("(")) {
23                 System.out.println("左右括号比對次序不正确！");
24                 return;
25             } else if (arr[i].equals("]") && !stack.isEmpty() && stack.getTop().equals("[")) {
26                 stack.pop();
27             } else if (arr[i].equals("]") && !stack.isEmpty() && !stack.getTop().equals("[")) {
28                 System.out.println("左右括号比對次序不正确！");
29                 return;
30             } else if (arr[i].equals("}") && !stack.isEmpty() && stack.getTop().equals("{")) {
31                 stack.pop();
32             } else if (arr[i].equals("}") && !stack.isEmpty() && !stack.getTop().equals("{")) {
33                 System.out.println("左右括号比對次序不正确！");
34                 return;
35             } else if (arr[i].equals(")") || arr[i].equals("]") || arr[i].equals("}") && stack.isEmpty()) {
36                 System.out.println("右括号多于左括号！");
37                 return;
38             }
39         }
40         if (!stack.isEmpty()) {
41             System.out.println("左括号多于右括号！");
42         } else {
43             System.out.println("括号比對正确！");
44         }
45     }
46 
47 
48     public static void main(String[] args) throws Exception {
49 
50         String str = "([(a+b)-(c*e)]+{a+b}";
51         //括号比對的檢測
52         Test.signCheck(str);
53     }
54 }

資料結構Java實作05----棧：順序棧和鍊式堆棧

1 public class Test {
 2 
 3     //方法：使用鍊式堆棧，設計一個算法計算表達式
 4     public static void expCaculate(LinkStack stack) throws Exception {
 5         char ch; //掃描每次輸入的字元。
 6         int x1, x2, b = 0; //x1,x2:兩個操作數 ，b字元的ASCII碼
 7         System.out.println("輸入字尾表達式并以#符号結束:");
 8         while ((ch = (char) (b = System.in.read())) != '#') {
 9             //如果是數字，說明是操作數則壓入堆棧
10             if (Character.isDigit(ch)) {
11                 stack.push(new Integer(Character.toString(ch)));
12             }
13             //如果不是數字，說明是運算符
14             else {
15                 x2 = ((Integer) stack.pop()).intValue();
16                 x1 = ((Integer) stack.pop()).intValue();
17                 switch (ch) {
18                     case '+':
19                         x1 += x2;
20                         break;
21                     case '-':
22                         x1 -= x2;
23                         break;
24                     case '*':
25                         x1 *= x2;
26                         break;
27                     case '/':
28                         if (x2 == 0) {
29                             throw new Exception("分母不能為零！");
30                         } else {
31                             x1 /= x2;
32                         }
33                         break;
34                 }
35                 stack.push(new Integer(x1));
36             }
37         }
38         System.out.println("字尾表達式計算結果是：" + stack.getTop());
39     }
40 
41     public static void main(String[] args) throws Exception {
42         LinkStack stack = new LinkStack();
43         //(2+3)*(3-1)/2=5的字尾表達式為：23+31-*2/
44         //方法：鍵盤輸入字尾表達式，輸出的得到計算結果
45         Test.expCaculate(stack);
46 
47     }
48 }

資料結構Java實作05----棧：順序棧和鍊式堆棧

資料結構Java實作05----棧：順序棧和鍊式堆棧

繼續閱讀

Java小案例——随機數猜測随機數猜測

nginx location中斜線的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

詳解STM32單片機的堆棧

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method