专栏首页菩提树下的杨过数据结构C#版笔记--队列(Quene)

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

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

先抽象接口IQuene<T>

namespace 栈与队列
{
    public interface IQuene<T>
    {
        /// <summary>
        /// 取得队列实际元素的个数
        /// </summary>
        /// <returns></returns>
        public int Count();

        /// <summary>
        /// 判断队列是否为空
        /// </summary>
        /// <returns></returns>
        public bool IsEmpty();

        /// <summary>
        /// 清空队列
        /// </summary>
        public void Clear();

        /// <summary>
        /// 入队(即向队列尾部添加一个元素)
        /// </summary>
        /// <param name="item"></param>
        public void Enquene(T item);

        /// <summary>
        /// 出队(即从队列头部删除一个元素)
        /// </summary>
        /// <returns></returns>
        public T Dequene();

        /// <summary>
        /// 取得队列头部第一元素
        /// </summary>
        /// <returns></returns>
        public T Peek();
    }
}

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

实现思路:用一个数组存放所有元素,同时设置二个关键变量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时,队列就已经满了,虽然牺牲了一个元素的空间,但却换来了逻辑的正确性,还是值得的。

完整实现如下:

using System;
using System.Text;

namespace 栈与队列
{
    /// <summary>
    /// 循环顺序队列
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class CSeqQueue<T>:IQueue<T>
    {
        private int maxsize;
        private T[] data;
        private int front;
        private int rear;       


        public CSeqQueue(int size) 
        {
            data = new T[size];
            maxsize = size;
            front = rear = -1;
        }

        public int Count()         
        {
            if (rear > front)
            {
                return rear - front;
            }
            else
            {
                return (rear - front + maxsize) % maxsize;
            }
        }


        public void Clear() 
        {
            front = rear = -1;
        }

        public bool IsEmpty() 
        {
            return front == rear;            
        }

        public bool IsFull() 
        {           
            if (front != -1) //如果已经有元素出队过
            {
                return (rear + 1) % maxsize == front;//为了区分与IsEmpty的区别,有元素出队过以后,就只有浪费一个位置来保持逻辑正确性.
            }
            else 
            {
                return rear == maxsize - 1;
            }            
        }

        public void Enqueue(T item) 
        {
            if (IsFull()) 
            {
                Console.WriteLine("Queue is full");
                return;
            }
            if (rear == maxsize - 1) //如果rear到头了,则循环重来(即解决伪满问题)
            {
                rear = 0;
            }
            else 
            {
                rear++;
            }
            data[rear] = item;
        }


        public T Dequeue() 
        {            
            if (IsEmpty()) 
            {
                Console.WriteLine("Queue is empty");
                return default(T);
            }
            if (front == maxsize - 1) //如果front到头了,则重新置0
            {
                front = 0;
            }
            else 
            {
                front++;
            }            
            return data[front];
        }

        public T Peek() 
        {
            if (IsEmpty()) 
            {
                Console.WriteLine("Queue is empty!");
                return default(T);
            }
            return data[(front + 1) % maxsize];            
        }

        public override string ToString()
        {
            if (IsEmpty()) { return "queue is empty."; }

            StringBuilder sb = new StringBuilder();

            if (rear > front)
            {
                for (int i = front + 1; i <= rear; i++)
                {
                    sb.Append(this.data[i].ToString() + ",");
                }
            }
            else 
            {
                for (int i = front + 1; i < maxsize; i++)
                {
                    sb.Append(this.data[i].ToString() + ",");
                }

                for (int i = 0; i <= rear; i++)
                {
                    sb.Append(this.data[i].ToString() + ",");
                }
            }
            return "front = " + this.front + " \t rear = " + this.rear + "\t count = " + this.Count() + "\t data = " +  sb.ToString().Trim(',');
        }
    }
}

