C#数据结构-队列

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

先来看下用法：

            Queue queue = new Queue();
            queue.Enqueue(1);
            queue.Enqueue(234);
            foreach (var r in queue)
            {
                Console.Write($"data:{r} ");
            }
            Console.WriteLine();
            Console.WriteLine($peek:{queue.Peek()});
            queue.Dequeue();
            queue.Enqueue(56);
            Console.WriteLine();

打印结果：

?

?

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

测试：

            MyQueue queue =  MyQueue();
            queue.Enqueue();
            queue.ShowAll();
            Console.WriteLine($);
            queue.ShowAll();
            Console.ReadLine();

实现方式：

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

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

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

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

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

打印结果：

?

?

?

?

?

（编辑：北几岛）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!