目录

一、涉及到的知识点

1.C#中的队列类

2.自定义队列的方法

(1)先设计一个CList类

(2)再设计CQueue类

二、自定义队列的实例


一、涉及到的知识点

1.C#中的队列类

        在C#中实现列类,其实队列也是链表的扩展,它是一种特殊的链表,如堆栈一样。它与堆栈的不同在于,堆栈采用的是先进后出原则,而队列采用的是先进先出原则。

        和栈相反,队列是先进先出的线性表,只允许在表的一端进行插入,而在另一端删除元素。在队列中,允许插入的一端叫做队尾,允许删除的一端称为队头。 在队列的实现过程中主要有两个操作,即入队和出队,具体如下:

  • 入队就是在队列的尾部添加数据,队列数据个数加1,尾指针后移。
  • 出队就是在队列的头部取数据,然后删除该数据,头指针后移。

2.自定义队列的方法

(1)先设计一个CList<T>类

        在这个CList<T>类的实现使用了一个私有内部类Node来表示链表中的节点。每个Node实例包含一个值(Value)和一个指向下一个节点的引用(Next)。

        CList<T>类提供了以下方法:

  • AddLast(T item):将一个元素添加到链表的末尾。
  • RemoveFirst():从链表的头部移除一个节点。如果链表为空,将抛出InvalidOperationException异常。
  • Count:获取链表中的元素数量。
  • Clear():清空链表。

(2)再设计CQueue<T>类

         在这个C#队列类CQueue<T>的实现,使用了链表类(CList)作为底层数据结构。

        这个CQueue<T>类提供了以下方法:

  • EnQueue(T item):将一个元素添加到队列的末尾。
  • DeQueue():从队列的头部移除一个元素并返回它。如果队列为空,将抛出InvalidOperationException异常。
  • Clear():清空队列。
  • QueueCount():返回队列中的元素数量。

二、自定义队列的实例

// 自定义队列类其中引用自定义的链表类的方法
namespace _134_2
{
    /// <summary>
    /// 自定义链表类
    /// </summary>
    /// <typeparam name="T">泛型运算符</typeparam>
    public class CList<T>
    {
        private class Node(T value)
        {
            public T Value = value;
            public Node? Next;
        }

        private Node? _head;
        private int _count;

        public CList()
        {
            _head = null;
            _count = 0;
        }

        public void AddLast(T item)
        {
            var newNode = new Node(item);

            if (_head == null)
            {
                _head = newNode;
            }
            else
            {
                var current = _head;
                while (current.Next != null)
                {
                    current = current.Next;
                }

                current.Next = newNode;
            }

            _count++;
        }

        public void RemoveFirst()
        {
            if (_head == null)
            {
                throw new InvalidOperationException("链表为空,无法移除元素。");
            }

            var removedNode = _head;
            _head = removedNode.Next;
            _count--;

            removedNode = null;
        }

        public int Count
        {
            get { return _count; }
        }

        public void Clear()
        {
            _head = null;
            _count = 0;
        }

        public T FirstOrDefault()
        {
            if (Count == 0)
            {
                throw new InvalidOperationException("列表为空,无法获取第一个元素。");
            }

            return Peek();
        }

        public T Peek()
        {
            if (_count == 0)
            {
                throw new InvalidOperationException("The list is empty, cannot get the first element.");
            }

            return _head!.Value;
        }
    }

    /// <summary>
    /// 自定义队列类
    /// 引用链表类CList<T>的方法
    /// </summary>
    /// <typeparam name="T">泛型运算符</typeparam>
    public class CQueue<T>
    {
        private readonly CList<T> _queue;

        public CQueue()
        {
            _queue = new CList<T>();
        }

        public void EnQueue(T item)
        {
            _queue.AddLast(item);
        }

        //public T DeQueue()
        //{
        //    if (_queue.Count == 0)
        //    {
        //        throw new InvalidOperationException("队列为空,无法出队。");
        //    }

        //    T item = _queue.First.Value;
        //    _queue.RemoveFirst();
        //    return item;
        //}

        public T DeQueue()
        {
            if (_queue.Count == 0)
            {
                throw new InvalidOperationException("队列为空,无法出队。");
            }

            T item = _queue.FirstOrDefault();
            _queue.RemoveFirst();
            return item;
        }

        public void Clear()
        {
            _queue.Clear();
        }

        public int QueueCount()
        {
            return _queue.Count;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            ArgumentNullException.ThrowIfNull(args);

            CQueue<int> queue = new();

            // 向队列中添加元素
            queue.EnQueue(1);
            queue.EnQueue(2);
            queue.EnQueue(3);

            // 查看队列中的元素数量
            Console.WriteLine("队列中的元素数量: " + queue.QueueCount);

            // 弹出第一个元素
            int dequeuedItem1 = queue.DeQueue();
            Console.WriteLine("弹出的第一个元素: " + dequeuedItem1);

            // 再次查看队列中的元素数量
            Console.WriteLine("队列中的元素数量: " + queue.QueueCount);

            // 弹出剩余的元素
            int dequeuedItem2 = queue.DeQueue();
            Console.WriteLine("弹出的第二个元素: " + dequeuedItem2);

            int dequeuedItem3 = queue.DeQueue();
            Console.WriteLine("弹出的第三个元素: " + dequeuedItem3);

            // 清空队列
            queue.Clear();

            // 查看队列是否为空
            Console.WriteLine("队列是否为空: " + queue.QueueCount == 0);
        }
    }
}
03-08 06:20