面试题-数组、链表实现队列

先来看看什么是队列，摘自百科：

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

队列和栈一样同样是一种特殊的数据结构，就像去医院排队体检一样，排在队伍头部(head)的人进行体检，新来的人站到队伍的尾部(tail)。包含入队(enqueue)和出队(dequeue)两个操作，特点是先进先出，后进后出。

数组实现队列（顺序队列） :

首先1、2入队，然后进行了两次出队操作，正常出队，当第三次出队时报出队列为空的提示，功能正常。

再看下这幅图，两次入队、两次出队，按理说队列此时为空，当再次入队操作时，提示队列满了，其实这个时候队列中已经没有了元素，只不过head、tail指针相等并且都指向了capacity的元素索引，无法新元素入队，那么该如何解决呢？

改造一下入队方法，在入队时如果发现tail=capatiy、head=0此时队列满了，如果head!=0则说明队列还有空余的空间，此时进行数据迁移，重置head、tail的位置。

链表实现队列（链式队列）：

队列的实际应用：

1.阻塞队列，队列为空时在对头取数据会被阻塞，直到队列中有数据了才会返回，如果队列已满，那么插入操作就被阻塞，直到队列有空闲位置后再插入数据。

2.线程池的队列，请求线程池时，如果核心线程都已经被使用，那么请求存入队列中。