近来复习数据结构，自己动手实现了栈。栈是一种限制插入和删除只能在一个位置上的表。最基本的操作是进栈和出栈，因此，又被叫作“先进后出”表。
首先了解下栈的概念：
栈是限定仅在表头进行插入和删除操作的线性表。有时又叫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