鏈式實現：
在棧的一段添加和刪除元素，在棧中維護一個指向棧頂的結點和一個count變量指示棧的大小：
private LinearNode top; //指向棧頂
private int count;//標記棧的大小
每次出棧和壓棧在鏈表的表頭：（也可以再表尾，實現方式不一樣而已）
top--->元素1--->元素2--->元素3.........
實現（附帶測試main）：
LinkedStack
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
package Stack;import Bag.LinearNode;//為了重點來實現算法，將異常情況直接打印出然后退出程序，不再聲明異常類public class LinkedStack implements StackADT { private LinearNode top; //指向棧頂 private int count;//標記棧的大小 public static void main(String[] args){ LinkedStack stack = new LinkedStack(); System.out.println("將0到10依次壓棧"); for(int i = 0;i < 10;i++) stack.push(i); System.out.println("連續執行5次出棧操作"); for(int i = 0;i < 5;i++) stack.pop(); System.out.println("棧為空嗎？： " + stack.isEmpty()); System.out.println("棧的大小為： " + stack.size()); System.out.println("棧頂元素為： " + stack.top.getElement()); System.out.println("棧頂元素為： " + stack.peek()); } public LinkedStack() { top = null; count = 0; } public int size() { return count; } public boolean isEmpty() { return (size() == 0); } public void push(Object element) { LinearNode node = new LinearNode(element); node.setNext(top); top = node; count++; } public Object pop() { if(isEmpty()) { System.out.println("stack is empty!"); System.exit(1); } Object result = top.getElement(); top = top.getNext(); count--; return result; } public Object peek() { Object result = top.getElement(); return result; }} |
運行結果：
將0到10依次壓棧
連續執行5次出棧操作
棧為空嗎？： false
棧的大小為： 5
棧頂元素為： 4
棧頂元素為： 4
數組實現：
棧底總是數組下標為0的位置，入棧出棧從數組下標的最后一個元素開始：
|
1
2
|
private Object[] contents;private int top;//top標記下一個入棧的位置，同時也表示棧的容量大小，跟鏈式實現的count比較一下?。?！ |
實現（附帶測試main）：
ArrayStack
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
package Stack;public class ArrayStack implements StackADT { private Object[] contents; private int top;//top標記下一個入棧的位置，同時也表示棧的容量大小，跟鏈式實現的count比較一下?。?！ private static int SIZE = 10; public ArrayStack() { contents = new Object[SIZE]; top = 0; } public void expand(){//借助于申請一個輔助空間,每次擴展容量一倍 Object[] larger = new Object[size()*2]; for(int index = 0;index < top;index++) larger[index] = contents[index]; contents = larger; } public int size() { return top; } public boolean isEmpty() { return (size() == 0); } public void push(Object element) { //if(isEmpty()) //expand(); if(top == contents.length) expand(); contents[top] = element; top++; } public Object pop() { if(isEmpty()) { System.out.println("stack is empty!"); System.exit(1); } Object result = contents[top-1]; contents[top-1] = null;//出棧 top--; return result; /*書上這樣寫簡便一點：：： * top--; * Object result = contents[top]; * contents[top] = null;*/ } public Object peek() { Object result; if(isEmpty()) result = null; else result = contents[top-1]; return result; } public static void main(String[] args) { ArrayStack stack = new ArrayStack(); System.out.println("將0到24依次壓棧，然后連續10次出棧"); for(int i = 0;i < 25;i++) stack.push(i); for(int i = 0;i < 10;i++) stack.pop(); System.out.println("棧的大小為： " + stack.size()); System.out.println("棧為空嗎？： " + stack.isEmpty()); System.out.println("棧頂元素為： " + stack.peek()); }} |
運行結果：
將0到24依次壓棧，然后連續10次出棧
棧的大小為： 15
棧為空嗎？： false
棧頂元素為： 14
使用集合LinkedList來模擬棧
方法
java的泛型可以讓LinkedList模擬存儲各種數據類型的棧，包括int，double，String，Object等等，介紹一下幾種用到的API接口：
入棧
|
1
|
void addFirst(E e); // 將指定元素插入此列表的開頭 |
獲取棧頂元素
|
1
|
E getFirst(); // 返回此列表的第一個元素 |
出棧
|
1
|
E removeFirst(); // 移除并返回此列表第一個元素 |
判?？?/p>
|
1
|
boolean isEmpty(); // 判斷棧空 |
示例代碼
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
import java.util.LinkedList; import java.util.NoSuchElementException; public class SimulateStack { private LinkedList<Integer> stack = new LinkedList<Integer>(); public boolean isEmpty() { return this.stack.isEmpty(); } public void push(int data) { this.stack.addFirst(data); } public int pop() throws NoSuchElementException{ return this.stack.removeFirst(); } public int getTop() throws NoSuchElementException{ return this.stack.getFirst(); } public static void main(String args[]) { SimulateStack s = new SimulateStack(); s.push(1); s.push(2); s.push(3); while (! s.isEmpty()) { int data = s.getTop(); System.out.println(data); s.pop(); } } } |
