数据结构和算法之美-第六篇-队列

队列

先进先出，类比现实生活中的排队，先到先得。

队列也是一种操作受限的线性表，支持操作：入队、出队

如下图所示
data-structures-algorithm 2019-08-05 下午4.52.06.png

队列可以使用数组实现也可以使用链表实现
基于链表实现的队列叫链式队列

class Node {
  constructor(v) {
    this.value = v;
    this.next = null;
  }
}
class LinkedQueue {
  constructor() {
    this.head = null;
    this.tail = null;
  }
  /**
   * 尾部添加
   * 注意为空的情况
   */
  enqueue(v) {
    if (this.head === null) {
      this.head = new Node(v);
      this.tail = this.head;
    } else {
      this.tail.next = new Node(v);
      this.tail = this.tail.next;
    }
  }
  /**
   * 头部删除
   */
  dequeue() {
    if (this.head === null) return -1;
    const tempNodeV = this.head.value;
    this.head = this.head.next;
    return tempNodeV;
  }
}

基于数组实现的队列叫顺序队列
在JS中使用数组实现队列不需要考虑超长的问题，还是贴上代码。

class ArrayQueue {
  constructor() {
    this.array = [];
  }
  enqueue(v) {
    // javascript中的数组支持扩容，不考虑超出长度的情况
    this.array.push(v);
  }
  dequeue() {
    const tempV = this.array.shift();
    if (tempV === undefined) return -1;
    return tempV;
  }
}

需要注意的是，JS 中的数组更像Java语言中的容器，但数组还是使用的连续的内存空间，提供的shift方法是需要进行数据搬运(删除第一个节点，后面的数据依次向左移动一个位置)的。为了解决这种问题，就有了后面的循环队列。

循环队列

保持队列的基本能力：先进先出，在数据结构上是一个循环。
循环队列主要是解决了使用数组需要数据搬运的麻烦。

如下图所示，依次添加节点a、b、c、d，tail指向最后一个空节点（注意不是最后一个有值的节点），由此可知：

当tail === head时，循环队列为空
当(tail+1)%n=head时，循环队列为满。其中n是队列的长度。
(tail+1)%n=head这条规律是总结而来的，根据队列的情况修改tail、head、n的值验证总结出来，可以自己修改验证一下

如图所示

efg进入队列之后，此时tail=7,n=8,head=0，满足(tail+1)%n=head

循环队列的实现难度就在判断何时队列为满。使用循环队列的场景中队列的长度n一定是确定的。

class CircularQueue {
  constructor(n) {
    this.len = n;
    this.queue = [];
    this.head = 0;
    this.tail = 0;
  }
  enqueue(v) {
    if ((this.tail + 1) % this.len === this.head) return false;
    this.queue[this.tail] = v;
    this.tail = ++this.tail % this.len;
    return true;
  }
  dequeue() {
    if (this.head === this.tail) return -1;
    const tempV = this.queue[this.head];
    this.head = ++this.head % this.len;
    return tempV;
  }
  display() {
    let i = this.head;
    let end = this.head > this.tail ? this.tail + this.len : this.tail;
    while (i < end) {
      console.log(this.queue[i]);
      i++;
      i = i % this.len;
    }
  }
}

在日常工作中，其实根本不会需要实现一个队列，可能都不会用到，但是很多底层的原理都与队列这种基础数据结构有关。所以需要对其有彻底的认识。

对大部分资源有限的场景，当没有空闲资源时，都可以使用队列这种数据结构来管理。

队列

FEATURED TAGS

FRIENDS