using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DataStructrue
{
    /// <summary>
    /// 循環數組
    /// （1）添加功能
    /// （2）刪除功能
    /// （3）查詢（任何、首尾處）功能
    /// （4）修改（任何，首位處）功能
    /// </summary>
    /// <typeparam name="E"></typeparam>
    class Array2<E>
    {
        private E[] data;
        private int N;
        private int first;
        private int last;
        public Array2(int capacity)
        {
            data = new E[capacity];
            N = 0;
            first = 0;
            last = 0;
        }
        public Array2() : this(10) { }
        public int Count { get { return N; } }
        public bool IsEmpty { get { return N==0; } }
        public E GetFirst()
            return data[first];
        /// <summary>
        /// 添加一個元素
        /// </summary>
        /// <param name="e"></param>
        public void Add(E e)
            if (N==data.Length)
            {
                ResetCapacity(data.Length*2);
            }
            data[last] = e;
            last = (last + 1) % data.Length;
            N++;
        /// 移除早放進的一個元素
        /// <returns></returns>
        public E RemoveLast()
            if (N==0)
                throw new ArgumentException("隊列已空");
            if (N<=(data.Length/4))
                ResetCapacity(data.Length / 2);
            E de = data[first];
            data[first] = default;
            first = (first + 1) % data.Length;
            N--;
            return de;
        /// 移除特定下標元素
        /// 消耗大，不建議使用
        /// <param name="index"></param>
        public E RemoveAt(int index)
            if (index > data.Length || index < 0 ||N==0)
                throw new ArgumentException("非法索引");
            if (first > last)
                if (index < first && index >= last)
                {
                    throw new ArgumentException("非法索引");
                }
            else if (last > first)
            E rd = data[index];
            for (int i = index+1; i !=last ; i=(i+1)%data.Length)
                data[i-1] = data[i];
            last--;
            return rd;
        /// 移除特定元素
        public E Remove(E e)
            for (int i = first; i !=last; i=(i+1)%data.Length)
                if (data[i].Equals(e))
                    return RemoveAt(i);
            return data[last];
        /// 對數組進行擴容操作
        /// <param name="newcapacity"></param>
        private void ResetCapacity(int newcapacity)
            E[] data2 = new E[newcapacity];
            for (int i = 0; i < N; i++)
                data2[i] = data[first];
                first = (first + 1) % data.Length;
                last = i+1;
            data = data2;
        public override string ToString()
            //實例化
            StringBuilder res = new();
            //重寫格式1：輸出數組元素個數以及長度
            //res.Append(string.Format("Array1:   count={0}    capacity={1}\n",N,data.Length));
            res.Append(string.Format("A2Queue: Count = {0} Capacity = {1}\n[", N, data.Length));
                res.Append(data[(first+i)%data.Length]);
                if (i!=N-1)
                    res.Append(',');
            res.Append(']'+"\n");
            //返回
            return res.ToString();
    }
}

using System;

namespace DataStructure
{
    /// <summary>
    /// 用數組實現隊列
    /// 用2個index標記開始合結束
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class ArrayQueue<T>
    {
        private int mCapicity;
        private int mStartIndex;
        private int mEndIndex;
        private int mCount;
        private T[] mArray;
        public ArrayQueue(int capicity)
        {
            mCapicity = capicity;
            mArray = new T[capicity];
        }
        public int Count
            get
            {
                return mCount;
            }
        public bool IsFull
                return mCount == mCapicity;
        public int Capicity
            get { return mCapicity; }
        public bool IsEmpty
                return mCount == 0;
        public void Clear()
            mStartIndex = 0;
            mEndIndex = 0;
            mCount = 0;
            mCapicity = 0;
            mArray = null;
        public void Enqueue(T e)
            //隊列滿了
            if (IsFull)
                throw new Exception("queue is full");
            mArray[mEndIndex] = e;
            mCount++;
            //計算下一個位置
            mEndIndex++;
            if (mEndIndex == mCapicity)
                mEndIndex = 0;
        public T Dequeue()
            //隊列空
            if (IsEmpty)
                throw new Exception("queue is empty");
            var r = mArray[mStartIndex];
            //計算下一次取元素的index
            //取出元素后增加start
            mStartIndex++;
            //到達尾部，開始循環，下一次從頭開始取
            if (mStartIndex == mCapicity)
                mStartIndex = 0;
            mCount--;
            return r;
    }
}

namespace DataStructure
{
    public class ArrayQueueTest : BaseSolution
    {
        public void Test()
        {
            var queue = new ArrayQueue<int>(4);
            queue.Enqueue(1);
            queue.Enqueue(2);
            queue.Enqueue(3);
            queue.Enqueue(4);
            // println(queue.Capicity);
            // println(queue.Count);

            println(queue.Dequeue());
            queue.Enqueue(5);
            while (!queue.IsEmpty)
            {
                println(queue.Dequeue());
            }
        }
    }
}