数据结构-栈

栈是一种后进先出(LIFO)的数据结构。新添加的或待删除的元素都保存在栈的末尾,称作栈顶,另一端叫栈低。

栈的创建

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
function Stack() {
// 创建一个数组保存栈里的元素
var items = [];
// 添加一个元素(或几个)到栈顶
this.push = function(element){
items.push(element);
}
// 移除栈顶的元素,同时返回被移除的元素
this.pop = function(){
return items.pop();
}
// 返回栈顶的元素,不对栈做任何修改
this.peek = function(){
return items[items.length - 1];
}
// 检查栈里是否为空,空->true
this.isEmpty = function(){
return items.length === 0;
}
// 移除栈里所有元素
this.clear = function(){
items = [];
}
// 返回栈内元素个数
this.length = function(){
return items.length;
}
// 控制台输出所有元素
this.print = function(){
console.log(items.toString());
}
}
// 使用(先实例化)
var stack = new Stack();

应用

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
// 十进制转二进制
function divideBy2(decNumber) {
var remStack = new Stack(),
rem,
binaryString = '';
while (decNumber > 0) {
rem = Math.floor(decNumber % 2);
remStack.push(rem);
decNumber = Math.floor(decNumber / 2);
}
while (!remStack.isEmpty()) {
// 把移出栈的元素依次连接成字符串
binaryString += remStack.pop().toString();
}
return binaryString;
}
// 简单修改,十进制可以转换成任何进制
function baseConverter(decNumber, base) {
var remStack = new Stack(),
rem,
baseString = '',
digits = '0123456789ABCDEF';
while (decNumber > 0) {
rem = Math.floor(decNumber % base);
remStack.push(rem);
decNumber = Math.floor(decNumber / base);
}
while (!remStack.isEmpty()) {
binaryString += digits[remStack.pop()];
}
return baseString;
}