用链队列解决队列的编程问题

╰+攻爆jí腚メ 2021-09-18 08:20 305阅读 0赞

用链队列解决队列的编程问题：

队列的另外一种存储方式是链式存储，这样的队列称为链队列（Linked Quene）。

链式队列的结点结构：

![2019022710403553.png][]

链队列的结构示意图：

![20190227102623522.png][]

初始化队列： front = rear = null;    size = 0;

清空链队列： front = rear = null;    size = 0;

求队列长度：return size;

判断链队列是否为空：size ==0 && front ==rear

获取链队列头结点的值：front.Data;

入队：rear.Next = newNode;  
                rear = newNode;

出队：front = front.Next;

代码实现：

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 QueneNode<T>
        {
            private T data;//数据域
            private QueneNode<T> next;//引用域
    
            public T Data { get => data; set => data = value; }//数据域属性
            public QueneNode<T> Next { get => next; set => next = value; }//引用域属性
    
            //构造函数
            public QueneNode()
            {
                data = default(T);
                next = null;
            }
            public QueneNode (T val)
            {
                data = val;
                next = null;
            }
            public QueneNode (QueneNode <T> p)
            {
                data = default(T);
                next = p;
            }
            public QueneNode (T val,QueneNode <T> p)
            {
                data = val;
                next = p;
            }
        }
    
        class LinkQuene<T> : IQuene<T>
        {
            private QueneNode<T> front;//队头指示器
            private QueneNode<T> rear;//队尾指示器
            private int size;//队列结点个数
    
            public QueneNode<T> Front { get => front; set => front = value; }
            public QueneNode<T> Rear { get => rear; set => rear = value; }
            public int Size { get => size; set => size = value; }
    
            /// <summary>
            /// 初始化链队列
            /// </summary>
            public LinkQuene()
            {
                front = rear = null;
                size = 0;
            }
    
           /// <summary>
           /// 清空链队列
           /// </summary>
            public void Clear()
            {
                front = rear = null;
                size = 0;
            }
    
            /// <summary>
            /// 求队列长度
            /// </summary>
            /// <returns></returns>
            public int GetLength()
            {
                return size;
            }
    
            /// <summary>
            /// 判断链队列是否为空
            /// </summary>
            /// <returns></returns>
            public bool IsEmpty()
            {
                if((size ==0)&&(front ==rear))
                {
                    return true;
                }else
                {
                    return false;
                }
            }
    
            /// <summary>
            /// 获取链队列头结点的值
            /// </summary>
            /// <returns></returns>
            public T GetFront()
            {
                if(IsEmpty())
                {
                    Console.WriteLine("Quene is empty");
                    return default(T);
                }
                return front.Data;
            }
    
            /// <summary>
            /// 入队操作
            /// </summary>
            /// <param name="elem"></param>
            public void EnQuene(T elem)
            {
                QueneNode<T> newNode = new QueneNode<T>(elem);
                if(IsEmpty())
                {
                    front = newNode;
                    rear = newNode; 
                }else
                {
                    rear.Next = newNode;
                    rear = newNode;//重难点
                }
                size++;
            }
    
            /// <summary>
            /// 出队操作
            /// </summary>
            /// <returns></returns>
            public T DeQuene()
            {
                if(IsEmpty())
                {
                    Console.WriteLine("Quene is empty");
                    return default(T);
                }
    
                //重难点
                QueneNode<T> p = front;
                front = front.Next;//如果有2个及以上的结点
                if(front ==null) //如果只有1个结点
                {
                    rear = null;
                }
    
                size--;
                return p.Data;
            }
    
            [Obsolete ("此函数无用。因为链队列对容量没有影响，所以返回false")]
            public bool IsFull()
            {
                return false;
            }
        }
    }

[2019022710403553.png]: /images/20210725/800f1e569b134fc381e24f1b26e5bd91.png
[20190227102623522.png]: /images/20210725/642d20ca21fd4a6db8a3011097a08816.png