数据结构之栈和队列

栈#

栈： Stack，是一种遵循后进先出 (LIFO: Last In First Out) 原则的有序集合，是一种线性结构。

新添加的或待删除的元素都保存在栈的同一端，称作栈顶，另一端就叫栈底。

代码实现#

在 JavaScript 中可以使用内置的数据结构数组轻松实现栈，也可以使用链表来实现栈。

使用数组实现栈

class Stack {
  constructor() {
    this.items = [];
  }
 
  // 入栈 O(1)
  push(element) {
    this.array.items(element);
  }
 
  // 出栈，返回出栈的元素 O(1)
  pop() {
    return this.items.pop();
  }
 
  // 返回栈顶元素 O(1)
  peek() {
    return this.items[this.items.length - 1];
  }
 
  // 返回栈里的元素个数 O(1)
  size() {
    return this.items.length;
  }
 
  // 检查栈是否为空 O(1)
  isEmpty() {
    return this.size() === 0;
  }
 
  // 清空栈 O(1)
  clear() {
    this.items = [];
  }
 
  toString() {
    let str = "Stack: [ ";
    str += this.items.join(", ");
    str += " ] top";
    return str;
  }
}

使用链表实现栈

需要导入链表LinkedList，因为栈的入栈和出栈都在同一端，在链表的表头添加和删除节点实现栈的入栈和出栈，时间复杂度和数组实现的栈是一样的，都是 O(1)。

class LinkedListStack {
  constructor() {
    this.list = new LinkedList();
  }
 
  // 入栈 O(1)
  push(element) {
    this.list.addFirst(element);
  }
 
  // 出栈，返回出栈的元素 O(1)
  pop() {
    this.list.removeFirst();
  }
 
  // 返回栈顶的元素 O(1)
  peek() {
    return this.list.getFirst();
  }
 
  // 获取栈的元素个数 O(1)
  size() {
    return this.list.size();
  }
 
  // 查询栈是否为空 O(1)
  isEmpty() {
    return this.list.isEmpty();
  }
 
  // 清空栈 O(1)
  clear() {
    this.list = new LinkedList();
  }
 
  toString() {
    let str = "Stack: top ";
    str += this.list.toString();
    return str;
  }
}

代码测试#

只测试数组实现的栈

const stack = new Stack();
 
for (let i = 0; i < 5; i++) {
  stack.push(i);
  console.log(stack.toString());
}
// Stack: [ 0 ] top
// Stack: [ 0, 1 ] top
// Stack: [ 0, 1, 2 ] top
// Stack: [ 0, 1, 2, 3 ] top
// Stack: [ 0, 1, 2, 3, 4 ] top
 
stack.pop();
console.log(stack.toString()); // Stack: [ 0, 1, 2, 3 ] top
 
console.log("Peek:", stack.peek()); // Peek: 3
console.log("Size:", stack.peek()); // Size: 4

实际应用#

栈在实际生活中应该很广泛，比如我们把书本一本一本的堆叠放在一个，这就是一个栈。

在代码中，比如 JavaScript 主线程的调度执行就是一个执行栈。还有一些文本编辑器中的撤销操作，也是应用了栈的原理，从栈顶删除刚入栈的元素即撤销。

队列#

队列：Queue，遵循先进先出 (FIFO: First In First Out) 原则有序的集合，也是一种线性结构。

队列在尾部添加新元素，并从另一端的顶部移除元素，最新添加的元素必须排在队列的末尾。

代码实现#

在 JavaScript 中可以使用内置的数据结构数组轻松实现队列，也可以使用链表来实现队列。

使用数组实现队列

在数组中实现的队列中，队首出列的时间复杂度为 O(n)，因为数组结构的元素出列后，后面所有的元素都需要往前移动一个位置。

class Queue {
  constructor() {
    this.items = [];
  }
 
  // 入列 O(1)
  enqueue(element) {
    this.items.push(element);
  }
 
