C#数据结构-队列

当前位置:

首页 > temp > C#教程 >

C#数据结构-队列

队列作为线性表的另一个数据结构，只允许在表的前端进行删除操作，而在表的后端进行插入操作，和栈一样，队列是一种操作受限制的线性表。

先来看下用法：

            Queue queue = new Queue();
            queue.Enqueue(1);
            queue.Enqueue(2);
            queue.Enqueue(3);
            queue.Enqueue(4);
            foreach (var r in queue)
            {
                Console.Write($"data:{r} ");
            }
            Console.WriteLine();
            Console.WriteLine($"peek:{queue.Peek()}");
            queue.Dequeue();
            queue.Enqueue(5);
            queue.Enqueue(6);
            Console.WriteLine();

打印结果：

    public class MyQueue
    {
        /// <summary>
        /// 存储栈结构
        /// </summary>
        public object[] content { get; set; }
        /// <summary>
        /// 队列第一个节点
        /// </summary>
        public int head { get; set; }
        /// <summary>
        /// 对列最后一个节点
        /// </summary>
        public int tail { get; set; }
        /// <summary>
        /// 队列长度
        /// </summary>
        public int size { get; set; }
        /// <summary>
        /// 增长因子 100 == 1.0
        /// </summary>
        public int growFactor { get; set; }
        /// <summary>
        /// 最小增加量
        /// </summary>
        private const int minimumGrow = 4;
        private const int _ShrinkThreshold = 32;
        /// <summary>
        /// 初始化
        /// </summary>
        public MyQueue()
            : this(32, (float)2.0)
        {
        }
        /// <summary>
        ///
        /// </summary>
        /// <param name="capacity">队列长度</param>
        /// <param name="growFactor">增长因子</param>
        public MyQueue(int capacity, float _growFactor)
        {
            if (capacity < 0)
                throw new ArgumentOutOfRangeException("参数错误");
            if (!(_growFactor >= 1.0 && _growFactor <= 10.0))
                throw new ArgumentOutOfRangeException("增长因子不在范围内");
            content = new Object[capacity];
            head = 0;
            tail = 0;
            size = 0;
            growFactor = (int)(_growFactor * 100);
        }
        /// <summary>
        /// 在队列尾处添加节点
        /// </summary>
        /// <param name="obj"></param>
        public virtual void Enqueue(object obj)
        {
            if (size == content.Length)
            {
                //计算扩展后的队列长度
                int newCapacity = (int)(content.Length * growFactor / 100);
                if (newCapacity < content.Length + newCapacity)
                {
                    newCapacity = content.Length + minimumGrow;
                }
                SetCapacity(newCapacity);
            }
            content[tail] = obj;
            tail = (tail + 1) % content.Length;
            size++;
        }
        /// <summary>
        /// 在队列头部出栈
        /// </summary>
        /// <returns></returns>
        public virtual Object Dequeue()
        {
            if (size == 0)
                throw new IndexOutOfRangeException("空队列");
            object rem = content[head];
            content[head] = null;
            head = (head + 1) % content.Length;
            size--;
            return rem;
        }
        public virtual Object Peek()
        {
            if (size == 0)
                throw new IndexOutOfRangeException("空队列");
            return content[head];
        }
        /// <summary>
        /// 扩展队列
        /// </summary>
        /// <param name="capacity"></param>
        private void SetCapacity(int capacity)
        {
            object[] newArray = new object[capacity];
            if (size > 0)
            {
                if (head < tail)
                {
                    Array.Copy(content, head, newArray, 0, size);
                }
                else
                {
                    Array.Copy(content, head, newArray, 0, content.Length - head);
                    Array.Copy(content, 0, newArray, content.Length - head, head);
                }
            }
            content = newArray;
            head = 0;
            tail = (size == capacity) ? 0 : size;
        }
        public void ShowAll()
        {
            for (int i = head; i < size; i++)
            {
                Console.Write($"index:{i},data:{content[i]}    ");
            }
            Console.WriteLine("——————————————————————");
        }
    }

测试：

            MyQueue queue = new MyQueue();
            queue.Enqueue(1);
            queue.Enqueue(2);
            queue.Enqueue(3);
            queue.Enqueue(4);
            queue.ShowAll();
            Console.WriteLine($"peek:{queue.Peek()}");
            queue.Dequeue();
            queue.Enqueue(5);
            queue.Enqueue(6);
            queue.ShowAll();
            Console.ReadLine();

实现方式：

通过object对象数组，存储队列中的节点数据，另外定义两个指针分别指向队列的头部节点以及尾部节点。

Enqueue入队时，（如果队列长度达到数组最大长度，则通过扩展数组（队列长度 * 增长因子）来增加数组长度）通过在对尾附加节点来实现的。

Dequeue出队时，通过头指针后移实现出队列。

另外未实现地方，为节省内存空间，数组中出队后的空间也要加入到后续入队时用到的闲置位置。

以上方法都是以虚方法的方式实现的，便于后续重写（例如线程安全队列）。

打印结果：

本文链接：https://www.cnblogs.com/xtt321/p/13850391.html

栏目列表