什么是队列？

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

在现实生活中，最常见的队列例子就是排队。
在JavaScript中，因为JavaScript在浏览器是单线程执行，所以在事件循环中会运用到队列的设计。具体的运用，大家可以仔细看JavaScript事件循环流程。

排队

JavaScript实现队列

队列是一种先进先出的结构，接下来主要实现队列的以下几个方法：

1. enqueue(element): 队首入队
2. dequeue(): 队尾出队
3. peek(): 仅返回队首元素
4. isEmpty(): 队列是否为空
5. size(): 队列长度
6. clear(): 清空队列
7. toString(): 顺序打印队列中数据

      class Queue {
        constructor() {
          this.items = {};
          this.lowerCount = 0; // 头指针
          this.count = 0; // 尾指针
        }
        enqueue(element) {
          this.items[this.count] = element;
          this.count++;
        }
        dequeue() {
          if (this.isEmpty()) {
            return undefined;
          }
          const result = this.items[this.lowerCount];
          delete this.items[this.lowerCount];
          this.lowerCount++;
          return result;
        }
        peek() {
          if (this.isEmpty()) {
            return undefined;
          }
          return this.items[this.lowerCount];
        }
        isEmpty() {
          return this.count - this.lowerCount === 0;
        }
        size() {
          return this.count - this.lowerCount;
        }
        clear() {
          this.items = {};
          this.lowerCount = 0;
          this.count = 0;
        }
        toString() {
          if (this.isEmpty()) {
            return " ";
          }
          let s = `${this.items[this.lowerCount]}`;
          for (let i = this.lowerCount + 1; i < this.count; i++) {
            s += `,${this.items[i]}`;
          }
          return s;
        }
      }

JavaScript实现双端队列

双端队列与队列的不同点在于，双端队列可以从队列头部和尾部添加或删除数据。双端队列也可以应用于计算机的撤销操作，可以把双端队列看成是对栈的一种扩展。

双端队列

主要实现双端队列的以下几种方法：

1. addFront(element): 从队首添加数据
2. addBack(element): 从队尾添加数据
3. removeFront()： 删除队首数据
4. removeBack(): 删除队尾数据
5. peekFront(): 仅返回队首数据
6. peekBack(): 仅返回队尾数据
7. isEmpty(): 队列是否为空
8. size(): 队列长度
9. toString(): 顺序打印队列

    class Dequeue {
      constructor() {
        this.count = 0; // 队尾指针
        this.lowerCount = 0; //队头指针
        this.items = {}; // 双端队列对象存储
      }
      /**
       * 存在3种情况
       * 1. 队列为空,则调用添加队尾方法
       * 2. 队头指针不为0,则队头指针需往前移
       * 3. 队头指针为0,队列需整体后移一位
       * */
      addFront(element) {
        if (this.isEmpty()) {
          this.addBack(element);
        } else if (this.lowerCount > 0) {
          this.lowerCount--;
          this.items[this.lowerCount] = element;
        } else {
          // 从后往前复制
          for (let i = this.count; i > 0; i--) {
            this.items[i] = this.items[i - 1];
          }
          this.count++;
          this.lowerCount = 0;
          this.items[0] = element;
        }
      }
      addBack(element) {
        this.items[this.count] = element;
        this.count++;
      }
      removeFront() {
        if (this.isEmpty()) {
          return undefined;
        }
        const result = this.items[this.lowerCount];
        delete this.items[this.lowerCount];
        this.lowerCount++;
        return result;
      }
      removeBack() {
        if (this.isEmpty()) {
          return undefined;
        }
        this.count--;
        const result = this.items[this.count];
        delete this.items[this.count];
        return result;
      }
      peekFront() {
        return this.items[this.lowerCount];
      }
      peekBack() {
        return this.items[this.count - 1];
      }
      isEmpty() {
        return this.size() === 0;
      }
      size() {
        return this.count - this.lowerCount;
      }
      toString() {
        if (this.isEmpty()) {
          return " ";
        }
        let s = `${this.items[this.lowerCount]}`;
        for (let i = this.lowerCount + 1; i < this.count; i++) {
          s += `,${this.items[i]}`;
        }
        return s;
      }
    }

JavaScript实现循环队列

循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

主要实现循环队列的以下几种方法：

1. CircleQueue(k): 构造器，设置队列长度为 k 。
2. Front: 从队首获取元素。如果队列为空，返回 -1 。
3. Rear: 获取队尾元素。如果队列为空，返回 -1 。
4. enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
5. deQueue(): 从循环队列中删除一个元素。如果成功删除则返回被删除元素。
6. isEmpty(): 检查循环队列是否为空。
7. isFull(): 检查循环队列是否已满。

      class CircleQueue {
        constructor(k) {
          if (k === undefined) {
            throw "必须传入循环队列长度";
          }
          this.size = k; //  队列长度
          this.front = 0; //  队头指针
          this.rear = 0; // 队尾指针
          this.items = {}; //  数组存储队列
        }
        Front() {
          if (this.isEmpty()) {
            return -1;
          }
          return this.items[this.front];
        }
        Rear() {
          /**
           * 分为3种情况
           * 1. 队列为空
           * 2. 队尾指针超出
           * 3. 队尾指针不超出
           **/
          if (this.isEmpty()) {
            return -1;
          }
          const val = this.rear - 1 >= 0 ? this.rear - 1 : this.size - 1;
          return this.items[val];
        }
        enQueue(element) {
          if (this.isFull()) {
            return -1;
          }
          this.items[this.rear] = element;
          this.rear = (this.rear + 1) % this.size;
          return true;
        }
        deQueue() {
          if (this.isEmpty()) {
            return -1;
          }
          const result = this.items[this.front];
          delete this.items[this.front];
          this.front = (this.front + 1) % this.size;
          return result;
        }
        isEmpty() {
          return this.front === this.rear && !this.items[this.front];
        }
        isFull() {
          return this.front === this.rear && !!this.items[this.front];
        }
        toString() {
          if (this.isEmpty()) {
            return " ";
          }
          let s = `${this.items[this.front]}`;
          for (let i = this.front + 1; i < this.rear; i++) {
            s += `,${this.items[i]}`;
          }
          return s;
        }
      }