【JS】数据结构之栈

基本介绍

内存中的堆栈和数据机构中的堆栈不是一个概念，内存中的堆栈是真实存在的物理区，数据结构中的堆栈是抽象数据存储结构。

• 栈：是一种受限制的线性表。他遵循后进先出的原则（LIFO）
• 其限制是仅允许在表的一端进行插入和删除运算，这一端被称为栈顶，相对的另一端称为栈底。
• 最开始的时候，栈是不含有任何数据的，叫做空栈。
• 向一个栈插入新元素称为入栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素。
• 从一个栈删除元素又称之为出栈，他是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

我们可以利用栈这个数据结构，理解JS的运行机制之：JS调用栈

• 执行上下文：就是当前JS代码被解析和执行所在环境的抽象概念。
• JS中任何代码都是在执行上下文中运行的（执行环境）
• JS 执行上下文分三种：

1. 全局执行上下文：先创建全局对象，再将this指向这个全局对象。
2. 函数执行上下文：每次调用函数的时候，会为这个函数创建一个新的执行上下文。
3. Eval函数执行上下文：`eval()`
1
2
3

• 示例：

const one = () => {
	two();
	console.log('我是one');
}
const two = () => {
	console.log('我是two');
}
one();
1
2
3
4
5
6
7
8

• JS引擎创建一个新的全局执行上下文，并将这个执行上下文推入当前的执行栈中。
• 执行栈用于存储在代码执行期间创建的所有的执行上下文。

- 每当发生函数调用的时候，JS引擎都会为该函数创建一个新的执行上下文并push到当前执行栈的栈顶。
- 当调用 one 函数的时候，JS引擎都会为该函数创建一个新的执行上下文并推到当前执行栈的栈顶。
- 当调用 two 函数的时候，JS引擎都会为该函数创建一个新的执行上下文并推到当前执行栈的栈顶。
- 当two函数调用完毕后，他的执行上下文就会从当前执行栈中弹出，上下文的控制权移到当前执行栈中的下一个执行上下文：one 函数
1
2
3
4

我们可以利用栈这个数据结构，理解JS的运行机制之：递归的原理

• 函数的调用本质：入栈和出栈操作。
• 但是函数在调用栈里面有个特例，那就是递归（自己调自己）。
• 先进栈，到条件后再出栈，如果不出栈，就会导致：栈溢出（栈的容量是有限的）
• 示例：阶乘n!（5! = 54321）

const factor = (n)=>{
	// 递归要有出口，否则就是死循环
	if(n === 1){
		return 1;
	}
	return n * factor(n - 1);
}
console.log(factor(3));	// 6
console.log(factor(10));	// 3628800
1
2
3
4
5
6
7
8
9

• 函数在内存中调用，会形成一个调用记录，又称为调用帧
• 递归可能需要同时保存成百上千个调用帧，很容易发生栈溢出。
• 但是对于尾递归来说，由于只存在一个调用栈，所有不会发生栈溢出错误

// 尾调用
function a(x){}
function b(x){
	return a(x);
}
// 尾调用自身就是尾递归
const factor = (n, total)=>{
	if(n === 1){
		return total;
	}
	return factor(n - 1, n * total);
}
1
2
3
4
5
6
7
8
9
10
11
12

• 示例：斐波那契数列（从第三项开始，每一项等于前两项的和：1，1，2，3，5，8，13）

// 递归
const Fibonacci = (n) => {
	if(n<=1){
		return 1;
	}
	return Fibonacci(n-1)+Fibonacci(n-2);
}
/*
	会存在一个重复计算问题
	n = 5, Fibonacci(4)+Fibonacci(3)
	n = 4, Fibonacci(3)+Fibonacci(2)
	...
*/
console.log(Fibonacci(50));	// 运行直接卡死
// 尾递归
// 把前面2位数，当作参数传进来
const Fibonacci = (n, ac1=1, ac2=1) => {
	if(n<=1){
		return ac2;
	}
	return Fibonacci(n-1, ac2, ac1+ac2);
}
console.log(Fibonacci(50));	// 运行就很流畅
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

代码实现

栈的应用有：十进制转二进制

• 使用JavaScript实现一个栈结构

class Stack{
	constructor() {
		this.items = [];
	}
	// 入栈
	push(ele){
		this.items.push(ele);
	}
	// 出栈
	pop() {
		return this.items.pop();
	}
	// 获取栈顶元素
	peek(){
		return this.items[this.items.length - 1];
	}
	// 查看栈是否为空
	isEmpty(){
		return this.items.length === 0;
	}
	// 查看栈中元素个数
	size(){
		return this.items.length;
	}
	// 清空栈
	clear(){
		this.items = []
	}
}

const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);

console.log(stack);

// 十进制转二进制
const binary = (number) =>{
	let stack = new Stack();
	let remainder = 0;
	let top = '';
	while(number > 0){
		// 除于2取余数
		remainder = number % 2;
		stack.push(remainder);
		// 向下取整
		number = Math.floor(number / 2);
	}
	// 不为空的时候
	while(!stack.isEmpty()){
		// 栈顶元素
		top += stack.pop();
	}
	return top;
}
console.log("2 = ", binary(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