数据结构-栈

栈是什么？

栈是一种线性的
一个后进先出的数据结构

JavaScript 中没有栈，但可以使用 Array 实现栈的所有功能

1
2
3
4
5
6
7
8
9
// 简单版本栈
const arr = [];
// 入栈
arr.push(1); // [ 1 ]
arr.push(2); // [ 1, 2 ]

// 出栈
arr.pop(); // [ 1 ]
arr.pop(); // []

实现栈基本操作有

入栈push()
出栈pop()
判断栈是否为空isEmpty()
清空栈clean()
栈的大小size()
栈顶元素peek()
栈底元素last()

 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
// JavaScipt实现
class Stack {
  stack = [];

  push(item) {
    this.stack.push(item);
  }
  pop() {
    return this.isEmpty() ? "stack is empty" : this.stack.pop();
  }
  isEmpty() {
    return this.size() === 0;
  }
  clean() {
    this.stack.length = 0;
  }
  size() {
    return this.stack.length;
  }
  peek() {
    // 只是返回元素不会从栈中移除元素
    return this.stack[this.stack.length - 1];
  }
  last() {
    return this.stack[0];
  }
}

// 运行示例
let stack = new Stack();
stack.push(1); // [1]
stack.push(5); // [1, 5]
stack.push(7); // [1, 5, 7]
stack.peek(); // 7
stack.size(); // length 3
stack.last(); // 1

stack.pop(); // [1, 5]
stack.size(); // length 2
stack.pop(); // [1]
stack.clean(); // []

使用场景

需要后进先出的场景

JavaScript 调用栈，比如 event loop
判断字符串的括号是否有效
十进制转二进制
计算带小括号的数学表达式
网页历史记录返回

to be continued…