共计 1888 个字符，预计需要花费 5 分钟才能阅读完成。
简介
基本概念
队列这个概念很好了解，队列常做的比喻就是排队买票，先到的先买，后到的只能在队尾等着。
队列是一种受限的线性表，非凡之处在于它只容许在一端插入，在另一端删除，因而是先进入队列的元素能最先从队列中删除，故队列又被称为 先进先出表。
操作
队列与栈十分类似，反对的操作也很无限。以下是队列的一些概念：
- 进行插入操作的端称为 队尾
- 进行删除操作的端称为 队头
- 队列中没有元素时，称为 空队列
- 向队列中插入一个元素称为 入队
- 删除队列中的一个元素称为 出队
队列的实现
队列能够应用数组或链表作为物理存储构造，应用数组实现的队列称为程序队列，应用链表实现的队列称为链式队列。
程序队列
应用数组实现的程序队列比实现残缺性能的数组更加简略，不须要实现往数组中插入元素和删除数组内元素的性能。
首先，须要申请一个大小为 n 的数组；而后，创立一个队头变量和队尾变量；当入队时，须要将队尾变量后移一位；当出队时，也须要将队头变量后移一位。
当数组无限大的时候，这样的实现形式没有任何问题。但数组向来是限度大小的，而且出队之后，数组的前半部分曾经没有数据存储了，十分节约空间。
对于这种状况，通常采纳 搬移数据 的方法，当队尾变量标识曾经达到 n 的下标时，则做一次数据搬移，并且将队头变量标识和队尾变量标识指向新的下标。
以这种实现思路，入队的均摊工夫复杂度为 $O(1)$，出队的工夫复杂度始终都是 $O(1)$。
链式队列
应用链表实现的链式队列比应用数组实现的程序队列更加不便，缩小了搬移数据的这一步。
链表不须要提前申请内存空间，也不须要放心内存空间不够的问题，只须要创立好队头变量标识和队尾变量标识即可，链式队列是常见的队列实现形式。
如果是采纳尾插法实现的链表，能够将链表的哨兵结点的指向作为队头变量标识，这样只须要新增一个队尾变量标识即可。当新的元素入队时，将这个元素链接到尾结点，而后批改队尾变量标识的指向；须要出队时，则做删除头结点的操作，批改哨兵结点的指向。
以链表实现的队列，无论是入队还是出队，工夫复杂度都能够达到 $O(1)$。
循环队列
程序队列在入队时会有搬移数据的状况，存在肯定的性能损耗，循环队列则是在这一方面做了局部优化，缩小这一步操作。
如果把数组看作一条直线，就能够把循环队列看作一个环，通过做成环的形式，胜利防止了数据搬移的操作。
如上图所示，通常会有一个 front 指针指向队头所在地址，有一个 rear 指针指向队尾的下一个地址，其起因次要是：若 front 和 rear 别离指向队头和队尾，无奈判断队空和存在一个元素的状态。
若采纳 rear 指针指向队尾的下一个地址的形式，则能够应用 front 和 rear 指向同一个地址来判断队空；同时，因为循环队列是逻辑上循环，通常应用求余运算判断队满，并且为了防止队空呈现的 rear % n = front 和队满呈现的 (rear + n) % n = front 造成过错，因而总是留出一个空位，应用 (rear + 1) % n = front 判断队满。
双端队列
双端队列是一种具备队列和栈的性质的数据结构，即常说的 deque(double-ended queue)，是一种限定插入和删除操作在表的两端进行的线性表。
现实生活中双端队列的例子：如果在电影院买票，一个刚刚买完票的人想征询一下简略信息，就能够间接回到队伍的头部，如果在队尾排队的人不想看电影了，就能够从队尾间接来到队伍。
只管双端队列看起来仿佛比栈和队列更灵便，但实际上在应用程序中远不迭栈和队列有用。
利用场景
队列的利用场景十分宽泛，尤其是一些带有非凡性质的队列，在各自的利用场景蛟龙得水。
阻塞队列
阻塞队列是在队列的根底上减少了阻塞的个性。
当队列为空的时候，出队的操作会被阻塞，直到队列中有数据；当队列满了的时候，入队的操作也会被阻塞，直到队列中有闲暇地位能够插入数据。
常见的场景就是“生产者 – 消费者”模型，应用阻塞队列能够无效地协调生产和生产的速度。
并发队列
并发队列指的是在多线程情景下，多个线程同时操作队列，而这个队列如果是线程平安的，则被称为并发队列。
实现并发队列最简略的形式就是在入队、出队的时候加锁，然而这会影响队列的并发量，队列在同一时刻仅能解决一个存取操作。
实际上应用循环队列，并应用 CAS 原子操作，能够实现十分高效的无锁并发队列。
优先队列
优先队列是在队列的概念上，对元素赋予优先级，拜访时是具备最高优先级的元素先出队。
通常优先队列会应用堆来实现，如大根堆就很好的示意了根结点是优先级最高的元素。当出队时能够先删除根结点，而后从上往下堆化；入队时则须要从下往上堆化。
能够看出，优先队列其实是堆的一种应用形式，赋予了队列的名称，放弃和一般队列雷同的操作方法。
