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