一、队列（queue）
队列和栈一样，在实际程序的算法设计和计算机一些其他分支里，都有很多重要的应用，比如计算机操作系统对进程 or 作业的优先级调度算法，对离散事件的模拟算法，还有计算机主机和外部设备运行速度不匹配的问题解决等，很多很多。其实队列的本质还是线性表！只不过是一种特殊的或者说是受限的线性表，是这样的：
1）、限定在表的一端插入、另一端删除。 插入的那头就是队尾，删除的那头就是队头。也就是说只能在线性表的表头删除元素，在表尾插入元素。形象的说就是水龙头和水管，流水的水嘴是队头，进水的泵是队尾，管子中间不漏水不进水。这样呲呲的流动起来，想想就是这么个过程。
2)、先进先出 (fifo结构)。显然我们不能在表（队列）的中间操作元素，只能是在尾部进，在头部出去，还可以类似火车进隧道的过程。（first in first out = fifo 结构）
注意，当队列没有元素的时候，我们就说队列是空队列。
1、双端队列
double-ended queue：限定插入和删除在表的两端进行，也是先进先出 (fifo)结构，类似铁路的转轨网络。实际程序中应用不多。
这种结构又细分为三类：
1）、输入受限的双端队列：一个端点可插入和删除，另一个端点仅可删除。
2）、输出受限的双端队列：一个端点可插入和删除，另一个端点仅可插入。
3）、等价于两个栈底相连接的栈：限定双端队列从某个端点插入的元素，只能在此端点删除。
2、链队（有链的地方，就有指针）
用链表表示的队列，限制仅在表头删除和表尾插入的单链表。一个链队列由一个头指针和一个尾指针唯一确定。（因为仅有头指针不便于在表尾做插入操作）。为了操作的方便，也给链队列添加一个头结点，因此，空队列的判定条件是：头指针和尾指针都指向头结点。
之前的链式结构，总是使用一个结点的结构来表示链表，其实不太方便，这里使用新的存储结构。定义一个结点结构，和一个队列结构。两个结构嵌套。
测试
结果：
初始化队列 queue
队尾依次插入0 1 2 3
队列第1个元素是：0
队列第2个元素是：1
队列第3个元素是：2
队列第4个元素是：3
先进先出，删除队列从头开始， 0
队列第1个元素是：1
队列第2个元素是：2
队列第3个元素是：3
先进先出，删除队列从头开始， 1
队列第1个元素是：2
队列第2个元素是：3
先进先出，删除队列从头开始， 2
队列第1个元素是：3
先进先出，删除队列从头开始， 3
销毁成功！
program ended with exit code: 0
3、顺序队列
限制仅在表头删除和表尾插入的顺序表，利用一组地址连续的存储单元依次存放队列中的数据元素。因为队头和队尾的位置是变化的，所以也要设头、尾指针。
初始化时的头尾指针，初始值均应置为 0。 入队尾指针增 1 ，出队头指针增 1 。头尾指针相等时队列为空，在非空队列里，头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。
初始为空队列，那么头尾指针相等。
入队，那么尾指针加1，头指针不变。先进先出，j1先进队，则 rear+1，尾指针始终指向队尾元素的下一位！如，j2进队，rear 继续+1，j3进队，尾指针继续加1，如图
出队，则尾指针不变，头指针加1，注意这里都是加1，先进先出原则，j1先删除，front+1，指向了 j2，j2删除，front+1指向了 j3，如图
最后，j3删除，则头指针再次和尾指针相等，说明队列空了。如图
在顺序队列中，当尾指针已经指向了队列的最后一个位置的下一位置时，若再有元素入队，就会发生“溢出”。如图位置，再次入队，就会溢出。
4、循环队列的诞生
顺序队列的 “假溢出” 问题：队列的存储空间未满，却发生了溢出。很好理解，比如 rear 现在虽然指向了最后一个位置的下一位置，但是之前队头也删除了一些元素，那么队头指针经历若干次的 +1 之后，遗留下了很多空位置，但是顺序队列还在傻乎乎的以为再有元素入队，就溢出呢！肯定不合理。故循环队列诞生！
解决“假溢出”的问题有两种可行的方法：
(1)、平移元素：把元素平移到队列的首部。效率低。否决了。
(2)、将新元素插入到第一个位置上，构成循环队列，入队和出队仍按“先进先出”的原则进行。操作效率高、空间利用率高。
虽然使用循环队列，解决了假溢出问题，但是又有新问题发生——判空的问题，因为仅凭 front = rear 不能判定循环队列是空还是满。比如如图：
这是空循环队列的样子
这是满循环队列的样子
解决办法：
(1)、另设一个布尔变量以区别队列的空和满；
(2)、少用一个元素的空间，约定入队前测试尾指针在循环下加 1 后是否等于头指针，若相等则认为队满；（最常用）
(3)、使用一个计数器记录队列中元素的总数。
对于第2个方案，必须牺牲一个元素的空间，那么入队的时候需要测试，循环意义下的加 1 操作可以描述为：
利用模运算可简化为：
基本操作
求长度
第一种情况，长度的求法
第二种情况，长度的求法，利用模运算，两个情况合二为一！
如下时为满，损失一个空间，不存储元素。方便判满
测试
结果；
循环队列初始化：
循环队列初始化后长度：
循环队列5个元素入队，总长度为5，但是损失一个位置空间，实际存储4个元素。先进先出原则：
循环队列元素0入队
循环队列元素1入队
循环队列元素2入队
循环队列元素3入队
循环队列元素遍历：
循环队列的第1个元素为0
循环队列的第2个元素为1
循环队列的第3个元素为2
循环队列的第4个元素为3
循环队列元素继续入队，无法完成：
循环队列是满的！
循环队列元素0出队之后，先进先出原则：
循环队列的第1个元素为1
循环队列的第2个元素为2
循环队列的第3个元素为3
循环队列元素1出队之后，先进先出原则：
循环队列的第1个元素为2
循环队列的第2个元素为3
循环队列元素2出队之后，先进先出原则：
循环队列的第1个元素为3
循环队列元素3出队之后，先进先出原则：
4个元素全部删除，循环队列已经空了：
队列是空的！
小结：
若用户需要循环队列，那么要设置队列的最大长度，否则无法完成判断空，如果用户不知道最大长度是多少，那么应该使用链队。队列在程序设计中和栈一样，应用很多，未完待续。
辛苦的劳动，转载请注明出处，谢谢……
http://www.cnblogs.com/kubixuesheng/p/4104802.html