栈是一种遵从后进先出（LIFO）原则的有序集合。新添加或待删除的元素都保存在栈的同一端，称作栈顶。在栈里，新元素都靠近栈顶，旧元素都接近栈底。
图片展示如下：
3.1 基于数组的栈
我们来规划一下栈类需要的方法：
**push(element)**： 添加一个（或几个）新元素到栈顶
**pop()**：移除栈顶的元素，同时返回被移除的元素
**peek()**：返回栈顶的元素，不对栈做任何修改
**isEmpty()**：如果栈里没有任何元素就返回true,否则返回false
**clear()**：移除栈里所有元素
**size()**：返回栈里元素的个数
**toString()**：转成字符串
完整的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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| class Stack {
constructor() {
this.items = [];
}
push(element) {
this.items.push(element);
}
pop() {
return this.items.pop()
}
peek() {
return this.items[this.items.length - 1];
}
isEmpty() {
return this.items.length === 0;
}
clear() {
this.items = [];
}
size() {
return this.items.length;
}
toString(){
return this.items.toString();
}
}
|
我们来使用一下Stack类
1
2
3
4
5
| let stack = new Stack();
stack.push(3);
stack.push(5);
stack.push(8);
console.log(stack.toString());
|
示例用图来绘制：
删除栈顶示例：
1
2
3
| stack.pop();
stack.pop();
console.log(stack.toString());
|
3.2 基于对象的栈
方法与上基于数组的栈方法规划一致
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
| class Stack {
constructor() {
this.count = 0;
this.items = {};
}
push(element) {
this.items[this.count] = element;
this.count++;
}
pop() {
if (this.isEmpty()) {
return undefined;
}
this.count--
let result = this.items[this.count];
delete this.items[this.count];
return result;
}
peek() {
return this.items[this.count - 1];
}
isEmpty() {
return this.count === 0;
}
clear() {
while (!this.isEmpty()) {
this.pop();
}
}
size() {
return this.count;
}
toString() {
if (this.isEmpty()) {
return '';
}
let content = this.items[0];
for (let i = 1; i < this.count; i++) {
content += ',' + this.items[i];
}
return content;
}
}
|
3.3 栈的应用
从十进制到二进制
在现实生活中，我们主要是使用十进制。但在计算机科学中，二进制非常重要，因为计算机里的所有内容都是有二进制数字表示的（0和1）。没有十进制和二进制相互转换的能力，与计算机交流就很困难。
要把十进制转换成二进制，我们可以将该十进制数除以2（二进制是满2进1）并对商取整，直到结果是0为止。
举个例子，把十进制数字10转换成2进制，过程大概如下：
实现代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
| function decimalToBinary(number) {
let stack = new Stack();
let binaryString = '';
while (number > 0) {
stack.push(Math.floor(number % 2));
number = Math.floor(number / 2);
}
while (!stack.isEmpty()) {
binaryString += stack.pop().toString();
}
return binaryString;
}
|
使用：
1
| console.log(decimalToBinary(10));
|
十进制转任意进制
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
function binaryConversion(number,level = 2) {
let stack = new Stack();
const digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';
if(level < 2 || level > 36){
return '';
}
let binaryString = '';
while (number > 0){
stack.push(Math.floor(number % level))
number = Math.floor(number / level);
}
while (!stack.isEmpty()){
binaryString += digits[stack.pop()];
}
return binaryString;
}
|
使用：
1
| console.log(binaryConversion(10,2));
|