  // 出列 O(n)
  dequeue() {
    return this.items.shift();
  }
 
  // 返回队列的第一个元素 O(1)
  peek() {
    return this.items[0];
  }
 
  // 返回队列的元素个数 O(1)
  size() {
    return this.items.length;
  }
 
  // 查询队列是否为空 O(1)
  isEmpty() {
    return this.size() === 0;
  }
 
  // 清空队列 O(1)
  clear() {
    this.items = [];
  }
 
  toString() {
    let str = "Queue: front [ ";
    str += this.array.join(", ");
    str += " ]";
    return str;
  }
}

使用链表实现队列

这里不需要导入链表数据结构，而是在实现链表结构的同时实现队列的功能。

这里使用了表头 head 和表尾 tail 属性，分别在链表的表尾添加实现队列入列，在链表的表头删除节点实现队列出列，这样入列和出列的时间复杂度都是 O(1)，性能比数组实现的队列更好。

// 链表的节点
class Node {
  constructor(element, next = undefined) {
    this.element = element;
    this.next = next;
  }
}
 
// 使用链表实现队列
class LinkedListQueue {
  constructor() {
    this.head = undefined;
    this.tail = undefined;
    this.count = 0;
  }
 
  // 入列 O(1)
  enqueue(element) {
    if (this.tail == undefined) {
      this.tail = new Node(element);
      this.head = this.tail;
    } else {
      this.tail.next = new Node(element);
      this.tail = this.tail.next;
    }
    this.count++;
  }
 
  // 出列 O(1)
  dequeue() {
    if (this.isEmpty()) {
      return undefined;
    }
 
    const delNode = this.head;
    this.head = this.head.next;
    delNode.next = undefined;
 
    if (this.head == undefined) {
      this.tail = undefined;
    }
    this.count--;
    return delNode.element;
  }
 
  // 返回队列的第一个元素 O(1)
  peek() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.head.element;
  }
 
  // 返回队列的元素个数 O(1)
  size() {
    return this.count;
  }
 
  // 查询队列是否为空 O(1)
  isEmpty() {
    return this.size() === 0;
  }
 
  // 清空队列 O(1)
  clear() {
    this.head = undefined; // 表头
    this.tail = undefined; // 表尾
    this.count = 0;
  }
 
  toString() {
    let cur = this.head,
      str = "Queue: front ";
 
    // 遍历节点
    while (cur !== null) {
      str += cur.element + " -> ";
      cur = cur.next;
    }
 
    str += "NULL tail";
    return str;
  }
}

代码测试#

只测试数组实现的队列

let queue = new Queue();
 
for (let i = 0; i < 5; i++) {
  queue.enqueue(i);
  console.log(queue.toString());
}
 
console.log(queue.toString()); // Queue: front [ 0, 1, 2, 3, 4 ]
 
queue.dequeue();
console.log(queue.toString()); // Queue: front [ 0, 1, 2, 3 ]
 
console.log("first element:", queue.peek()); // 1
console.log("element size:", queue.size()); // 4

实际应用#

队列在现实生活中运用很广。比如我们平时在银行排队办理业务就是队列的引用。一个个排队进入队伍当中就是“入列”，办理完业务后离开队伍就是“出列”等。

在代码中使用根据实际场景使用队列。比如vue-router的导航守卫中就使用了队列，把所有的钩子都放在一个队列中，然后按照指定的顺序先后调用各类钩子。

总结#

在 JavaScript 中，栈和队列可以说是特殊功能的数组，可以不需要专门去实现它们，只需要熟悉它们的原理，灵活使用内置的数组相应的 API 就相当于使用了它们。

因为前端的数据量一般都不是很大，即使使用数组来模拟队列的出列操作所耗费的时间也不会很大，一般的使用场景都是够用的。但是如果出列涉及大量的数据，就应该使用链表来实现队列。