队列-阿里云开发者社区

开发者社区> 云计算> 正文

队列

简介:

1、顺序结构描述的队列

在这一章中,我们选择用Rear队尾的指针来指示最后一个入队的元素在队列中的位置。我们选择队列内存储的数组的Data[0]作为队头,每次取数据的时候,队头弹出(out)。具体的代码如下所示:

 

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

 

namespace DataStructure.Queue

{

    class SeqQueue<T>: IQueue<T>

    {

 

        int Rear =-1;//队尾

        constint MaxSize=100;//队列的最大容量

        T[] Data =new T[MaxSize];//一个数组

        public SeqQueue()

        {

 

        }

        public SeqQueue(T[] data)

        {

            Array.Copy(data,this.Data,data.Length);

            Rear = data.Length -1;

        }

 

 

        publicint GetLength(out States states)

        {

            if(Rear==-1)

            {

                states = States.Fail;

                return0;

            }

            else

            {

                states = States.Success;

                return Rear +1;

            }

        }

        publicbool IsEmpty()

        {

            return Rear ==-1?true:false;

         }

 

        publicvoid Clear()

        {

            Rear =-1;

        }

        privatebool isFull(){

            return Rear +1== MaxSize ?true:false;

        }

        publicvoid In(T item,out States states)

        {

            if(isFull())

            {

                states = States.Fail;

                return;

            }

            this.Data[++Rear]= item;

            states = States.Success;

 

        }

 

        public T Out(out States states)

        {

            //判断队列是否为空

            if(IsEmpty())

            {

                states = States.Fail;

                returndefault(T);

            }

           

            States mStates;

            //当队列中只有一个元素的时候

            if(this.GetLength(out mStates)==1)

            {

                Rear--;

                states = States.Success;

                returnthis.Data[0];

            }

            //普通的情况

        

            //(1)将所有元素往前移动一位

            T DataToOut=this.Data[0];

            for(int i =1; i <this.GetLength(out mStates); i++)

            {

                this.Data[-1]=this.Data[i];

            }

            --Rear;

            states = States.Success;

            //(2)返回要弹出的值

            return DataToOut;

        }

 

        public T GetFront(out States states)

        {

            if(this.IsEmpty()==true)

            {

                states = States.Fail;

                returndefault(T);

            }

            else

            {

                states= States.Success;

                return Data[0];//返回队头的元素

            }   

        }

    }

}

 

从代码的实现上看,这种实现的方式有一种明显缺点:那就是每次当我们出队一个元素的时候,我们都需要将除队头外的元素全部往前移动一个,这样子的时间复杂度为O(n)。我们将在循环队列中讨论相应的解决方案。

2、循环队列

在循环队列中,比较困难的地方就是在队列长度和是否为满的判断。由于这方面的教程很多,大家可自行百度。另外,队头(Front)和队尾(Rear)的初始化位置(比如以下代码中是Front=0,Rear=0,如果改为Front=0,Rear=-1呢?)将会极大地影响代码的书写。

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

 

namespace DataStructure.Queue

{

    /// <summary>

    /// 循环队列

    /// </summary>

    class CSeqQueue<T>: IQueue<T>

    {

        int Front =0;//队头

        int Rear =0;//队尾

        constint MaxSize =4;//队列的最大容量

        T[] Data =new T[MaxSize];//一个数组

        public CSeqQueue()

        {

 

        }

        public CSeqQueue(int[] data)

        {

            Array.Copy(data,this.Data, data.Length);

            Rear = data.Length -1;

        }

 

 

        publicint GetLength()

        {

            return(Rear - Front + MaxSize)% MaxSize;

        }

 

        publicbool IsEmpty()

        {

            returnthis.GetLength()==0?true:false;

        }

 

        publicvoid Clear()

        {

            Front =0;//队头

            Rear =0;//队尾

        }

        publicbool isFull()

        {

            return(Rear +1)% MaxSize == Front ?true:false;

 

        }

        publicvoid In(T item,out States states)

        {

            if(isFull())

            {

                states = States.Fail;

                return;

            }

 

            this.Data[Rear]= item;

            Rear =(Rear +1)% MaxSize;

            states = States.Success;

        }

 

        public T Out(out States states)

        {

            if(IsEmpty())

            {

                states = States.Fail;

                returndefault(T);

            }

            T dataToOut =this.Data[Front];

            Front =(Front +1)% MaxSize;

            states = States.Success;

            return dataToOut;

        }

 

        public T GetFront(out States states)

        {

            thrownew NotImplementedException();

        }

    }

}

 

2、链队

由单链表的实现,我们可知单链表有一个Head字段,通过Head字段我们可以遍历单链表。在链队中,我们打算直接利用Head字段,只不过我们将其命名Front。通常当我们需要遍历一个单链表时,我们得从链表头遍历都最后,才能找到链表尾。这样操作的话,时间复杂度为O(n),我们打算引用Rear字段,用来指示每次新入队的元素。

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

 

namespace DataStructure.Queue

{

    class LinkQueue<T>:IQueue<T>

    {

 

        class Node<T>

        {

 

            private T data;

            /// <summary>

            /// 数据域

            /// </summary>

            public T Data

            {

                get {return data;}

                set { data = value;}

            }

 

 

            private Node<T> next;

            /// <summary>

            /// 引用域

            /// </summary>

            public Node<T> Next

            {

                get {return next;}

                set { next = value;}

            }

 

            //头结点构造函数

            public Node(Node<T> node)

                :this(default(T), node)

            {

            }

            //普通结点构造函数

            public Node(T data, Node<T> node)

            {

                this.Data = data;

                this.Next = node;

            }

            /// <summary>

            /// 空构造函数

            /// </summary>

            public Node()

                :this(default(T),null)

            {

            }

            //尾结点构造函数

            public Node(T data)

                :this(data,null)

            {

 

            }

        }

        private Node<T> Front;//队头

        private Node<T> Rear;//队尾

 

        publicbool IsEmpty()

        {

            return Front ==null?true:false;

       

        }

 

        publicvoid Clear()

        {

            Front =null;

        }

 

        publicvoid In(T item,out States states)

        {

            if(IsEmpty())

            {

                Front =new Node<T>(item);

                states = States.Success;

                Rear = Front;

            }

            else

            {

                Node<T> newNode=new Node<T>(item);

                Rear.Next = newNode;

                Rear = newNode;

                states = States.Success;

            }

       

        }

 

        public T Out(out States states)

        {

            if(this.IsEmpty())

            {

                states = States.Fail;

                returndefault(T);

            }

            else

            {

                states = States.Success;

                T DataToOut =this.Front.Data;

                Front = Front.Next;

                return DataToOut;

            }

        }

 

        public T GetFront(out States states)

        {

            if(this.IsEmpty())

            {

                states = States.Fail;

                returndefault(T);

            }

            else

            {

                states = States.Success;

                returnthis.Front.Data;

            }

        }

 

        publicint GetLength()

        {

            if(IsEmpty())

            {

                return0;

            }

            int Lenth=0;//长度

            for(Node<T> last = Front; last.Next !=null; last=last.Next)

            {

                Lenth++;

            }

            return Lenth;

 

        }

    }

}

 本文转自陈哈哈博客园博客,原文链接http://www.cnblogs.com/kissazi2/p/3203428.html如需转载请自行联系原作者


kissazi2

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
云计算
使用钉钉扫一扫加入圈子
+ 订阅

时时分享云计算技术内容,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。

其他文章