数据结构（用 JS 实现栈和队列【三种方式】）

栈

先进后出

JS 实现栈

• 栈 : 用数组实现
• 入栈 push ---- 时间复杂度 O(1)
• 出栈 pop ---- 时间复杂度 O(1)

let stack = [];

// 入栈
stack.push("a");
stack.push("b");

console.log(stack);

// 出栈 -- 先进后出 -- b 出栈
stack.pop();

console.log(stack);

1
2
3
4
5
6
7
8
9
10
11
12
13

队列

先进先出

JS 实现队列（方案1）

• 队列 : 用数组实现
• 入队 push ---- 时间复杂度 O(1)
• 出队 shift ---- 时间复杂度 O(n)

let queue = [];

// 入队
queue.push("a");
queue.push("b");

console.log(queue);

// 出队 -- 先进先出 -- a 出队
queue.shift();

console.log(queue);
1
2
3
4
5
6
7
8
9
10
11
12

JS 实现队列（方案2）

• 队列 : 用数组实现
• 入队 unshift ---- 时间复杂度 O(n)
• 出队 pop ---- 时间复杂度 O(1)

let queue = [];

// 入队
queue.unshift("a");
queue.unshift("b");

console.log(queue);

// 出队 -- 先进先出 -- a 出队
queue.pop();

console.log(queue);
1
2
3
4
5
6
7
8
9
10
11
12

【推荐】JS 链表实现队列（方案3）

时间复杂度 O(1)

// 实现队列的：入队、出队、长度
// PS：要用链表来实现，用数组性能较低

class MyQueue {
  constructor() {
    this.length = 0; // 长度
    this.head = null;
    this.tail = null;
  }
  // 从 tail 入队
  add(value) {
    const newNode = { value };

    if (this.length === 0) {
      // 长度是 0
      this.head = newNode;
      this.tail = newNode;
    } else {
      // 长度 > 0 ，把 newNode 拼接到 tail 位置
      this.tail.next = newNode;
      this.tail = newNode;
    }

    this.length++; // 累加长度
  }
  // 从 head 出队
  delete() {
    if (this.length <= 0) return null;

    let value = null;
    if (this.length === 1) {
      // 长度是 1 ，只有一个元素了
      value = this.head.value; // 先找到结果
      // 重置 head tail
      this.head = null;
      this.tail = null;
    } else {
      // 长度 > 1 ，多个元素
      value = this.head.value; // 先找到结果
      this.head = this.head.next; // 重置 head
    }

    // 减少长度，返回结果
    this.length--;
    return value;
  }
}

// 功能测试
const queue = new MyQueue();
queue.add(100);
console.log("length1", queue.length); // 1
queue.add(200);
console.log("length2", queue.length); // 2
console.log("delete1", queue.delete()); // 100
queue.add(300);
console.log("length3", queue.length); // 2
console.log("delete2", queue.delete()); // 200
console.log("length4", queue.length); // 1
console.log("delete3", queue.delete()); // 300
console.log("length5", queue.length); // 0
console.log("delete4", queue.delete()); // null
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
59
60
61
62