数据结构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(',');
        }
    }
}

 

时间： 2024-03-18 23:05:13

数据结构C#版笔记--队列(Quene)的相关文章

数据结构C#版笔记--树与二叉树

图1 上图描述的数据结构就是"树",其中最上面那个圈圈A称之为根节点(root),其它圈圈称为节点(node),当然root可以认为是node的特例. 树跟之前学习过的线性结构不同,它是一对多的非线性结构,具有二个基本特点: 1.根节点(root)没有前驱节点,除root之外的所有节点有且只有一个前驱节点2.树中的所有节点都可以有0个或多个后继节点. 所以下面这些歪瓜咧枣,不能算是树: 图2 下是是一些烦人但是很重要的术语:  1.结点(Node):表示树中的数据元素,由数据项和数据元

数据结构C#版笔记--堆栈(Stack)

堆栈(Stack)最明显的特征就是"先进后出",本质上讲堆栈也是一种线性结构,符合线性结构的基本特点:即每个节点有且只有一个前驱节点和一个后续节点. 相对前面学习过的顺序表.链表不同的地方在于:Stack把所有操作限制在"只能在线性结构的某一端"进行,而不能在中间插入或删除元素.下面是示意图: 从示意图中可以看出,堆栈有二种实现方式:基于数组的顺序堆栈实现.类似链表的链式堆栈实现 先抽象堆栈的接口IStack: namespace 栈与队列 { public int

数据结构C#版笔记--顺序表(SeqList)

线性结构(Linear Stucture)是数据结构(Data Structure)中最基本的结构,其特征用图形表示如下: 即:每个元素前面有且只有一个元素(称为"前驱"),同样后面有且只有一个元素(称为"后继")--注:起始元素的前驱认为是空,末尾元素的后继认为也是空,这样在概念上就不冲突了. 线性表(List)是线性结构的一种典型实现,它又可以分为:顺序表(SeqList)和链表(LinkList)二大类. 顺序表(SeqList)的基本特征为:元素在内部存储时

数据结构C#版笔记--单链表(LinkList)

上一篇学习了"顺序表(SeqList)",这一篇来看下"单链表(LinkList)".在上一篇的最后,我们指出了:顺序表要求开辟一组连续的内存空间,而且插入/删除元素时,为了保证元素的顺序性,必须对后面的元素进行移动.如果你的应用中需要频繁对元素进行插入/删除,那么开销会很大.   而链表结构正好相反,先来看下结构: 每个元素至少具有二个属性:data和next.data用来存放数据,而next用来指出它后面的元素是谁(有点"指针"的意思). 链

数据结构与算法C#版笔记--排序(Sort)-下

5.堆排序(HeapSort) 在接触"堆排序"前,先回顾一下数据结构C#版笔记--树与二叉树 ,其中提到了"完全二叉树"有一些重要的数学特性: 上图就是一颗完全二叉树,如果每个节点按从上到下,从左至右标上序号,则可以用数组来实现顺性存储,同时其序号: 1.如果i>1,则序号为i的父结节序号为i/2(这里/指整除) 言外之意:整个数组前一半都是父节点,后一半则是叶节点 2.如果2*i<=n(这里n为整颗树的节点总数),则序号为i的左子节点序号为2*i 3

数据结构与算法C#版笔记--查找(Search)

做数据库开发的程序员,可能每天都会处理各种各样的查询sql,这个就是查找(Search).通过查询记录主键字段(即主关键码)或其它非唯一字段(即次关键码)找到所需要的记录. 如果在查找的过程中,不改变原始数据(的数据结构),则这种查找称为静态查找(Static Search):如果找不到,需要向数据库里插入记录(或者找到了,需要从数据库里删除),这种在查找过程中需要动态调整原始数据(的数据结构),这种查找称为动态查找(Dynamic Search). 被查找的数据结构(比如数据库中的某张表)称为

数据结构 单链表-求大神给我讲讲数据结构单链表和队列

问题描述 求大神给我讲讲数据结构单链表和队列 帮我彻底分析下两种结构,感激不尽多谢大神了 解决方案 单链表和队列是两个层次的事情. 单链表是一种基本的表示一个线性表的方式,它记录下当前节点的数据和指向下一个节点的指针.因此一环一环可以得到整个数据.除了单链表,我们还有数组.双向链表.循环链表等. 队列是一种先进先出的数据结构,它高于链表一个层次,这是说,你可以用链表实现队列(当然也可以用数组或者别的).另外还有先进后出的数据结构(堆栈)等. 解决方案二: 具体你可以google下wikipedi

c c++-数据结构，栈和队列，问题

问题描述 数据结构,栈和队列,问题 已知Q 是一个非空队列,S 是一个空栈,借助队列和栈的ADT 函数,将队列Q的所有元素逆置 解决方案 数据结构-栈和队列数据结构-栈和队列<数据结构>第三章 栈和队列问题回收站 解决方案二: 将队列元素都出队到栈中,再将栈中的数据入队 解决方案三: http://zhidao.baidu.com/link?url=dOiiECx8cRRi-hWjhDyWkIJoYigGhttDvdFnx28a9RNh35ddFDuTlXCINA7CCIriyrMRlHDUp

Python实现的数据结构与算法之队列详解_python

本文实例讲述了Python实现的数据结构与算法之队列.分享给大家供大家参考.具体分析如下: 一.概述 队列(Queue)是一种先进先出(FIFO)的线性数据结构,插入操作在队尾(rear)进行,删除操作在队首(front)进行. 二.ADT 队列ADT(抽象数据类型)一般提供以下接口: ① Queue() 创建队列 ② enqueue(item) 向队尾插入项 ③ dequeue() 返回队首的项,并从队列中删除该项 ④ empty() 判断队列是否为空 ⑤ size() 返回队列中项的个数 队