数据结构之栈
栈（stack）又名堆栈，仅能在表尾进行插入和删除操作的线性表，这一端被称为栈顶，另一端称为栈底，向一个栈插入新元素又称作入栈，从一个栈删除元素称作出栈。 栈遵守先进后出,后进先出的原则(LIFO)。
# 入栈和出栈
# 栈的分类
栈中每一个节点称为栈帧，栈作为线性表，栈帧有两种存储形式：
- 顺序存储结构
- 链式存储结构
# 顺序存储结构
# Stack
参照顺序存储的表现形式，我们使用数组来存储栈帧数据, 先定义一个栈类：
// 栈(堆栈)stack
// 先进后出,后进先去
function Stack() {
// 栈数据
this.data = [];
}
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
# 入栈
入栈直接向数组push()向数组末尾添加元素：
// 入栈
this.push = function(data) {
this.data.push(data);
}
1
2
3
4
2
3
4
# 出栈
出栈直接使用数组pop方法删除并返回最后一个元素：
this.pop = function() {
if (this.data.length == 0) return null;
else return this.data.pop();
}
1
2
3
4
2
3
4
# 清空栈
清空栈即将数组清空：
// 清空栈
this.clear = function() {
this.data = [];
}
1
2
3
4
5
2
3
4
5
# 完整代码
// 栈(堆栈)stack
// 先进后出,后进先去
function Stack() {
// 栈数据
this.data = [];
// 入栈
this.push = function(data) {
this.data.push(data);
}
// 出栈
this.pop = function() {
if (this.empty()) return null;
else return this.data.pop();
}
// 判断是否为空
this.empty = function() {
if (this.data.length == 0) return true;
else return false;
}
// 查看栈中元素总数
this.length = function() {
return this.data.length;
}
// 清空栈
this.clear = function() {
this.data = [];
}
this.toString = function() {
return this.data.join(',')
}
}
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
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
# 链式存储结构
顺出存储结构的栈是通过数组来存储栈帧，而链式存储结构是用链表来存储数据，我们只需要把顺序存储结构的栈中数组换成链表即可。
链表可参考：文章
# 链表
先定义一个链表:
function Node(data) {
this.data = data;
this.next = null;
}
function LinkList() {
head = null;
length = 0;
// 在链表最后添加节点
this.push = function(data) {
var node = new Node(data);
if (head == null) {
head = node;
} else {
var current = head;
var previous;
while(current) {
previous = current;
current = current.next;
}
previous.next = node;
}
length++;
}
// 从链表尾部移除节点
this.pop = function() {
var current = head;
var previous;
while (current.next) {
previous = current;
current = current.next;
}
previous.next = null;
length--;
}
// 清空节点
this.clear = function() {
var current = head;
var previous;
while(current.next) {
previous = current;
current = current.next;
// 清空前一个节点
previous = null;
head = current;
length--;
}
// 清空最后一个节点
current = null;
length--;
}
this.size = function() {
return length;
}
// 遍历节点
this.toString = function() {
var str = head.data;
var current = head.next;
while (current) {
str += ','+ current.data;
current = current.next;
}
return str;
}
}
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
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
# 链栈
链式存储结构的栈结构和顺序存储结构栈基本一样:
function Stack() {
// 栈数据
this.data = new LinkList();
// 入栈
this.push = function(data) {
this.data.push(data);
}
// 出栈
this.pop = function() {
if (this.empty()) return null;
else return this.data.pop();
}
// 判断是否为空
this.empty = function() {
if (this.data.size() == 0) return true;
else return false;
}
// 查看栈中元素总数
this.length = function() {
return this.data.size();
}
// 清空栈
this.clear = function() {
this.data.clear();
}
this.toString = function() {
return this.data.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
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
# 完整代码
// 栈(堆栈)stack
// 先进后出,后进先去
function Node(data) {
this.data = data;
this.next = null;
}
function LinkList() {
head = null;
length = 0;
// 在链表最后添加节点
this.push = function(data) {
var node = new Node(data);
if (head == null) {
head = node;
} else {
var current = head;
var previous;
while(current) {
previous = current;
current = current.next;
}
previous.next = node;
}
length++;
}
// 从链表尾部移除节点
this.pop = function() {
var current = head;
var previous;
while (current.next) {
previous = current;
current = current.next;
}
previous.next = null;
length--;
}
// 清空节点
this.clear = function() {
var current = head;
var previous;
while(current.next) {
previous = current;
current = current.next;
// 清空前一个节点
previous = null;
head = current;
length--;
}
// 清空最后一个节点
current = null;
length--;
}
this.size = function() {
return length;
}
// 遍历节点
this.toString = function() {
var str = head.data;
var current = head.next;
while (current) {
str += ','+ current.data;
current = current.next;
}
return str;
}
}
function Stack() {
// 栈数据
this.data = new LinkList();
// 入栈
this.push = function(data) {
this.data.push(data);
}
// 出栈
this.pop = function() {
if (this.empty()) return null;
else return this.data.pop();
}
// 判断是否为空
this.empty = function() {
if (this.data.size() == 0) return true;
else return false;
}
// 查看栈中元素总数
this.length = function() {
return this.data.size();
}
// 清空栈
this.clear = function() {
this.data.clear();
}
this.toString = function() {
return this.data.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
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
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
上次更新: 2022/12/01, 11:09:34