本篇是java數(shù)據(jù)結(jié)構(gòu)與算法的第2篇，從本篇開始我們將來了解棧的設(shè)計(jì)與實(shí)現(xiàn)，以下是本篇的相關(guān)知識點(diǎn)：
棧的抽象數(shù)據(jù)類型順序棧的設(shè)計(jì)與實(shí)現(xiàn)鏈?zhǔn)綏５脑O(shè)計(jì)與實(shí)現(xiàn)棧的應(yīng)用
棧的抽象數(shù)據(jù)類型
棧是一種用于存儲(chǔ)數(shù)據(jù)的簡單數(shù)據(jù)結(jié)構(gòu)，有點(diǎn)類似鏈表或者順序表（統(tǒng)稱線性表），棧與線性表的最大區(qū)別是數(shù)據(jù)的存取的操作，我們可以這樣認(rèn)為棧(stack)是一種特殊的線性表，其插入和刪除操作只允許在線性表的一端進(jìn)行，一般而言，把允許操作的一端稱為棧頂(top)，不可操作的一端稱為棧底(bottom)，同時(shí)把插入元素的操作稱為入棧(push),刪除元素的操作稱為出棧(pop)。若棧中沒有任何元素，則稱為空棧，棧的結(jié)構(gòu)如下圖：
由圖我們可看成棧只能從棧頂存取元素，同時(shí)先進(jìn)入的元素反而是后出，而棧頂永遠(yuǎn)指向棧內(nèi)最頂部的元素。到此可以給出棧的正式定義：棧(stack)是一種有序特殊的線性表，只能在表的一端(稱為棧頂，top，總是指向棧頂元素)執(zhí)行插入和刪除操作，最后插入的元素將第一個(gè)被刪除，因此棧也稱為后進(jìn)先出(last in first out,lifo)或先進(jìn)后出(first in last out filo)的線性表。棧的基本操作創(chuàng)建棧，判空，入棧，出棧，獲取棧頂元素等，注意棧不支持對指定位置進(jìn)行刪除，插入，其接口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
|
/** 棧接口抽象數(shù)據(jù)類型*/public interface stack<t> { /** * 棧是否為空 * @return */ boolean isempty(); /** * data元素入棧 * @param data */ void push(t data); /** * 返回棧頂元素,未出棧 * @return */ t peek(); /** * 出棧,返回棧頂元素,同時(shí)從棧中移除該元素 * @return */ t pop();} |
順序棧的設(shè)計(jì)與實(shí)現(xiàn)
順序棧，顧名思義就是采用順序表實(shí)現(xiàn)的的棧，順序棧的內(nèi)部以順序表為基礎(chǔ)，實(shí)現(xiàn)對元素的存取操作，當(dāng)然我們還可以采用內(nèi)部數(shù)組實(shí)現(xiàn)順序棧，在這里我們使用內(nèi)部數(shù)據(jù)組來實(shí)現(xiàn)棧，至于以順序表作為基礎(chǔ)的棧實(shí)現(xiàn)，將以源碼提供。這里先聲明一個(gè)順序棧其代碼如下，實(shí)現(xiàn)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
|
/* * 順序棧的實(shí)現(xiàn) */public class seqstack<t> implements stack<t>,serializable { private static final long serialversionuid = -5413303117698554397l; /** * 棧頂指針,-1代表空棧 */ private int top=-1; /** * 容量大小默認(rèn)為10 */ private int capacity=10; /** * 存放元素的數(shù)組 */ 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
|
/** * 添加元素,從棧頂(數(shù)組尾部)插入 * 容量不足時(shí)，需要擴(kuò)容 * @param data */@overridepublic void push(t data) { //判斷容量是否充足 if(array.length==size) ensurecapacity(size*2+1);//擴(kuò)容 //從棧頂添加元素 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--]; } |
到此，順序棧的主要操作已實(shí)現(xiàn)完，是不是發(fā)現(xiàn)很簡單，確實(shí)如此，棧的主要操作就這樣，當(dāng)然我們也可以通過前一篇介紹的myarraylist作為基礎(chǔ)來實(shí)現(xiàn)順序棧，這個(gè)也比較簡單，后面也會(huì)提供帶代碼，這里就不過多啰嗦了。下面給出順序棧的整體實(shí)現(xiàn)代碼：
|
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;/* * 順序棧的實(shí)現(xiàn) */public class seqstack<t> implements stack<t>,serializable { private static final long serialversionuid = -5413303117698554397l; /** * 棧頂指針,-1代表空棧 */ private int top=-1; /** * 容量大小默認(rèn)為10 */ private int capacity=10; /** * 存放元素的數(shù)組 */ 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; } /** * 添加元素,從棧頂(數(shù)組尾部)插入 * @param data */ @override public void push(t data) { //判斷容量是否充足 if(array.length==size) ensurecapacity(size*2+1);//擴(kuò)容 //從棧頂添加元素 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--]; } /** * 擴(kuò)容的方法 * @param capacity */ public void ensurecapacity(int capacity) { //如果需要拓展的容量比現(xiàn)在數(shù)組的容量還小,則無需擴(kuò)容 if (capacity<size) return; t[] old = array; array = (t[]) new object[capacity]; //復(fù)制元素 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()); }} |
鏈?zhǔn)綏５脑O(shè)計(jì)與實(shí)現(xiàn)
了解完順序棧，我們接著來看看鏈?zhǔn)綏＃^的鏈?zhǔn)綏＃╨inked stack），就是采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的棧，由于我們操作的是棧頂一端，因此這里采用單鏈表（不帶頭結(jié)點(diǎn)）作為基礎(chǔ)，直接實(shí)現(xiàn)棧的添加，獲取，刪除等主要操作即可。其操作過程如下圖：
從圖可以看出，無論是插入還是刪除直接操作的是鏈表頭部也就是棧頂元素，因此我們只需要使用不帶頭結(jié)點(diǎn)的單鏈表即可。代碼實(shí)現(xiàn)如下，比較簡單，不過多分析了：
|
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;/* * 棧的鏈?zhǔn)綄?shí)現(xiàn) */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){//調(diào)用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()); } }} |
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持服務(wù)器之家。
原文鏈接：http://www.cnblogs.com/ECJTUACM-873284962/p/7506864.html
