数据结构之栈

栈(stack)又名堆栈,仅能在表尾进行插入和删除操作的线性表,这一端被称为栈顶,另一端称为栈底,向一个栈插入新元素又称作入栈,从一个栈删除元素称作出栈。 栈遵守先进后出,后进先出的原则(LIFO)。

入栈和出栈

入栈

出栈

栈的分类

栈中每一个节点称为栈帧,栈作为线性表,栈帧有两种存储形式:

  • 顺序存储结构
  • 链式存储结构

顺序存储结构

Stack

参照顺序存储的表现形式,我们使用数组来存储栈帧数据, 先定义一个栈类:

1
2
3
4
5
6
7
8
// 栈(堆栈)stack
// 先进后出,后进先去

function Stack() {

// 栈数据
this.data = [];
}

入栈

入栈直接向数组push()向数组末尾添加元素:

1
2
3
4
// 入栈
this.push = function(data) {
this.data.push(data);
}

出栈

出栈直接使用数组pop方法删除并返回最后一个元素:

1
2
3
4
this.pop = function() {
if (this.data.length == 0) return null;
else return this.data.pop();
}

清空栈

清空栈即将数组清空:

1
2
3
4
// 清空栈
this.clear = function() {
this.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
// 栈(堆栈)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
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 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
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
// 栈(堆栈)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();
}

}
有用就打赏一下作者吧!