转：queue

数据结构C#版笔记--队列(Quene)

队列(Quene)的特征就是“先进先出”，队列把所有操作限制在"只能在线性结构的两端"进行，更具体一点：添加元素必须在线性表尾部进行，而删除元素只能在线性表头部进行。

先抽象接口IQuene<T>

下面是基于数组实现的示意图：

实现思路：用一个数组存放所有元素，同时设置二个关键变量front与rear用于记录队列“头”与“尾”的元素下标，当有元素入列时rear加1，当有元素出队时front+1，而rear-front即为队列实际元素的总数.

但有一种“队列伪满”的特殊情况要注意，如下图：

这张图上面的部分：假设经过入队、出队一番折腾后，rear已经指向数组的下标最大值，而front指向在中间(即front之间的元素已经出队不用考虑了，相当于front下标前面的内存区域空闲)，如果这时再有一个元素入列，rear+1就超出数组下标的最大值了，但是从图上一眼就能看出，实际上front前面还空着一堆位置可以重复利用，队列并非真正的“满”--这种情况称为伪满，为了解决这个问题，我们可以把数组想象为首尾相接的循环结构，即图中下面部分，这时候可以让rear重新指向到0，以便重复利用空闲的位置。

所以：入列时rear++的操作，应该稍做修正，当rear到数组下标最大值时，让它置0，以便能循环利用 (见后面的代码)

另外还有一个问题：最开始时front与rear都为-1，即front==rear时表示队列为空，改成循环以后，有可能会出现rear在循环过程中碰到front的情况，即真正意义的上"满"状态，这时rear也同样等于front，这样就无法单纯的用rear==front来判断是满，还是空？这时可以浪费一个元素的位置，认为当rear+1==front时，队列就已经满了，虽然牺牲了一个元素的空间，但却换来了逻辑的正确性，还是值得的。

完整实现如下：

测试代码片段：

当然，队列也可以用链表来实现，相对要容易很多。

先定义链表中的节点Node.cs

为了方便，定义了很多构造函数的重载版本，当然这些只是浮云，重点是理解结构：data用来保存数据，next指出下一个节点是谁

链式队列的完整实现LinkQueue.cs

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

using System;
using System.Text;
 
namespace 栈与队列
{
    public class LinkQueue:IQueue
    {
        private Node front;//队列头
        private Node rear;//队列尾
        private int num;//队列元素个数
 
 
        /// 
        /// 构造器
        /// 
        public LinkQueue() 
        {
            //初始时front,rear置为null，num置0
            front = rear = null;
            num = 0;
        }
 
        public int Count() 
        {
            return this.num;
        }
 
 
        public void Clear() 
        {
            front = rear = null;
            num = 0;
        }
 
        public bool IsEmpty() 
        {
            return (front == rear && num == 0);
        }
 
        //入队
        public void Enqueue(T item) 
        {
            Node q = new Node(item);
 
            if (rear == null)//第一个元素入列时
            {
                front = rear = q;
            }
            else
            {
                //把新元素挂到链尾
                rear.Next = q;
                //修正rear指向为最后一个元素
                rear = q;
            }
            //元素总数+1
            num++;
        }
 
        //出队
        public T Dequeue() 
        {
            if (IsEmpty()) 
            {
                Console.WriteLine("Queue is empty!");
                return default(T);
            }
 
            //取链首元素
            Node p = front;
 
            //链头指向后移一位
            front = front.Next;
 
            //如果此时链表为空，则同步修正rear
            if (front == null) 
            {
                rear = null;
            }
 
            num--;//个数-1
 
            return p.Data;
        }
 
 
        public T Peek() 
        {
            if (IsEmpty()) 
            {
                Console.WriteLine("Queue is empty!");
                return default(T);
            }
 
            return front.Data;
        }
 
 
        public override string ToString()
        {
            if (IsEmpty()) {
                Console.WriteLine("Queue is empty!");
            }
 
            StringBuilder sb = new StringBuilder();
 
            Node node = front;
 
            sb.Append(node.Data.ToString());
 
            while (node.Next!=null)
            {
                sb.Append("," + node.Next.Data.ToString());
                node = node.Next;
            }
 
            return sb.ToString().Trim(',');
        }
    }
}

作者：菩提树下的杨过
出处：http://yjmyzz.cnblogs.com
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。

如果觉得文章对您有帮助，请不吝点个赞，表示一下支持！谢谢！