作者/EdisonZhou这是恰童鞋骚年的第篇原创文章上一篇介绍了队列的基本概念和顺序存储实现，本篇会介绍链式存储实现及循环队列。1队列的链式存储实现
跟Stack链式存储结构不同，在Queue链式存储结构中需要设置两个节点：一个head队头节点，一个tail队尾节点。现在我们来看看在链式存储结构中，如何实现Enqueue与Dequeue两个方法。
（1）入队：Enqueue
publicvoidEnQueue(Titem){NodeToldLastNode=tail;tail=newNodeT();tail.Item=item;if(IsEmpty()){head=tail;}else{oldLastNode.Next=tail;}size++;}
入队操作就是在链表的末尾插入一个新节点，将原来的尾节点的Next指针指向新节点。
（2）出队：Dequeue
publicTDeQueue(){Tresult=head.Item;head=head.Next;size--;if(IsEmpty()){tail=null;}returnresult;}
出队操作本质就是返回链表中的第一个元素即头结点，这里可以考虑到如果队列为空，将tail和head设为null以加快垃圾回收。
模拟的队列链式存储结构的完整代码如下，这里就不再做基本功能测试了，有兴趣的读者可以自行测试：
///summary///基于链表的队列节点////summary///typeparamname="T"/typeparampublicclassNodeT{publicTItem{get;set;}publicNodeTNext{get;set;}publicNode(Titem){this.Item=item;}publicNode(){}}///summary///基于链表的队列实现////summary///typeparamname="T"类型/typeparampublicclassMyLinkQueueT{privateNodeThead;privateNodeTtail;privateintsize;publicMyLinkQueue(){this.head=null;this.tail=null;this.size=0;}///summary///入队操作////summary///paramname="node"节点元素/parampublicvoidEnQueue(Titem){NodeToldLastNode=tail;tail=newNodeT();tail.Item=item;if(IsEmpty()){head=tail;}else{oldLastNode.Next=tail;}size++;}///summary///出队操作////summary///returns出队元素/returnspublicTDeQueue(){Tresult=head.Item;head=head.Next;size--;if(IsEmpty()){tail=null;}returnresult;}///summary///是否为空队列////summary///returnstrue/false/returnspublicboolIsEmpty(){returnthis.size==0;}///summary///队列中节点个数////summarypublicintSize{get{returnthis.size;}}}2循环队列
首先，我们来看看下面的情景，在数组容量固定的情况下，队头指针之前有空闲的位置，而队尾指针却已经指向了末尾，这时再插入一个元素时，队尾指针会指向哪里？
图1
从图中可以看出，目前如果接着入队的话，因数组末尾元素已经占用，再向后加，就会产生数组越界的错误，可实际上，我们的队列在下标为0和1的地方还是空闲的。我们把这种现象叫做“假溢出”。现实当中，你上了公交车，发现前排有两个空座位，而后排所有座位都已经坐满，你会怎么做？立马下车，并对自己说，后面没座了，我等下一辆？没有这么笨的人，前面有座位，当然也是可以坐的，除非坐满了，才会考虑下一辆。
所以解决假溢出的办法就是后面满了，就再从头开始，也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。在循环队列中需要注意的几个问题是：
（1）入队与出队的索引位置如何确定？
这里我们可以借助%运算对head和tail两个指针进行位置确定，实现方式如下所示：
//移动队尾指针tail=(tail+1)%items.Length;//移动队头指针head=(head+1)%items.Length;
（2）在队列容量固定时如何判断队列空还是队列满？
①设置一个标志变量flag，当head==tail，且flag=0时为队列空，当head==tail，且flag=1时为队列满。
②当队列空时，条件就是head=tail，当队列满时，我们修改其条件，保留一个元素空间。也就是说，队列满时，数组中还有一个空闲单元。如下图所示：
图2
从上图可以看出，由于tail可能比head大，也可能比head小，所以尽管它们只相差一个位置时就是满的情况，但也可能是相差整整一圈。所以若队列的最大尺寸为QueueSize，那么队列满的条件是(tail+1)%QueueSize==head（取模“%”的目的就是为了整合tail与head大小为一个问题）。比如上面这个例子，QueueSize=5，图中的左边front=0，而rear=4，(4+1)%5=0，所以此时队列满。再比如图中的右边，front=2而rear=1。(1+1)%5=2，所以此时队列也是满的。
（3）由于tail可能比head大，也可能比head小，那么队列的长度如何计算？
当tailhead时，此时队列的长度为tail-head。但当tailhead时，队列长度分为两段，一段是QueueSize-head，另一段是0+tail，加在一起，队列长度为tail-head+QueueSize。因此通用的计算队列长度公式为：(tail-head+QueueSize)%QueueSize。
3小结本文介绍了队列的链式存储实现及循环队列，下一篇会介绍队列的常见应用场景及.NET中的队列QueueT的实现要点。
5参考资料程杰，《大话数据结构》陈广，《数据结构（C#语言描述）》段恩泽，《数据结构（C#语言版）》往期精彩回顾每天5分钟用C#学习数据结构（12）
每天5分钟用C#学习数据结构（11）
每天5分钟用C#学习数据结构（10）
每天5分钟用C#学习数据结构（9）
每天5分钟用C#学习数据结构（8）
点个“在看”/转发朋友圈就是对我最大的支持
??点击阅读原文，获取文章源码
预览时标签不可点