队列

队列

先进者先出，后进者后出，这就是典型的“队列”

顺序队列

队列可以用数组来实现，也可以用链表来实现。用数组实现的栈叫作顺序栈，用链表实现的栈叫作链式栈。同样，用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。

队列需要两个指针：一个是 head 指针，指向队头；一个是 tail 指针，指向队尾。随着不停地进行入队、出队操作，head 和 tail 都会持续往后移动。当 tail 移动到最右边，即使数组中还有空闲空间，也无法继续往队列中添加数据了。如果没有空闲空间了，我们只需要在入队时，再集中触发一次数据的搬移操作。

链式队列

基于链表的实现，我们同样需要两个指针：head 指针和 tail 指针。它们分别指向链表的第一个结点和最后一个结点。如图所示，入队时，tail->next= new_node, tail = tail->next；出队时，head = head->next。

循环队列

循环队列，顾名思义，它长得像一个环。原本数组是有头有尾的，是一条直线。现在把首尾相连，扳成了一个环。
环形队列的关键在于确定好队空和队满的判定条件。假定头指针为head，尾指针为tail，队列为空的判断条件是 head == tail，队列满时，需要牺牲一个空间完成，当队满时，(tail+1)%n=head，此时tail指向的指针是没有存储数据。

阻塞队列

阻塞队列其实就是在队列基础上增加了阻塞操作。简单来说，就是在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。

并发队列

线程安全的队列，简单直接的实现方式是直接在 enqueue()、dequeue() 方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或者取操作。实际上，基于数组的循环队列，利用 CAS 原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。