基础知识
更新时间: 2023-03-12 16:24:26
- 栈是一种非常常见的数据结构,并且在程序中的应用非常广泛,
- 数组
- 我们知道数组是一种线性结构,并且可以在数组的任意位置插入和删除数据
- 但有时候,我们为了实现某些功能,必须对这种任意性加以限制
- 栈和队列就是比较常见的受限的线性结构。
# 认识栈结构
- 栈(stask),它是一种受限的线性表,后进先出(LIFO)
- 其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。
- LIFO(last in first out)表示就是后进入的元素,第一个弹出栈空间。类似于自助餐托盘,最后放上的托盘,往往先被拿出去使用。
- 向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之称为新的栈顶元素
- 从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删掉,使其相邻的元素成为新的栈顶元素
# 栈的应用
程序中什么是使用栈实现的呢?学了这么久的编程是否听说过,函数调用栈呢?
- 我们知道函数之间和相互调用:A调用B,B中又调用C,C中又调用D
- 那样在执行的过程中,会先将A压入栈,A没有执行完,所以不会弹出栈
- 在A执行的过程中调用了B,会将B压入到栈,这个时候B在栈顶,A在栈底
- 如果这个时候B可以执行完,那么B会弹出栈,但是B有执行完吗?没有,它调用了C
- 所以C会压栈,并且在栈顶,而C调用了D,D会压入到栈顶
- D执行完,弹出栈。C/B/A一次弹出栈
- 所以我们函数调用栈的称呼,就来自于它们内部的实现机制(通过栈来实现的)
# 栈结构的实现
实现栈结构有两种比较常见的方式
- 基于数组实现
- 基于链表实现
什么是链表?
- 也是一种数据结构,目前我们还没有学习,并且JavaScript中并没有自带链表结构
- 后续,我们会自己来实现链表结构,并且对比数组和链表的区别
因此我们用数组来实现栈结构:
- 栈有哪些常见操作呢?
- push(element):添加一个(或几个)新元素到栈顶位置
- pop():移除栈顶的元素,同时返回被移除的元素。
- peek(): 返回栈顶的元素,不对栈做任何修改(这个方法不会移除栈顶的元素,仅仅返回它)
- isEmpty():如果栈里没有任何元素就返回true,否则返回false
- size():返回栈里的元素个数,这个方法和数组的length属性很类似
- clear():移除栈里的所有元素
现在,我们可以在类中一一实现这些方法。
export default class StackArray {
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;
}
size() {
return this.items.length;
}
clear() {
this.items = [];
}
toArray() {
return this.items;
}
toString() {
return this.items.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
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
# 创建一个基于JavaScript对象的Stack类
创建一个Stack类最简单的方式是使用一个数组来存储其元素。在处理大量数据的时候,我们统一需要评估如何操作数据是最高效的。在使用数组时,大部分方法的时间复杂度是O(n)。O(n)的意思是,我们需要迭代整改数组直到找到要找的那个元素,在最坏的情况下需要迭代数组的所有位置,其中的n代表数组的长度。如果数组有更多元素的话,所需的时间会更长。另外,数组是元素的有序集合,为了保证元素排列有序,它会占用更多的内存空间。
我们可以使用对象来存储所有的元素,并且遵守LIFO原则。
export default 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--;
const result = this.items[this.count];
delete this.items[this.count];
return result;
}
peek() {
if (this.isEmpty()) {
return undefined;
}
return this.items[this.count - 1];
}
isEmpty() {
return this.count === 0;
}
size() {
return this.count;
}
clear() {
/* while (!this.isEmpty()) {
this.pop();
} */
this.items = {};
this.count = 0;
}
toString() {
if (this.isEmpty()) {
return '';
}
let objString = `${this.items[0]}`;
for (let i = 1; i < this.count; i++) {
objString = `${objString},${this.items[i]}`;
}
return objString;
}
}
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
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
除了toString方法,我们创建的其他方法的复杂度均为O(1),代表我们可以直接找到目标元素并对其进行操作。
# 用ES2015的限定作用域Symbol实现类
ES2015新增了一种叫做Symbol的基本类型,它是不可变的,可以用作对象的属性。
const _items = Symbol('stackItems')
class Stack {
constructor() {
this[_items] = []
}
//...
}
1
2
3
4
5
6
7
2
3
4
5
6
7
这种方法创建了一个假的私有属性,因为ES2015新增的Object.getOwnPropertySymbols方法能够获取到类里面的所有Symbols属性。
# WeakMap实现类
有一种数据类型可以确保属性是私有的,这就是WeakMap.
const items = new WeakMap()
class Stack {
constructor() {
items.set(this,[])
}
push(element) {
const s = items.get(this)
s.push(element)
}
pop() {
const s = items.get(this)
const r = s.pop()
return r
}
//...
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 十进制转二进制
//函数:将十进制转成二进制
function dec2bin(decNumber) {
// 1. 定义栈对象
const remStack = new Stack()
let number = decNumber
let rem
let binaryString = ''
// 2.循环操作
while(number > 0) {
// 2.1获取余数,并且放入到栈中
rem = stack.push(decNumber % 2)
// 2.2获取整除后的结果,作为下一次
number = Math.floor(decNumber / 2)
}
// 3. 从栈中取出0和1
while(!stack.isEmpty()) {
binaryString += stack.pop().toString()
}
return binaryString
}
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~36的任意进制。
function baseConverter(decNumber, base) {
const remStack = new Stack()
const digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
let number = decNumber
let rem
let baseString = ''
if(!(base >= 2 && base <= 36)) {
return ''
}
while(number > 0) {
rem = Math.floor(number % base)
remStack.push(rem)
number = Math.floor(number / base)
}
while(!remStack.isEmpty()) {
baseString += digits[remStack.pop()]
}
return baseString
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23