队列(Queue)的基本结构_queue物理结构

定义： 队列(Queue) 是一种只在表的一端进行插入，而在另一端进行删除的数据结构。

队头(front) 允许删除的一端，永远指向第一个元素前一个位置。
队尾(rear) 允许插入的一端，永远是指向队列最后一个元素
先进先出(First In First Out)的线性表，简称FIFO表
空队列 当队列中没有元素

上溢和下溢
当队列满时再入队会产生空间溢出，简称“上溢”;当队列空时再出队也会产生溢出，简称“下溢”。上溢是一种出错状态，应该避免；下溢则是正常现象。
假上溢：

因为在入队和出队的操作中，头尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。因此，尽管队列中实际的元素个数远远小于向量空间的规模，但也可能由于尾指针巳超出向量空间的上界而不能做入队操作。该现象称为假上溢。

队尾指针为5，队头指针为1，此时尾指针已经指向了顺序队列最后一个元素，但可以看到0，1两个
并没有被使用，此时就为假上溢。
顺序队列
定义： 队列的顺序存储结构简称顺序队列。

完整代码
基于 JS 数组实现，由于 JS 数组能够自动扩容，所以没有上溢问题。并且原生实现了队列方法。
 

class ArrayQueue {
  constructor() {
    this.queue = [];
  }
  // 入队
  enqueue(value) {
    return this.queue.push(value);
  }
  // 出队
  dequeue() {
    return this.queue.shift();
  }
  // 取队头元素
  peek() {
    return this.queue[0];
  }
  // 判断队列是否为空
  isEmpty() {
    return this.queue.length === 0;
  }
  // 取队列有多少个元素
  size() {
    return this.queue.length;
  }
  // 清空队列
  clear() {
    this.queue = [];
  }
}

基于 JS 对象实现。不存在上溢和假上溢问题。

class ObjectQueue {
  constructor() {
    this.queue = {};
    this.end = -1;
    this.front = -1;
  }
   // 入队
  enqueue(value) {
    if (this.front === -1) {
      this.front++;
    }
    this.queue[++this.end] = value;
  }
  // 出队
  dequeue() {
    if (!this.isEmpty()) {
      const res = this.queue[this.front];
      delete this.queue[this.front++];
      return res;
    }
    return null;
  }
  // 取队头元素
  peek() {
    if (!this.isEmpty()) {
      return this.queue[this.front];
    }
    return null;
  }
  // 判断队列是否为空
  isEmpty() {
    return this.front > this.end;
  }
  // 取队列有多少个元素
  size() {
    return this.end - this.front + 1;
  }
  // 清空队列
  clear() {
    this.queue = {};
    this.front = -1;
    this.end = -1;
  }
}

为了解决假上溢问题，引入循环队列，即把向量空间想象为一个首尾相接的圆环，在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（MAXNUM-1）时，其加1操作的结果是指向向量的下界0。

但是引进的循环队列又出现了新的问题，看图：

判空和判满两种方法
即队空和队满的时都满足q->front==q->rear，我们无法利用这个条件判断队空还是队满！！！该怎么解决这个问题呢？有两种方法：

少用一个数据元素空间，以队尾指示器加 l等于队头指示器判断队满，即队满条件为:
(q-> rear+l)％MAXNUM==q->front
使用一个计数器记录队列中元素的总数（实际上是队列长度）。
第一种方法实现
 

class LoopArrayQueue{
  constructor() {
    this.MAXNUM = 5;
    this.queue = new Array(this.MAXNUM);
    this.front = 0;
    this.rear = 0;
  }
  // 入队
  enqueue(value) {
    if ((this.rear + 1) % this.MAXNUM === this.front) {
      console.log('队列已满，入队失败');
      return;
    }
    this.rear++;
    this.queue[this.rear % this.MAXNUM] = value;
  }
  // 出队
  dequeue() {
  	if(!this.isEmpty()) {
    	this.front++;
    	const res = this.queue[this.front % this.MAXNUM];
    	this.queue[this.front % this.MAXNUM] = undefined;
    	return res;
    }
    return undefined;
  }
  // 取队头元素
  peek() {
    return this.queue[(this.front + 1) % this.MAXNUM];
  }
  // 判断队列是否为空
  isEmpty() {
    return this.front === this.rear;
  }
  // 取队列有多少个元素
  size() {
    return this.rear - this.front;
  }
  // 清空队列
  clear() {
    this.queue = new Array(this.MAXNUM);
    this.front = 0;
    this.rear = 0;
  }
}

