队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

队列是一种先进先出的（First In First Out）的线性表，简称 FIFO。允许插入的一端为队尾，允许删除的一端为队头。队列不允许在中间部位进行操作。

假设队列是 q=(a, a, …, a)，那么 a 就是队头元素，而 a 是队尾元素。这样我们就可以删除时，总是从 a 开始，而插入时，总是在队列最后。这也比较符合我们通常生活中的习惯，排在第一个的优先出列，最后来的当然排在队伍最后。

跟栈一样都是受限的线性表数据结构。

作为一种非常基础的数据结构，队列的应用也非常广泛，特别是一些具有某些额外特性的队列，比如循环队列、阻塞队列、并发队列。它们在很多偏底层系统、框架、中间件的开发中，起着关键性的作用。比如高性能队列 Disruptor、Linux 环形缓存，都用到了循环并发队列；Java concurrent 并发包利用 ArrayBlockingQueue 来实现公平锁等。

在结构方面，队列和栈一样

• 用数组实现的队列叫做 顺序队列
• 用链表实现的队列叫做 链式队列

对于栈来说，只需要一个栈顶指针，而对于队列，需要两个指针，一个head指针，指向队头。一个tail指针，指向队尾。

顺序队列

如下图，当a,b,c,d依次入队之后，head指针指向下标0，tail指针指向下标4的位置：

当我们调用两次出队操作之后，队列中 head 指针指向下标为 2 的位置，tail 指针仍然指向下标为 4 的位置。

类似数组，当我们进行出队，入队操作，都需要进行数据搬移。为了优化，我们可以把多次操作批量处理。出队我们不需要搬移数据，入队我们只在空间不足的时候，进行一次数据搬移操作，把原来的head到tail之间的数据，整体搬移到数组中0到tail-head的位置上。

链式队列

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

代码参考—基于链表实现的队列：https://github.com/wangzheng0822/algo/blob/81cea36eae/javascript/09_queue/QueueBasedOnLinkedList.js

循环队列

阻塞队列

普通队列

先进先出，后进后出