【数据结构】循环队列

MaybeHC

发布于 2024-04-23 19:04:50

670

发布于 2024-04-23 19:04:50

上次实现了数组队列，这次来实现循环队列循环队列的几个要点，front指向队头元素，tail指向队尾元素的下一个位置，front=tail时队列为空，（front+1）% data.Length = tail时队列为满，还是会使用第一节所编写的数组类做最底层。

实现

 class LoopQueue<E> : Queue<E>
    {
        private E[] data;
        private int front, tail;
        private int size;
        public LoopQueue(int capacity)
        {
            data = new E[capacity + 1];
            front = 0;
            tail = 0;
            size = 0;
        }
        public LoopQueue():this(10)
        {
            
        }
        public int getCapacity()
        {
            return data.Length - 1;
        }
        public E dequeue()
        {
            if (isEmpty())
                throw new ArgumentException("Cannot dequeue from an empty queue");
            E ret = data[front];
            data[front] = default(E);
            front = (front + 1) % data.Length;
            size--;
            if (size == getCapacity() / 4 && getCapacity() / 2 != 0)
                resize(getCapacity() / 2);
            return ret;

        }

        public void enqueue(E e)
        {
            if ((tail + 1) % data.Length == front)
                resize(getCapacity() * 2);
            data[tail] = e;
            tail = (tail + 1) % data.Length;
            size++;
        }
        private void resize(int newCapacity)
        {
            E[] newData = new E[newCapacity + 1];
            for(int i = 0; i < size; i++)
            {
                newData[i] = data[(i + front) % data.Length];
            }
            data = newData;
            front = 0;
            tail = size;
        }
        public E getFront()
        {
            if (isEmpty())
                throw new ArgumentException("Queue is empty");
            return data[front];
            
        }

        public int getSize()
        {
            return size;
        }

        public bool isEmpty()
        {
            return front == tail;
        }
        public override string ToString()
        {
            StringBuilder sb = new StringBuilder();
            sb.Append($"Queue: size ={size},capacity ={getCapacity()}");
            sb.Append("front [");
            for (int i = front; i !=tail; i=(i+1)%data.Length)
            {
                sb.Append(data[i]);
                if ((i+1)% data.Length!=tail)
                    sb.Append(", ");
            }
            sb.Append("] tail");
            return sb.ToString();
        }
    }

测试

static void Main(string[] args)
        {
            LoopQueue<int> queue = new DataStructure.LoopQueue<int>();
            for (int i = 0; i < 10; i++)
            {
                queue.enqueue(i);
                Console.WriteLine(queue);
                if (i % 3 == 2)
                {
                    queue.dequeue();
                    Console.WriteLine(queue);
                }
            }
            Solution su = new Solution();
            Console.ReadKey();
        }