数据结构中队列(数据结构循环队列队满)

导语：技术连载：数据结构 - 队列及其变种（循环、双端、阻塞、并发）

队列

队列是一种典型的“先进先出”FIFO的数据结构；这个特点与栈正好相反；

队列的应用非常广泛，也有很多对应的变种，后面会针对常见的“循环队列”、“双端队列”、“优先级队列”、“并发队列”进行详细介绍；

队列的基本操作

入队操作（enqueue）、出队操作（dequeue）以及队列中元素的个数

队列实现

队列可以使用数组实现，也可以使用链表实现；

数组实现：

使用数组实现略微复杂，需要设定两个指针，一个指向队列头，另一个指向队列尾；

一般的入队和出队操作只需要移动指针即可，从前面的指针出队，后面的指针入队；

需要考虑的是当入队时，如果数组空间不够，这时候需要搬移元素（因为数组前面有一些已经出去的元素）；

链表实现：

链表实现相对简单，同时记录头尾结点，从尾结点入队，头结点出队即可；

特殊队列

循环队列：

循环队列主要解决数组实现队列时的数据搬移问题，同样使用数组实现，如果尾指针移动到数组最后一个元素之后，再次移动时只需要移动到第0个位置即可（如果头指针位置大于0）；

判断队列满的条件时(tail + 1) % n ==head; 当满足这个条件时表明队列已满

循环队列

双端队列：

双端队列支持从队尾插入或删除元素；也支持从队列头部插入和删除元素；java中的Deque就是双端队列的实现；

双端队列在实际应用中并没有普通队列或者栈应用广，但在某些特定场景下会特别适合，比如：判读字符串是否是回文串；

你知道双端队列的其他应用吗？欢迎留言评论~

优先级队列：

优先级队列一般通过"堆"这种数据结构来实现，队列元素的弹出顺序时根据元素的优先级进行的；插入和弹出元素的时间复杂度为O(log(n))

优先级队列的应用非常广泛，比如线程池中的某些调度机制、有限资源的使用管理（带宽管理），迪杰斯特拉算法，霍夫曼编码以及一些最佳搜索算法等。

阻塞队列

阻塞队列是在普通队列基础上增加了阻塞机制，即出队列时，如果队列为空则阻塞，直到有元素插入队列再返回；

入队列时，如果没有空闲位置，则阻塞直到有空闲位置时，再插入返回；

并发队列

即线程安全的队列

下一篇文章将分析java中的各种队列实现；