基础知识

更新时间: 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一次弹出栈
  • 所以我们函数调用栈的称呼,就来自于它们内部的实现机制(通过栈来实现的)

# 栈结构的实现

  • 实现栈结构有两种比较常见的方式

    1. 基于数组实现
    2. 基于链表实现
  • 什么是链表?

    1. 也是一种数据结构,目前我们还没有学习,并且JavaScript中并没有自带链表结构
    2. 后续,我们会自己来实现链表结构,并且对比数组和链表的区别

因此我们用数组来实现栈结构:

  • 栈有哪些常见操作呢?
    • 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

# 创建一个基于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

除了toString方法,我们创建的其他方法的复杂度均为O(1),代表我们可以直接找到目标元素并对其进行操作。

# 用ES2015的限定作用域Symbol实现类

ES2015新增了一种叫做Symbol的基本类型,它是不可变的,可以用作对象的属性。

const _items = Symbol('stackItems')
class Stack {
    constructor() {
        this[_items] = []
    }
    //...
}
1
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

# 十进制转二进制










 
 
 
 
 
 








//函数:将十进制转成二进制
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~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