本篇是java數據結構與算法的第2篇，從本篇開始我們將來了解棧的設計與實現，以下是本篇的相關知識點：
棧的抽象數據類型順序棧的設計與實現鏈式棧的設計與實現棧的應用
棧的抽象數據類型
棧是一種用于存儲數據的簡單數據結構，有點類似鏈表或者順序表（統稱線性表），棧與線性表的最大區別是數據的存取的操作，我們可以這樣認為棧(stack)是一種特殊的線性表，其插入和刪除操作只允許在線性表的一端進行，一般而言，把允許操作的一端稱為棧頂(top)，不可操作的一端稱為棧底(bottom)，同時把插入元素的操作稱為入棧(push),刪除元素的操作稱為出棧(pop)。若棧中沒有任何元素，則稱為空棧，棧的結構如下圖：
由圖我們可看成棧只能從棧頂存取元素，同時先進入的元素反而是后出，而棧頂永遠指向棧內最頂部的元素。到此可以給出棧的正式定義：棧(stack)是一種有序特殊的線性表，只能在表的一端(稱為棧頂，top，總是指向棧頂元素)執行插入和刪除操作，最后插入的元素將第一個被刪除，因此棧也稱為后進先出(last in first out,lifo)或先進后出(first in last out filo)的線性表。棧的基本操作創建棧，判空，入棧，出棧，獲取棧頂元素等，注意棧不支持對指定位置進行刪除，插入，其接口stack聲明如下：
|
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
|
/** 棧接口抽象數據類型*/public interface stack<t> { /** * 棧是否為空 * @return */ boolean isempty(); /** * data元素入棧 * @param data */ void push(t data); /** * 返回棧頂元素,未出棧 * @return */ t peek(); /** * 出棧,返回棧頂元素,同時從棧中移除該元素 * @return */ t pop();} |
順序棧的設計與實現
順序棧，顧名思義就是采用順序表實現的的棧，順序棧的內部以順序表為基礎，實現對元素的存取操作，當然我們還可以采用內部數組實現順序棧，在這里我們使用內部數據組來實現棧，至于以順序表作為基礎的棧實現，將以源碼提供。這里先聲明一個順序棧其代碼如下，實現stack和serializable接口：
|
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
|
/* * 順序棧的實現 */public class seqstack<t> implements stack<t>,serializable { private static final long serialversionuid = -5413303117698554397l; /** * 棧頂指針,-1代表空棧 */ private int top=-1; /** * 容量大小默認為10 */ private int capacity=10; /** * 存放元素的數組 */ private t[] array; private int size; public seqstack(int capacity){ array = (t[]) new object[capacity]; } public seqstack(){ array= (t[]) new object[this.capacity]; } //.......省略其他代碼} |
其獲取棧頂元素值的peek操作過程如下圖（未刪除只獲取值）：
以上是獲取棧頂元素的操作，代碼如下：
|
1
2
3
4
5
6
7
8
9
10
|
/** * 獲取棧頂元素的值,不刪除 * @return */ @override public t peek() { if(isempty()) new emptystackexception(); return array[top]; } |
從棧添加元素的過程如下（更新棧頂top指向）：
以上是入棧操作，代碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
/** * 添加元素,從棧頂(數組尾部)插入 * 容量不足時，需要擴容 * @param data */@overridepublic void push(t data) { //判斷容量是否充足 if(array.length==size) ensurecapacity(size*2+1);//擴容 //從棧頂添加元素 array[++top]=data; } |
棧彈出棧頂元素的過程如下（刪除并獲取值）：
以上是出棧操作，代碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
|
/** * 從棧頂(順序表尾部)刪除 * @return */ @override public t pop() { if(isempty()) new emptystackexception(); size--; return array[top--]; } |
到此，順序棧的主要操作已實現完，是不是發現很簡單，確實如此，棧的主要操作就這樣，當然我們也可以通過前一篇介紹的myarraylist作為基礎來實現順序棧，這個也比較簡單，后面也會提供帶代碼，這里就不過多啰嗦了。下面給出順序棧的整體實現代碼：
|
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
|
import java.io.serializable;import java.util.emptystackexception;/* * 順序棧的實現 */public class seqstack<t> implements stack<t>,serializable { private static final long serialversionuid = -5413303117698554397l; /** * 棧頂指針,-1代表空棧 */ private int top=-1; /** * 容量大小默認為10 */ private int capacity=10; /** * 存放元素的數組 */ private t[] array; private int size; public seqstack(int capacity){ array = (t[]) new object[capacity]; } public seqstack(){ array= (t[]) new object[this.capacity]; } public int size(){ return size; } @override public boolean isempty() { return this.top==-1; } /** * 添加元素,從棧頂(數組尾部)插入 * @param data */ @override public void push(t data) { //判斷容量是否充足 if(array.length==size) ensurecapacity(size*2+1);//擴容 //從棧頂添加元素 array[++top]=data; size++; } /** * 獲取棧頂元素的值,不刪除 * @return */ @override public t peek() { if(isempty()) new emptystackexception(); return array[top]; } /** * 從棧頂(順序表尾部)刪除 * @return */ @override public t pop() { if(isempty()) new emptystackexception(); size--; return array[top--]; } /** * 擴容的方法 * @param capacity */ public void ensurecapacity(int capacity) { //如果需要拓展的容量比現在數組的容量還小,則無需擴容 if (capacity<size) return; t[] old = array; array = (t[]) new object[capacity]; //復制元素 for (int i=0; i<size ; i++) array[i]=old[i]; } public static void main(string[] args){ seqstack<string> s=new seqstack<>(); s.push("a"); s.push("b"); s.push("c"); system.out.println("size->"+s.size()); int l=s.size();//size 在減少,必須先記錄 for (int i=0;i<l;i++){ system.out.println("s.pop->"+s.pop()); } system.out.println("s.peek->"+s.peek()); }} |
鏈式棧的設計與實現
了解完順序棧，我們接著來看看鏈式棧，所謂的鏈式棧（linked stack），就是采用鏈式存儲結構的棧，由于我們操作的是棧頂一端，因此這里采用單鏈表（不帶頭結點）作為基礎，直接實現棧的添加，獲取，刪除等主要操作即可。其操作過程如下圖：
從圖可以看出，無論是插入還是刪除直接操作的是鏈表頭部也就是棧頂元素，因此我們只需要使用不帶頭結點的單鏈表即可。代碼實現如下，比較簡單，不過多分析了：
|
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
66
67
68
69
70
71
72
73
74
75
76
77
|
import com.zejian.structures.linkedlist.singlelinked.node;import java.io.serializable;/* * 棧的鏈式實現 */public class linkedstack<t> implements stack<t> ,serializable{ private static final long serialversionuid = 1911829302658328353l; private node<t> top; private int size; public linkedstack(){ this.top=new node<>(); } public int size(){ return size; } @override public boolean isempty() { return top==null || top.data==null; } @override public void push(t data) { if (data==null){ throw new stackexception("data can\'t be null"); } if(this.top==null){//調用pop()后top可能為null this.top=new node<>(data); }else if(this.top.data==null){ this.top.data=data; }else { node<t> p=new node<>(data,this.top); top=p;//更新棧頂 } size++; } @override public t peek() { if(isempty()){ throw new emptystackexception("stack empty"); } return top.data; } @override public t pop() { if(isempty()){ throw new emptystackexception("stack empty"); } t data=top.data; top=top.next; size--; return data; } //測試 public static void main(string[] args){ linkedstack<string> sl=new linkedstack<>(); sl.push("a"); sl.push("b"); sl.push("c"); int length=sl.size(); for (int i = 0; i < length; i++) { system.out.println("sl.pop->"+sl.pop()); } }} |
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持服務器之家。
原文鏈接：http://www.cnblogs.com/ECJTUACM-873284962/p/7506864.html
