近來復習數據結構，自己動手實現了棧。棧是一種限制插入和刪除只能在一個位置上的表。最基本的操作是進棧和出棧，因此，又被叫作“先進后出”表。
首先了解下棧的概念：
棧是限定僅在表頭進行插入和刪除操作的線性表。有時又叫lifo（后進先出表）。要搞清楚這個概念，首先要明白”棧“原來的意思，如此才能把握本質。
"棧“者,存儲貨物或供旅客住宿的地方,可引申為倉庫、中轉站，所以引入到計算機領域里，就是指數據暫時存儲的地方，所以才有進棧、出棧的說法。
實現方式是這樣的：首先定義了一個接口，然后通過這個接口實現了線性棧和鏈式棧，代碼比較簡單，如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
package com.peter.java.dsa.interfaces;/** * 棧操作定義 * * @author peter pan */public interface stack<t> { /* 判空 */ boolean isempty(); /* 清空棧 */ void clear(); /* 彈棧 */ t pop(); /* 入棧 */ boolean push(t data); /* 棧的長度 */ int length(); /* 查看棧頂的元素，但不移除它 */ t peek(); /* 返回對象在棧中的位置 */ int search(t data);} |
線性棧：以數組的方式實現。
|
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
|
package com.peter.java.dsa.common;import com.peter.java.dsa.interfaces.stack;/** * 線性棧 * * @author peter pan */public class linearstack<t> implements stack<t> { @suppresswarnings("unchecked") private t[] t = (t[]) new object[16]; private int size = 0; @override public boolean isempty() { // todo auto-generated method stub return size == 0; } @override public void clear() { // todo auto-generated method stub for (int i = 0; i < t.length; i++) { t[i] = null; } size = 0; } @override public t pop() { // todo auto-generated method stub if (size == 0) { return null; } t tmp = t[size - 1]; t[size - 1] = null; size--; return tmp; } @override public boolean push(t data) { // todo auto-generated method stub if (size >= t.length) { resize(); } t[size++] = data; return true; } @override public int length() { // todo auto-generated method stub return size; } @override public t peek() { // todo auto-generated method stub if (size == 0) { return null; } else { return t[size - 1]; } } /* return index of data, return -1 if no data */ @override public int search(t data) { // todo auto-generated method stub int index = -1; for (int i = 0; i < t.length; i++) { if (t[i].equals(data)) { index = i; break; } } return index; } @suppresswarnings("unchecked") private void resize() { t[] tmp = (t[]) new object[t.length * 2]; for (int i = 0; i < t.length; i++) { tmp[i] = t[i]; t[i] = null; } t = tmp; tmp = null; } /* from the left to the right is from the top to the bottom of the stack */ @override public string tostring() { // todo auto-generated method stub stringbuffer buffer = new stringbuffer(); buffer.append("linear stack content:["); for (int i = t.length - 1; i > -1; i--) { buffer.append(t[i].tostring() + ","); } buffer.append("]"); buffer.replace(buffer.lastindexof(","), buffer.lastindexof(",") + 1, ""); return buffer.tostring(); }} |
鏈式棧：通過單鏈表進行實現。
|
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
|
package com.peter.java.dsa.common;import com.peter.java.dsa.interfaces.stack;public class linkedstack<t> implements stack<t> { private node top; private int size; @override public boolean isempty() { // todo auto-generated method stub return size == 0; } @override public void clear() { // todo auto-generated method stub top = null; size = 0; } @override public t pop() { // todo auto-generated method stub t topvalue = null; if (top != null) { topvalue = top.data; node oldtop = top; top = top.prev; oldtop.prev = null; size--; } return topvalue; } @override public boolean push(t data) { // todo auto-generated method stub node oldtop = top; top = new node(data); top.prev = oldtop; size++; return true; } @override public int length() { // todo auto-generated method stub return size; } @override public t peek() { // todo auto-generated method stub t topvalue = null; if (top != null) { topvalue = top.data; } return topvalue; } @override public int search(t data) { // todo auto-generated method stub int index = -1; node tmp = top; for (int i = size - 1; i > -1; i--) { if (tmp.data.equals(data)) { index = i; break; } else { tmp = tmp.prev; } } tmp = null; return index; } @override public string tostring() { // todo auto-generated method stub stringbuffer buffer = new stringbuffer(); buffer.append("linked stack content:["); node tmp = top; for (int i = 0; i < size - 1; i++) { buffer.append(tmp.tostring() + ","); tmp = tmp.prev; } tmp = null; buffer.append("]"); buffer.replace(buffer.lastindexof(","), buffer.lastindexof(",") + 1, ""); return super.tostring(); } private class node { t data; node prev; public node(t data) { // todo auto-generated constructor stub this.data = data; } }} |
學習還在進行中，以后會繼續更新代碼。
就是本文關于java語言實現數據結構棧代碼詳解的全部內容，希望對大家有所幫助。感興趣的朋友可以繼續參閱本站其他相關專題，如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！
原文鏈接：http://www.cnblogs.com/littlepanpc/p/3436419.html
