数据结构与算法 | 栈

定义

线性表中的一种特殊数据结构,数据只能从固定的一端插入数据或删除数据,另一端是封死的。

特点

  • FILO(First In Last Out): 先进后出
  • 栈满还存会“上溢”,栈空再取会“下溢”

分类

顺序栈

特点

  • 采用数组实现,数据在物理结构上保持连续性。

代码实现

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
package one.wangwei.algorithms.datastructures.stack.impl;

import one.wangwei.algorithms.datastructures.stack.IStack;

import java.util.Arrays;

/**
* 顺序栈
*
* @param <T>
* @author wangwei
* @date 2018/05/04
*/
public class ArrayStack<T> implements IStack<T> {

/**
* 默认大小
*/
private static final int DEFAULT_SIZE = 10;
/**
* 数组
*/
private T[] array = (T[]) new Object[DEFAULT_SIZE];
/**
* 大小
*/
private int size;

/**
* 入栈
*
* @param value
* @return
*/
@Override
public boolean push(T value) {
if (size >= array.length) {
grow();
}
array[size] = value;
size++;
return false;
}

/**
* 扩容50%
*/
private void grow() {
int growSize = size + (size << 1);
array = Arrays.copyOf(array, growSize);
}

/**
* 压缩50%
*/
private void shrink() {
int shrinkSize = size >> 1;
array = Arrays.copyOf(array, shrinkSize);
}

/**
* 出栈
*
* @return
*/
@Override
public T pop() {
if (size <= 0) {
return null;
}
T element = array[--size];
array[size] = null;

int shrinkSize = array.length >> 1;
if (shrinkSize >= DEFAULT_SIZE && shrinkSize > size) {
shrink();
}
return element;
}

/**
* 查看栈顶值
*
* @return
*/
@Override
public T peek() {
if (size <= 0) {
return null;
}
return array[size - 1];
}

/**
* 删除元素
*
* @param value
* @return
*/
@Override
public boolean remove(T value) {
if (size <= 0) {
return false;
}
for (int i = 0; i < size; i++) {
T t = array[i];
if (value == null && t == null) {
return remove(i);
}
if (value != null && value.equals(t)) {
return remove(i);
}
}
return false;
}

/**
* 移除 index 处的栈值
*
* @param index
* @return
*/
private boolean remove(int index) {
if (index < 0 || index >= size) {
throw new ArrayIndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
if (index != --size) {
System.arraycopy(array, index + 1, array, index, size - index);
}
array[size] = null;

int shrinkSize = array.length >> 1;
if (shrinkSize >= DEFAULT_SIZE && shrinkSize > size) {
shrink();
}
return true;
}

/**
* 清空栈
*/
@Override
public void clear() {
if (size <= 0) {
return;
}
for (int i = 0; i < size; i++) {
array[i] = null;
}
size = 0;
array = null;
}

/**
* 是否包含元素
*
* @param value
* @return
*/
@Override
public boolean contains(T value) {
if (size <= 0) {
return false;
}
for (int i = 0; i < size; i++) {
T t = array[i];
if (value == null && t == null) {
return true;
}
if (value != null && value.equals(t)) {
return true;
}
}
return false;
}

/**
* 栈大小
*
* @return
*/
@Override
public int size() {
return size;
}
}

查看源码

链表栈

特点

  • 用线性表的链式结构存储,数据在物理结构上非连续

代码实现

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
package one.wangwei.algorithms.datastructures.stack.impl;

import one.wangwei.algorithms.datastructures.stack.IStack;

/**
* 链表栈
*
* @param <T>
* @author wangwei
* @date 2018/05/04
*/
public class LinkedStack<T> implements IStack<T> {

private Node<T> top;
private int size;

public LinkedStack() {
this.top = null;
this.size = 0;
}

/**
* 入栈
*
* @param value
* @return
*/
@Override
public boolean push(T value) {
Node<T> newTop = new Node<>(value);
if (top == null) {
top = newTop;
} else {
Node<T> oldTop = top;
top = newTop;
oldTop.above = top;
top.below = oldTop;
}
size++;
return true;
}

/**
* 出栈
*
* @return
*/
@Override
public T pop() {
if (top == null) {
return null;
}

Node<T> needTop = top;
top = needTop.below;
if (top != null) {
top.above = null;
}

T needValue = needTop.element;
needTop = null;

size--;
return needValue;
}

/**
* 查看栈顶值
*
* @return
*/
@Override
public T peek() {
return top == null ? null : top.element;
}

/**
* 删除元素
*
* @param value
* @return
*/
@Override
public boolean remove(T value) {
if (top == null) {
return false;
}
Node<T> x = top;
if (value == null) {
while (x != null && x.element != null) {
x = x.below;
}
} else {
while (x != null && !value.equals(x.element)) {
x = x.below;
}
}
return remove(x);
}

/**
* 删除一个节点
*
* @param node
* @return
*/
private boolean remove(Node<T> node) {
if (node == null) {
return false;
}
Node<T> above = node.above;
Node<T> below = node.below;

// 删除中间元素
if (above != null && below != null) {
above.below = below;
below.above = above;
}
// 删除top元素
else if (above == null && below != null) {
top = below;
top.above = null;
} else if (above != null && below == null) {
above.below = null;
below = null;
} else {
top = null;
}
node = null;
size--;
return true;
}

/**
* 清空栈
*/
@Override
public void clear() {
if (top == null) {
return;
}
for (Node<T> x = top; x != null; ) {
Node<T> below = x.below;
x.element = null;
x.above = null;
x.below = null;
x = below;
}
top = null;
size = 0;
}

/**
* 是否包含元素
*
* @param value
* @return
*/
@Override
public boolean contains(T value) {
if (value == null) {
for (Node<T> x = top; x != null; x = x.below) {
if (x.element == null) {
return true;
}
}
} else {
for (Node<T> x = top; x != null; x = x.below) {
if (x.element.equals(value)) {
return true;
}
}
}
return false;
}

/**
* 栈大小
*
* @return
*/
@Override
public int size() {
return size;
}

/**
* 节点
*
* @param <T>
*/
private static class Node<T> {
private T element;
private Node<T> above;
private Node<T> below;

public Node(T element) {
this.element = element;
}
}
}

查看源码

参考资料

请我喝杯咖啡吧~