用顺序队列解决队列的编程问题

亦凉 2021-09-18 07:50 224阅读 0赞

用顺序队列解决队列的编程问题:

队列（Quene）是一种特殊的线性表，是一种只允许在表的一端进行插入操作而在另一端进行删除操作的线性表。把进行插入操作的表尾称为队尾（rear），把进行删除操作的头部称为队头（front）。当队列中没有数据元素时称为空队列。

队列操作按照的原则：先进先出，后进后出。

判断队列是否为满的操作只在存储结构为顺序结构时才需要，而在链式存储结构中不会对队列的长度有限制。尽管IsFull方法只在顺序存储结构中才需要实现，但还是把它定义在接口，其目的是为应用程序提供一个统一的接口，使应用程序在使用队列表示数据时，不必考虑是顺序存储还是链式存储。

当有数据元素入队时，队尾指示器rear加1；当有数据元素出队时，队头指示器front加1；当front=rear时，队列为空。

解决“假溢出”的方法是：将顺序队列看成首尾相接的循环结构，头尾指示器的关系不变，这种队列叫“循环顺序队列”。

循环顺序队列中，队尾指示器rear的值不一定大于队头指示器的值front的。

**判断循环顺序队列是否已满**（循环队列为满时有两种情况，一种是当队列还没有一个元素出队，队头指示器front的值为-1，二队尾指示器的值为maxsize-1，即：front ==-1&&rear ==maxsize -1)；另一种情况就不说了，即：

front ==-1&&rear ==maxsize -1 或者 front ==(rear +1)%maxsize

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70][]

** 获取循环队列的长度**：(rear - front + maxsize) % maxsize

**获取队头数据元素**：data\[(front + 1) % maxsize\]

**入队操作**： rear = (rear + 1) % maxsize;  
                   data\[rear\] = elem;

**出队操作**： front = (front + 1) % maxsize;  
                   return data\[front\];

**判断循环顺序队列是否为空**：front ==rear

**清空循环顺序队列**：front = rear = -1

代码实现：

using System;
    
    namespace 用顺序队列解决队列的编程问题
    {
        class Program
        {
            static void Main(string[] args)
            {
    
            }
        }
        interface IQuene<T>
        {
            void EnQuene(T elem);//入队列
            T DeQuene();//出队列
            T GetFront();//取队头元素
            int GetLength();//求队列长度
            bool IsEmpty();//判断队列是否为空
            bool IsFull();//判断队列是否已满
            void Clear();//清空队列
        }
    
        class CSeqQuene<T>:IQuene <T>
        {
            private int maxsize;//循环顺序队列的容量
            private T[] data;//数组，用于存储循环顺序队列中的数据元素
            private int front;//循环顺序队列的队头。指示最近一个已经离开队列的元素所占的位置
            private int rear;//循环顺序队列的队尾。指示最近一个进行入队列的元素的位置
    
            //以下是用Ctrl+R Ctrl+E自动生成的get，set属性
            public int Maxsize { get => maxsize; set => maxsize = value; } //容量属性
            public T[] Data { get => data; set => data = value; }//索引器
            public int Front { get => front; set => front = value; }//队头属性
            public int Rear { get => rear; set => rear = value; }//队尾属性
    
            //初始化队列
            public CSeqQuene() { } 
            public CSeqQuene (int size)
            {
                data = new T[size];
                maxsize = size;
                front = rear = -1;
            }
    
            /// <summary>
            /// 清空循环顺序队列
            /// </summary>
            public void Clear()
            {
                front = rear = -1;
            }
    
            /// <summary>
            /// 判断循环顺序队列是否为空
            /// </summary>
            /// <returns></returns>
            public bool IsEmpty()
            {
                if(front ==rear)
                {
                    return true;
                }else
                {
                    return false;
                }
            }
    
            /// <summary>
            /// 判断循环顺序队列是否已满
            /// </summary>
            /// <returns></returns>
            public bool IsFull()
            {
                if((front ==-1&&rear ==maxsize -1)||front ==(rear +1)%maxsize)
                {
                    return true;
                }else
                {
                    return false;
                }
            }
    
            /// <summary>
            /// 获取循环队列的长度
            /// </summary>
            /// <returns></returns>
            public int GetLength()
            {
                return (rear - front + maxsize) % maxsize;
            }
    
            /// <summary>
            /// 获取队头数据元素
            /// </summary>
            /// <returns></returns>
            public T GetFront()
            {
                if(IsEmpty())
                {
                    Console.WriteLine("Quene is empty");
                    return default(T);
                }
                return data[(front + 1) % maxsize];//重难点
            }
    
            /// <summary>
            /// 入队操作
            /// </summary>
            /// <param name="elem"></param>
            public void EnQuene(T elem)
            {
                if(IsFull())
                {
                    Console.WriteLine("Quene is Full ");
                }
                rear = (rear + 1) % maxsize;
                data[rear] = elem;
    
            }
    
            /// <summary>
            /// 出队操作
            /// </summary>
            /// <returns></returns>
            public T DeQuene()
            {
                if(IsEmpty())
                {
                    Console.WriteLine("Quene is empty");
                    return default(T);
                }
                front = (front + 1) % maxsize;
                return data[front];
            }
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70]: /images/20210725/d40682c23a82471484bef9144199ed63.png