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出隊時，通過頭指標后移實作出佇列，

另外未實作地方，為節省記憶體空間，陣列中出隊后的空間也要加入到后續入隊時用到的閑置位置，

以上方法都是以虛方法的方式實作的，便于后續重寫（例如執行緒安全佇列），

列印結果：

標籤：.NET技术

上一篇：技術債！ 怎樣簡潔高效的實作多個 Enum 自由轉換

下一篇：技術債！ 怎樣簡潔高效的實作多個 Enum 自由轉換