Queue--队列

淩亂°似流年 2022-02-03 16:25 273阅读 0赞

队列（Queue）和栈不同，队列是只允许在一端插入，在另一端进行删除的线性表，所有的插入操作都在队尾进行，删除操作则在队头进行。入队和出队顺序一样。

由于数组在删除元素的时候，需要花费大量时间移动元素，所以基于数组的队列很少有实际应用，多采用循环队列方式。

本文主要介绍也是循环队列，将一个一维数组中各个元素看成一个首尾相接的封闭圆环。

两个基本操作：

入队： Enqueue： 将一个数据插入队尾

出队：Dequeue：读取队头节点的数据，并删除该结点

代码实现：

//存放元素的数组
            private object[] _array;
            //增长因子(动态改变队列大小)
            private int _growFactory;
            //头指针(index)
            private int _head;
            //最小增长值
            private const int _MinimumGrow = 4;
            //初始容量（16进制20，表示10进制32，可存放32个元素）
            private const int _ShrinkThreshold = 0x20;
            //元素个数
            private int _size;
            public int Count
            {
                get
                {
                    return _size;
                }
            }
    
    
            //尾指针（index）
            private int _tail;
    
    
    
            //（指定初始容量，增长因子）
            public MyQueue(int capacity,float growFactory)
            {
                if (capacity<0)
                {
                    throw new ArgumentOutOfRangeException("capacity", "Cant Less Zero");
                }
                if ((growFactory < 1) || (growFactory > 10)) 
                {
                    //1--10之间
                    throw new ArgumentOutOfRangeException("growFactory", "增长因子处于1--10之间");
                }
                //数组初始化
                this._array = new object[capacity];
                this._head = 0;
                this._tail = 0;
                this._size = 0;
                this._growFactory = (int)(growFactory * 100f);
            }
    
            public MyQueue():this(_ShrinkThreshold,2f)
            {
    
            }

出队，入队操作
      //出队
            public object Dequeue()
            {
                if (this._size == 0) 
                {
                    //对下溢
                    throw new InvalidOperationException("队列为空");
                }
                object obj = this._array[this._head];
                this._array[this._head] = null;
                //移动队头指针(让队头指针正确指向对头位置，防止假溢出现象)
                this._head = (this._head + 1) % this._array.Length;
                this._size--;
                return obj;
            }
            
            //入队
            public void Enqueue(object obj)
            {
                if (this._size==this._array.Length)
                {
                    //满员
                    int capacity = (int)((this._array.Length * this._growFactory) / 100L);
                    if (capacity < this._array.Length + _MinimumGrow) 
                    {
                        //有最少增长量
                        capacity = this._array.Length + _MinimumGrow;
                    }
                    SetCapacity(capacity);
                }
                //放到新的队尾
                this._array[_tail] = obj;
                //校正尾指针 位置指向
                _tail = (_tail + 1) % _array.Length;
                _size++;
            }
    
            //内存转移
            private void SetCapacity(int capacity)
            {
                //开辟新的内存空间
                object[] newArr = new object[capacity];
                //头指针在前
                if (_head < _tail) 
                {
                    Array.Copy(this._array, _head, newArr, 0, _size);
                }
                else
                {
                    //尾指针在前
                    //先移动头指针后面的元素，再移动头指针和尾指针之间的
                    Array.Copy(_array, _head, newArr, 0, _array.Length - _head);
                    Array.Copy(_array, 0, newArr, _array.Length - _head, _tail);
                }
                this._array = newArr;
                this._head = 0;
                this._tail = (this._size == capacity) ? 0 : this._size;
            }

空间每次增长为原来的2倍。队列初始化可存放32个元素，0x20 十六进制20，表示十进制32

入队操作的时候，发生队上溢时，开辟新的内存空间，增长最小空间为4.

入队时，队尾指针算法 Tail=（Tail+1）%数组长度

出队时队头指针算法和队尾一样