队列

队列的结构

队列是一种“先进先出，后进后出”的结构，

队列既可以用数组实现，也可以用链表实现，用数组实现的叫顺序队列，用链表实现的叫链式队列。

队列的应用

循环队列、阻塞队列、并发队列会用在一些底层的开发中

循环队列:如果一个队列中，已经有些元素已经被移除之后(在数组中实际是调用)，队头就会有一些空队列，那么这时如果tail已经满了，入队列的元素就可以往已经被移除的空位置去存储。

在一般队列中:队列空:head==tail 队列满: tail==size

在循环队列中:队列空:head==tail 队列满: (tail+1)%n==head

阻塞队列:就是在队列的基础，添加阻塞操作，比如说你想取出队列的数据，但是队列中并没有数据，这时就会阻塞这个取数据的操作直到队列中有了数据。如果你想往队列中插入数据，但这时队列已经满了就会阻塞插入数据的操作直到队列中有空的位置。就像在线程池中请求请求网络的操作，这时线程池已经满了，一种是直接拒绝请求的非阻塞操作，一种是等待线程池有空余线程的阻塞操作。

并发队列:如果多个线程对同一个队列进程操作，就会可能出现线程安全问题，一个线程安全的队列就叫并发队列。最简单多线程访问就是用锁，但是同一时刻只允许一个存或取操作。

数组实现队列

大致思路是，先定义一个预知大小n的数组，然后用两个int变量分别指向头尾:head、tail。入队列的时候先判断队列是否满了tail==n,tail变量+1。出队列的时候先判断是否队列空head==tail，head往上+1。循环队列的实现也一样，就是判断队列是否满的时候是:(tail+1)%n==head.

image

数组实现队列

链表实现队列

大致思路是，先定义两个结点tail、head,当tail为空时就是第一次加入队列，那么两个结点都被赋值，其他入队列的话，就是tail.next指向新的元素，然后tail被赋值于tail.next.当出队列的时候一要做判空处理，二要做最后一个元素出队处理，Head被赋值为head.next

image

链表实现队列