测试代码片段:

            CSeqQueue<int> queue = new CSeqQueue<int>(5);
            queue.Enqueue(1);
            queue.Enqueue(2);
            queue.Enqueue(3);
            queue.Enqueue(4);
            Console.WriteLine(queue);//front = -1       rear = 3        count = 4       data = 1,2,3,4
            queue.Dequeue();
            Console.WriteLine(queue);//front = 0        rear = 3        count = 3       data = 2,3,4
            queue.Dequeue();
            Console.WriteLine(queue);//front = 1        rear = 3        count = 2       data = 3,4
            queue.Enqueue(5);
            Console.WriteLine(queue);//front = 1        rear = 4        count = 3       data = 3,4,5
            queue.Enqueue(6);
            Console.WriteLine(queue);//front = 1        rear = 0        count = 4       data = 3,4,5,6
            queue.Enqueue(7);        //Queue is full
            Console.WriteLine(queue);//front = 1        rear = 0        count = 4       data = 3,4,5,6
            queue.Dequeue();
            queue.Enqueue(7);
            Console.WriteLine(queue);//front = 2        rear = 1        count = 4       data = 4,5,6,7

            queue.Clear();
            Console.WriteLine(queue);//queue is empty.

            queue.Enqueue(1);
            queue.Enqueue(2);
            queue.Enqueue(3);
            queue.Enqueue(4);
            Console.WriteLine(queue);//front = -1       rear = 3        count = 4       data = 1,2,3,4
            queue.Enqueue(5);
            Console.WriteLine(queue);//front = -1       rear = 4        count = 5       data = 1,2,3,4,5
            queue.Enqueue(6);        //Queue is full
            Console.WriteLine(queue);//front = -1       rear = 4        count = 5       data = 1,2,3,4,5
            queue.Dequeue();
            queue.Dequeue();
            queue.Dequeue();
            queue.Dequeue();
            Console.WriteLine(queue);//front = 3        rear = 4        count = 1       data = 5
            queue.Dequeue();
            Console.WriteLine(queue);//queue is empty.
            queue.Enqueue(0);
            queue.Enqueue(1);
            queue.Enqueue(2);
            queue.Enqueue(3);
            queue.Enqueue(4);        //Queue is full
            Console.WriteLine(queue);//front = 4        rear = 3        count = 4       data = 0,1,2,3
            Console.WriteLine(queue.Peek());//0
            queue.Dequeue();
            Console.WriteLine(queue);//front = 0        rear = 3        count = 3       data = 1,2,3
            queue.Dequeue();
            Console.WriteLine(queue);//front = 1        rear = 3        count = 2       data = 2,3
            queue.Dequeue();
            Console.WriteLine(queue);//front = 2        rear = 3        count = 1       data = 3
            queue.Dequeue();
            Console.WriteLine(queue);//queue is empty.
            queue.Enqueue(9);
            Console.WriteLine(queue);//front = 3        rear = 4        count = 1       data = 9
            Console.ReadLine();

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

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

namespace 栈与队列
{
    public class Node<T>
    {
        private T data;

        private Node<T> next;

        public Node(T data, Node<T> next) 
        {
            this.data = data;
            this.next = next;
        }

        public Node(Node<T> next) 
        {
            this.next = next;
            this.data = default(T);
            
        }

        public Node(T data) 
        {
            this.data = data;
            this.next = null;
        }

        public Node() 
        {
            this.data = default(T);
            this.next = null;
        }

        public T Data {
            get { return this.data; }
            set { this.data = value; }
        }

        public Node<T> Next 
        {
            get { return next; }
            set { next = value; }
        }
    }
}

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

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

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(',');
        }
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 温故而知新:设计模式之工厂模式(Factory)

    工厂模式:个人理解为主要用于创建"同一系列"的N个对象实例。(注意这里"同一系列"指这一系列对象均继承于某一个抽象类或均实现了某一个接口) 举例:(仍然来自李建...

    菩提树下的杨过
  • 温故而知新:设计模式之抽象工厂(AbstractFactory)

    抽象工厂主要用来解决多个系列的对象实例问题。 问题的应用场景(来源于李建忠老师的webcast讲座): 如果有一款游戏,里面有"道路,房屋,隧道,丛林"这四类基...

    菩提树下的杨过
  • 温故而知新:设计模式之Builder

    Builder模式主要用于以下场景: 需要创建一个较复杂的大对象实例,并且构成该对象的子对象可能经常会发生变化,但是组成大对象的算法却相对稳定。 比如:我们做b...

    菩提树下的杨过
  • Enterprise Library深入解析与灵活应用(9):个人觉得比较严重的关于CachingCallHandler的Bug

    微软EnterLib的Policy Injection Application Block(PIAB)是一个比较好用的轻量级的AOP框架,你可以通过创建自定义的...

    蒋金楠
  • 还在用SimpleDateFormat?Java8都发布N年了,转LocalDateTime吧

    Java8发布,已有数年之久,但是发现很多人都还是坚持着用SimpleDateFormat和Date进行时间操作。SimpleDateFormat这个类不是线程...

    Happyjava
  • Google 开源的依赖注入库,比 Spring 更小更快!

    Guice是Google开源的一个依赖注入类库,相比于Spring IoC来说更小更快。Elasticsearch大量使用了Guice,本文简单的介绍下Guic...

    良月柒
  • 【一起学系列】之迭代器&组合:虽然有点用不上啦

    【产品】:嘿,有一个好消息,咱们旗下的餐厅把月巴克的咖啡店吞并了!太棒了!年终奖稳了!

    Kerwin
  • .NET IoC模式依赖反转(DIP)、控制反转(Ioc)、依赖注入(DI)

    依赖倒置(Dependency Inversion Principle,缩写DIP)是面向对象六大基本原则之一。他是指一种特定的的解耦形式,使得高层次的模块不依...

    HueiFeng
  • Caffe 实践 - 基于 ResNet101 的 Multi-label 多标签标注的训练与部署

    以前曾尝试过修改 Caffe ImageDataLayer 源码的方式来读取多个 labels - ImageMultilabelDataLayer [Caff...

    AIHGF
  • 【源码】基于FPGA的PPPoE协议获取账号密码的攻击实现

    对于PPPOE认证上网的过程如下图所示,分为发现阶段和会话阶段,发现阶段分为PADI,PADO,PADR,PADS。

    网络交换FPGA

扫码关注云+社区

领取腾讯云代金券