作者/EdisonZhou这是恰童鞋骚年的第篇原创文章上一篇介绍完了操作受限的线性表-栈。本篇开始介绍另一种操作受限的线性表-队列。1队列的基本概念
在日常生活中，队列的例子比比皆是，例如在车展排队买票，排在队头的处理完离开，后来的必须在队尾排队等候。在程序设计中，队列也有着广泛的应用，例如计算机的任务调度系统、为了削减高峰时期订单请求的消息队列等等。与栈类似，队列也是属于操作受限的线性表，不过队列是只允许在一端进行插入，在另一端进行删除。在其他数据结构如树的一些基本操作中（比如树的广度优先遍历）也需要借助队列来实现，因此这里我们来看看队列。
队列的基本特征
队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。它是一种先进先出（FirstInFirstOut）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。
队列的基本操作
（1）入队（Enqueue）：将一个数据元素插入队尾；
（2）出队（Dequeue）：读取队头节点数据并删除该节点；
2队列的顺序存储实现既然队列也属于特殊的线性表，那么其实现也会有两种形式：顺序存储结构和链式存储结构。
首先，对于Queue，我们希望能够提供以下几个方法供调用：
QueueT()
创建一个空的队列
voidEnqueue(Ts)
往队列中添加一个新的元素
TDequeue()
移除队列中最早添加的元素
boolIsEmpty()
队列是否为空
intSize()
队列中元素的个数
OK，废话不多说了，开始用我们最熟悉的C#来实现一个顺序存储方式的队列吧！
与Stack不同，在队列中我们需要定义一个head队头“指针”和tail队尾“指针”，当新元素入队时tail+1，当老元素出队时head+1。
下面重点来看看Enqueue和Dequeue两个方法的代码实现。
publicvoidEnQueue(Titem){if(Size==items.Length){//扩大数组容量ResizeCapacity(items.Length*2);}items[tail]=item;tail++;size++;}
新元素入队后，tail队尾指针向前移动指向下一个新元素要插入的位置；这里仍然模仿.NET中的实现，在数组容量不足时及时进行扩容以容纳新元素入队。
（2）出队：Dequeue
publicTDeQueue(){if(Size==0){returndefault(T);}Titem=items[head];items[head]=default(T);head++;if(head0Size==items.Length/4){//缩小数组容量ResizeCapacity(items.Length/2);}size--;returnitem;}
在对老元素进行出队操作时，首先取得head指针所指向的老元素，然后将head指针向前移动一位指向下一个将出队的老元素。这里将要出队的元素所在数组中的位置重置为默认值。最后判断容量是否过小，如果是则进行数组容量的缩小。
下面是完整的队列模拟实现代码，仅供参考，这里就不再做基本功能测试了，有兴趣的读者可以自行测试：
///summary///基于数组的队列实现////summary///typeparamname="T"类型/typeparampublicclassMyArrayQueueT{privateT[]items;privateintsize;privateinthead;privateinttail;publicMyArrayQueue(intcapacity){this.items=newT[capacity];this.size=0;this.head=this.tail=0;}///summary///入队////summary///paramname="item"入队元素/parampublicvoidEnQueue(Titem){if(Size==items.Length){//扩大数组容量ResizeCapacity(items.Length*2);}items[tail]=item;tail++;size++;}///summaryv///出队////summary///returns出队元素/returnspublicTDeQueue(){if(Size==0){returndefault(T);}Titem=items[head];items[head]=default(T);head++;if(head0Size==items.Length/4){//缩小数组容量ResizeCapacity(items.Length/2);}size--;returnitem;}///summary///重置数组大小////summary///paramname="newCapacity"新的容量/paramprivatevoidResizeCapacity(intnewCapacity){T[]newItems=newT[newCapacity];intindex=0;if(newCapacityitems.Length){for(inti=0;iitems.Length;i++){newItems[index++]=items;}}else{for(inti=0;iitems.Length;i++){if(!items.Equals(default(T))){newItems[index++]=items;}}head=tail=0;}items=newItems;}///summary///队列是否为空////summary///returnstrue/false/returnspublicboolIsEmpty(){returnthis.size==0;}///summary///队列中节点个数////summarypublicintSize{get{returnthis.size;}}}3小结
本文介绍了队列的基本概念及其顺序存储方式的实现，下一篇我们会介绍其链式存储方式的实现以及循环队列！
4参考资料程杰，《大话数据结构》陈广，《数据结构（C#语言描述）》段恩泽，《数据结构（C#语言版）》往期精彩回顾每天5分钟用C#学习数据结构（11）
每天5分钟用C#学习数据结构（10）
每天5分钟用C#学习数据结构（9）
每天5分钟用C#学习数据结构（8）
每天5分钟用C#学习数据结构（7）
点个“在看”/转发朋友圈就是对我最大的支持
??点击阅读原文，获取文章源码
预览时标签不可点收录于话题#个上一篇下一篇