第二种方法实现

class LoopArrayQueue{
  constructor() {
    this.MAXNUM = 5;
    this.queue = new Array(this.MAXNUM);
    this.front = -1;
    this.rear = -1;
    this.count = 0;
  }
  // 入队
  enqueue(value) {
    if (this.count === this.MAXNUM) {
      console.log('队列已满，入队失败');
      return;
    }
    this.count++;
    this.rear++;
    this.queue[this.rear % this.MAXNUM] = value;
  }
  // 出队
  dequeue() {
    if (this.count > 0){
      this.front++;
      this.count--;
      const res = this.queue[this.front % this.MAXNUM];
      this.queue[this.front % this.MAXNUM] = undefined;
      return res;
    }
    return undefined;
  }
  // 取队头元素
  peek() {
    return this.queue[(this.front + 1) % this.MAXNUM];
  }
  // 判断队列是否为空
  isEmpty() {
    return this.count === 0;
  }
  // 取队列有多少个元素
  size() {
    return this.count;
  }
  // 清空队列
  clear() {
    this.count = 0;
    this.front = -1;
    this.rear = -1;
    this.queue = new Array(this.MAXNUM);
  }
}

链队列
定义： 队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。 显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。于是，一个链队列由头指针和尾指针唯一确定。

注意：虽然 JS 并没有指针的概念，但是对于对象这样的类型，对象的名字本质上就相当于指针。

虽然 JS 中数组实现了在队列的方法，但是它本质上还是数组操作，所以若从数组头部删除一个元素，那么在 JS 引擎内部还是需要移动后边的数组元素，很耗费性能。但是链式存储结构删除和添加元素复杂度为 O1。

节点存储结构：
 

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

判断队空
注意：有 JS 本身并无指针概念，所以再实现“链队”时必须要定义一个变量 count 记录队列中元素个数，由 count == 0 作为判空条件。

而其他语言（例如 c 语言）链队队空条件是pointer->front->next == NULL && pointer->rear->next == NULL而不是pointer->front == pointer->rear这是因为当队空的时候pointer->front和pointer->rear的值不一样。

原因： 如上图所示，当创建空链队时，队列头指针、尾指针都指向上图中黑色节点（这个黑色节点相当于顺序队列的-1，是一个初始节点），当链队列添加元素后尾指针会改变它指向的节点，此时pointer->rear的值是它指向的尾结点的地址。而当队列删除元素时，改变的是黑色节点的 next 指针（这样做是为了使头指针满足它的特点，具体看上边队列特点），这样pointer->front的值永远是黑色节点的地址。所以pointer->front和pointer->rear的值不一样，不能作为判断队空的条件。

出队列：

当使用其它语言（例如 c 语言）时此功能需要注意的就是当队列只剩一个元素时，即pointer->front->next == pointer->rear，而你要删除此元素，就需要先改变尾指针指向的节点，再删除，释放最后一个元素节点的内存。因为如果你不改变的话，则尾指针是指向最后一个元素节点的，而你删除释放最后一个元素节点的内存后，此时pointer->rear->next是一个野指针（野指针的危害就不用我说了吧！！！）。
 

class LinkQueue {
  constructor() {
    const node = new Node();
    this.count = 0;
    this.head = node;
    this.rear = node;
  }
  // 入队
  enqueue(value) {
    const node = new Node(value);
    this.rear.next = node;
    this.rear = node;
    this.count++;
  }
  // 出队
  dequeue() {
    if (!this.isEmpty()) {
      const res = this.head.next.value;
      this.head.next = this.head.next.next;
      this.count--;
      if (this.isEmpty()) {
        this.rear = this.head;
      }
      return res;
    }
    return null;
  }
  // 取队头元素
  peek() {
    if (!this.isEmpty()) {
      return this.head.value;
    }
    return null;
  }
  // 判断是否为空
  isEmpty() {
    return this.count === 0;
  }
  // 返回队列元素个数
  size() {
    return this.count;
  }
  // 清空队列
  clear() {
    const node = new Node();
    this.count = 0;
    this.head = node;
    this.rear = node;
  }
}