栈(stack)是一种运算受限的线性结构:
- 先进后出,后进先出
LIFO:(last in first out)
。 - 其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。
- 向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;
- 从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。
程序中的栈结构:
栈被用在编程语言的编译器和内存中保存变量、方法调用等,也被用于浏览器历史记录(浏览器的返回按钮)。
函数调用栈:A(B(C(D()))):
- 即A函数中调用B,B调用C,C调用D;
- 在A执行的过程中会将A压入栈,随后B执行时B也被压入栈,函数C和D执行时也会被压入栈。
- 所以当前栈的顺序为:A->B->C->D(栈顶);
- 函数D执行完之后,会弹出栈被释放,弹出栈的顺序为D->C->B->A;
递归:为什么没有停止条件的递归会造成栈溢出?
- 比如函数A为递归函数,不断地调用自己(因为函数还没有执行完,不会把函数弹出栈)
- 不停地把相同的函数A压入栈,最后造成栈溢出(Stack Overfloat)
练习:题目:有6个元素6,5,4,3,2,1按顺序进栈,问下列哪一个不是合法的出栈顺序?
- A:5 4 3 6 1 2 (√)
- B:4 5 3 2 1 6 (√)
- C:3 4 6 5 2 1 (×)
- D:2 3 4 1 5 6 (√)
题目所说的按顺序进栈指的不是一次性全部进栈,而是有进有出,进栈顺序为6 -> 5 -> 4 -> 3 -> 2 -> 1。
解析:
- A答案:65进栈,5出栈,4进栈出栈,3进栈出栈,6出栈,21进栈,1出栈,2出栈(整体入栈顺序符合654321);
- B答案:654进栈,4出栈,5出栈,3进栈出栈,2进栈出栈,1进栈出栈,6出栈(整体的入栈顺序符合654321);
- C答案:6543进栈,3出栈,4出栈,之后应该5出栈而不是6,所以错误;
- D答案:65432进栈,2出栈,3出栈,4出栈,1进栈出栈,5出栈,6出栈。符合入栈顺序;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
栈常见的操作:
- push(element):添加一个新元素到栈顶位置;
- pop():移除栈顶的元素,同时返回被移除的元素;
- peek():返回栈顶的元素,不对栈做任何修改(该方法不会移除栈顶的元素,仅仅返回它);
- isEmpty():如果栈里没有任何元素就返回true,否则返回false;
- size():返回栈里的元素个数。这个方法和数组的length属性类似;
- toString():将栈结构的内容以字符串的形式返回。
# 1、封装栈
栈的实现:
- 基于数组
- 基于链表
基于数组的栈代码实现:
class Stack {
// 用数组来保存栈内元素
constructor() {
this.items = []
}
// 栈的相关操作:
// 1.添加一个(或几个)新元素到栈顶
push(element) {
this.items.push(element)
}
// 2.移除栈顶的元素,同时返回被移除的元素
pop() {
return this.items.pop()
}
// 3.返回栈顶的元素,不对栈做任何修改
peek() {
return this.items[this.items.length-1]
}
// 4.判断栈是否为空,如果栈里没有任何元素就返回true,否则返回false
isEmpty() {
return this.items.length === 0
}
// 5.获取栈中元素个数
size() {
return this.items.length
}
// 6.移除栈里所有元素
clear() {
this.items = []
}
// 7.toString方法
toString() {
let resultString = ''
for (const item of this.items) {
resultString += item + ' '
}
return resultString
}
}
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
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
测试代码:
const stack = new Stack()
// push() 测试
stack.push(1);
stack.push(2);
stack.push(3);
console.log("输出栈",stack.items); //--> [1, 2, 3]
// pop() 测试
console.log("pop() 测试",stack.pop()); //--> 3
// peek() 测试
console.log("peek() 测试",stack.peek()); //--> 2
// isEmpty() 测试
console.log("isEmpty() 测试",stack.isEmpty()); //--> false
// size() 测试
console.log("size() 测试",stack.size()); //--> 2
// toString() 测试
console.log("toString() 测试",stack.toString()); //--> 1 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
测试结果:
# 2、栈简单应用
栈的实际应用非常广泛。在回溯问题中,它可以存储访问过的任务或路径、撤销的操作。Java和C#用栈来存储变量和方法调用,特别是处理递归算法时,有可能抛出一个栈溢出异常。
既然我们已经了解了Stack类的用法,不妨用它来解决一些计算机科学问题。利用栈结构的特点封装实现十进制转换为二进制的方法。
分析:
- 把十进制转换为二进制的通用方法就是模二取余法
- 将十进制数字不断模二取余,直到被除数等于零时停止
- 将得到的余数逆序输出即为相应二进制数字。
代码实现:
function dec2bin(decNumber) {
//1.定义一个栈对象,保存余数
let stack = new StackArray()
// 2.循环取余压栈
while (decNumber > 0) {
// 2.1.获取余数并放入栈中
stack.push(decNumber % 2)
// 2.2.获取整除后的结果作为下一次运算的数字(floor:向下取整)
decNumber = Math.floor(decNumber / 2)
}
// 3.按顺序出栈显示结果
let binaryString = ''
while (!stack.isEmpty()) {
binaryString += stack.pop()
}
return binaryString
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
测试:
// dec2bin() 测试
console.log(dec2bin(100)); //--> 1100100
console.log(dec2bin(88)); //--> 1011000
console.log(dec2bin(233)); //--> 11101001
1
2
3
4
2
3
4