定义

先进者先出。就按照平时排队的的形式理解，先到先得。

操作特性

和数据结构：栈一样，也是“操作受限”的线性表，只允许在一端插入和删除数据。相比于数据结构：数组和数据结构：链表，更少的操作结构，意味着更加可控，不易出错的状态。

顺序队列：用数组实现的队列

优点：队列大小有限，超出队列的请求会被拒绝，适合时间敏感系统缺点：不容易设计合适队列大小，太大导致等待的请求太多，小了会导致无法利用系统资源、发挥最大性能。

class ArrayQueue {
  private items: string[]; // 数组
  private n: number; // 数组大小
  private head = 0; // 队头指针
  private tail = 0; // 队尾指针
 
  // 初始化数组，申请一个大小为 n 的数组空间
  constructor(n: number) {
    this.items = [];
    this.n = n;
  }
 
  // 入队操作
  enqueue(element: string): boolean {
    // 如果 tail 指针和 n 相等，表示队列已满，无法再加入元素
    if (this.tail === this.n) {
	    // tail === n & head === 0，表示整个队列都占满了
	    if (head === 0) return false
	    // 在这里进行一次性集体数据搬移，避免每次出队都搬移一次数据，将出队时间复杂度从 O(n) 降低至 O(1)
		for (let i = head; i< tail; i++) {
			items[i - head] = items[i]
		}
		// 搬移完之后重新更新 head 和 tail
		tail -= head
		head = 0
    }
    this.items[this.tail] = element;
    this.tail++;
    return true;
  }
 
  // 出队操作
  dequeue(): string | null {
    // 如果 head 指针和 tail 相等，表示队列为空，无法再弹出元素
    if (this.head === this.tail) return null;
    const element = this.items[this.head];
    this.head++;
    return element;
  }
}

链式队列：基于链表的队列实现方法

优点：可以实现无限支持排队的无界队列缺点：可能导致排队时间过长，不适合响应时间敏感的系统

class LinkedNode {
  constructor(element) {
    this.element = element;
    this.next = null;
  }
}
 
class QueueBasedOnLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }
 
  enqueue(value) {
    if (this.head === null) {
      this.head = new LinkedNode(value);
      this.tail = this.head;
    } else {
      this.tail.next = new LinkedNode(value);
      this.tail = this.tail.next;
    }
  }
 
  dequeue() {
    if (this.head !== null) {
      const value = this.head.element;
      this.head = this.head.next;
      return value;
    } else {
      return -1;
    }
  }
}

循环队列：避免顺序队列中的数据搬移

// 这里的难点在于队空和队满的判断
class CircularQueue {
  private items: string[];
  private n: number;
  private head = 0;
  private tail = 0;
 
  constructor(n: number) {
    this.items = new Array(n);
    this.n = n;
  }
 
  enqueue(item: string): boolean {
    // 队列满了
    if ((this.tail + 1) % this.n == this.head) return false;
    this.items[this.tail] = item;
    this.tail = (this.tail + 1) % this.n;
    return true;
  }
 
  dequeue(): string | null {
    if (this.head === this.tail) return null;
    const ret = this.items[this.head];
    this.head = (this.head + 1) % this.n;
    return ret;
  }
}

生产中用的队列

大部分资源有限的场景，当没有空闲资源时，基本都可以通过”队列”数据结构来实现排队。

阻塞队列

在队列为空时，从队头取数据会被阻塞，只有队列有了数据才能返回。
在队列满时，从队尾取数据会被阻塞，只有队列有空闲位置才能插入数据。
“生产者（head）-消费者（tail）模型”下，通过配置“生产者”和“消费者”的个数，来提高数据的处理效率。（分布式构建？）

并发队列

基于数组的循环队列，利用 CAS 原子操作，实现高效的并发队列。比如 Disruptor

以我所主，为我所用

探索

数据结构：队列

定义