栈的应用

栈（Stack）：是一种后进先出的数据结构 只能一端进行添加（入栈）或删除（出栈）操作，这一端称为栈顶。

栈的相关操作

Stack void Push(e) //往栈中添加元素 E Pop() //将栈顶的元素取出删除 E Peek() //查询栈顶的元素 int Count //栈中的元素有多少 Bool IsEmpty //栈是否为空

Array1底层代码：

 //第一版常规数组类  
class Array1<E
    {
        private E[] data;   //存储元素的数组
        private int N;      //数组中的元素个数
        //通过指定容量开辟数组空间
        public Array1(int capacity)
        {
            data = new E[capacity];
            N = 0;
        }
        //默认数组容量为10
        public Array1() : this(10) { }
        //获取数组容量的属性
        public int Capacity
        {
            get { return data.Length; }
        }
        //获取数组元素个数的属性
        public int Count
        {
            get { return N; }
        }
        //判断数组是否为空的属性
        public bool IsEmpty
        {
            get { return N == 0; }
        }
        //在数组指定位置添加元素e
        public void Add(int index, E e)
        {
            if (index < 0 || index > N)
                throw new ArgumentException("数组索引越界");
            if (N == data.Length)
                ResetCapacity(2 * data.Length);
            for (int i = N - 1; i >= index; i--)
                data[i + 1] = data[i];
            data[index] = e;
            N++;
        }
        //在数组尾部添加元素e
        public void AddLast(E e)
        {
            Add(N, e);
        }
        //在数组头部添加元素e
        public void AddFirst(E e)
        {
            Add(0, e);
        }
        //获取指定位置的元素e
        public E Get(int index)
        {
            if (index < 0 || index >= N)
                throw new ArgumentException("数组索引越界");
            return data[index];
        }
        //获取数组头部的元素e
        public E GetFirst()
        {
            return Get(0);
        }
        //获取数组尾部的元素e
        public E GetLast()
        {
            return Get(N - 1);
        }
        //修改数组中的值
        public void Set(int index, E newE)
        {
            if (index < 0 || index >= N)
                throw new ArgumentException("数组索引越界");
            data[index] = newE;
        }
        //查询数组是否包含元素e
        public bool Contains(int e)
        {
            for (int i = 0; i < N; i++)
            {
                if (data[i].Equals(e))
                    return true;
            }
            return false;
        }
        //查询数组中元素e的位置索引
        public int IndexOf(int e)
        {
            for (int i = 0; i < N; i++)
            {
                if (data[i].Equals(e))
                    return i;
            }
            return -1;
        }
        //删除指定位置的元素并返回该元素
        public E RemoveAt(int index)
        {
            if (index < 0 || index >= N)
                throw new ArgumentException("索引超出了数组界限");
            E del = data[index];
            for (int i = index + 1; i <= N - 1; i++)
                data[i - 1] = data[i];
            N--;
            data[N] = default(E);
            if (N == data.Length / 4)
                ResetCapacity(data.Length / 2);
            return del;
        }
        //删除数组头部位置的元素并返回该元素
        public E RemoveFirst()
        {
            return RemoveAt(0);
        }
        //删除数组尾部位置的元素并返回该元素
        public E RemoveLast()
        {
            return RemoveAt(N - 1);
        }
        //删除指定的元素e
        public void Remove(int e)
        {
            int index = IndexOf(e);
            if (index != -1)
                RemoveAt(index);
        }
        //调整数组容量的大小
        private void ResetCapacity(int newCapacity)
        {
            E[] newData = new E[newCapacity];
            for (int i = 0; i < N; i++)
                newData[i] = data[i];
            data = newData;
        }
        //输出链表类的信息
        public override string ToString()
        {
            StringBuilder res = new StringBuilder();
            //res.Append(string.Format("Array1:  count={0}  capacity={1}\n", N, data.Length));
            res.Append("[");
            for (int i = 0; i < N; i++)
            {
                res.Append(data[i]);
                if (i != N - 1)
                    res.Append(", ");
            }
            res.Append("]");
            return res.ToString();
        }
    }

在数组栈中添加元素，删除栈顶的元素，其例子

要点：我们应该将栈的尾部还是头部作为栈顶？ 从时间复杂度来看： （1）如果将头部作为栈顶，需要两步，将头部删除后，再把后面的元素的向前移（第一个不在了，那就将第二设为第一，第三设为第二，以此类推） 0（N） （2）如果将尾部作为栈顶，只需一步，删除尾部，其他的元素的位置不用进行改变 0（1） IStack——>**接口 Array1 ——>底层代码（数组）**

 class ArrayIstack<E>:IStack<E>
    {
        private Array1<E>  arr;

        public ArrayIstack(int capacity)
        {
            arr = new Array1<E>(capacity);
        }

        public ArrayIstack()
        {
            arr = new Array1<E>();
        }

        /// <summary>
        /// 返回栈中的元素有多少
        /// </summary>
        public int Count { get { return arr.Count; } }

        /// <summary>
        /// 栈是否为空
        /// </summary>
        public bool IsEmpty { get { return arr.IsEmpty; } }

        /// <summary>
        /// 查询栈顶的元素
        /// </summary>
        /// <returns></returns>
        public E Peek()
        {
            return arr.GetLast();
        }

        /// <summary>
        /// 将栈顶的元素取出删除
        /// </summary>
        /// <returns></returns>
        public E Pop()
        {
            return arr.RemoveLast();
        }

        /// <summary>
        /// 往栈中添加元素 
        /// </summary>
        /// <param name="e"></param>
        public void Push(E e)
        {
            arr.AddLast(e);
        }

        public override string ToString()
        {
            return "Stack" + arr.ToString() + "Top";
        }
    }

class Program
    {
        private static void Main(string[] args)
        {
            ArrayIstack<int> stack = new ArrayIstack<int>();
            for (int i = 0; i < 5; i++)
            {
                stack.Push(i);
                Console.WriteLine(stack);
            }

            stack.Pop();
            Console.WriteLine(stack);

            Console.ReadKey();
        }
    }

运行结果：

在链表栈中添加元素，删除栈顶的元素，其例子

要点：我们应该将栈的尾部还是头部作为栈顶？ 从时间复杂度来看： （1）如果将头部作为栈顶，需要一步，将头部的下一个结点作为头部即可（head = head.next;）。0（1） （2）如果将尾部作为栈顶，需要遍历整条链表，然后将 Null 作为新的尾部（last = last.next;）,之后链表的长度自减即可。 0（N） IStack——>接口

class LinkListStack<E>:IStack<E>
    {
        private LinkedList1<E> list;

        /// <summary>
        /// 因为链表本身就是完整的动态数组
        /// 所以不需要传入容量值
        /// 同时它也没有容量这个概念
        /// </summary>
        public LinkListStack()
        {
            list = new LinkedList1<E>();
        }

        /// <summary>
        /// 返回栈中的元素有多少
        /// </summary>
        public int Count { get { return list.Count; } }

        /// <summary>
        /// 栈是否为空
        /// </summary>
        public bool IsEmpty { get { return list.IsEmpty; } }

        public E Peek()
        {
            return list.GetFirst();
        }

        public E Pop()
        {
            return list.RemoveFirst();
        }

        public void Push(E e)
        {
            list.AddFrist(e);
        }

        public override string ToString()
        {
            return "Stack" + list.ToString()+"Top";
        }
    }

 class Program
    {

        private static void Main(string[] args)
        {
            LinkListStack<int> stack = new LinkListStack<int>();
            for (int i = 0; i < 5; i++)
            {
                stack.Push(i);
                Console.WriteLine(stack);
            }

            stack.Pop();
            Console.WriteLine(stack);
        }
 }

运行结果：

数组栈、链表栈性能对比例子

TestStack方法： 对栈执行N次入栈和出栈操作 对于TestStack方法，不管是测试数组栈还是链表栈它们的时间复杂度都是O（n） 运行时间和数据规模成正比的关系 在Main方法中： 测试不同底层实现的栈性能 ArrayStack和linkedListStack耗时消耗巨大 由于链表的实现需要不断的new空间，所以内存操作耗时较大。 而对于数组操作，是对连续空间进行操作的，C#底层对连续空间的访问有非常好的优化。 再加上数据规模增大以后，动态数组resize调用的频次其实很小，所以得到这个测试结果是正常的：）

 class Program
    {
        public static long TestStack(IStack<int> stack, int N)
        {
            Stopwatch t = new Stopwatch();
            t.Start();

            for (int i = 0; i < N; i++)
                stack.Push(i);
            for (int i = 0; i < N; i++)
                stack.Pop();
            t.Stop();
            return t.ElapsedMilliseconds;
        }

          private static void Main(string[] args)
        {

            int n = 10000000;

            //ArrayIstack'time：1842ms
            ArrayIstack<int> arrayIstack = new ArrayIstack<int>(n);
            long t1 = TestStack(arrayIstack, n);
            Console.WriteLine("ArrayIstack'time：" + t1 + "ms");

            LinkListStack<int> linkListStack = new LinkListStack<int>();
            long t2 = TestStack(linkListStack, n);
            Console.WriteLine("linkListStack'time：" + t2 + "ms");

            //C#提供的栈是基于数组实现的。
            Stack<int> stack = new Stack<int>(n);
            Stopwatch t = new Stopwatch();
            t.Start();
            for (int i = 0; i < n; i++)
                stack.Push(i);
            for (int i = 0; i < n; i++)
                stack.Pop();
            t.Stop();
            Console.WriteLine("Stack'time: " + t.ElapsedMilliseconds + "ms");

            Console.ReadKey();
          }
}

运行结果：

链表LinkedList1的底层代码：

重点：在链表中，只能通过 一 找到 二 ，没办法从 二 找到 一。

 class LinkedList1<E>
    {
        private class Node
        {
            public E e;
            public Node next;

            /// <summary>
            /// 指向下一个节点的方法
            /// </summary>
            /// <param name="e"></param>
            /// <param name="next"></param>
            public Node(E e, Node next)
            {
                this.e = e;
                this.next = next;
            }

            /// <summary>
            /// 头部的节点
            /// </summary>
            /// <param name="e"></param>
            public Node(E e)
            {
                this.e = e;
                this.next = null;
            }

            public override string ToString()
            {
                return e.ToString();
            }
        }

        private Node head;
        private int N;

        public  LinkedList1() {
            head = null;
            N = 0;
        }

        public int Count
        {
            get { return N; }
        }

        public bool IsEmpty
        {
            get { return N == 0; }
        }

        public void Add(int index,E e)
        {
            if (index < 0 || index > N)
                throw new ArgumentException("非法索引");
            if (index == 0)
            {
                //如果index 等于零，那就说明我们将进行头部节点的添加
                //原来的头部节点就是新节点的引用指向
                //新节点就是新的头部结点
                //Node node = new Node(e);
                //node.next = head;
                //head = node;

                head = new Node(e, head);
            }
            else
            {
                Node pro = head;
                for (int i = 0; i < index - 1; i++)
                    pro = pro.next;
                //.next 意思是：结点的引用指向

                //将 for循环遍历后的头部结点指向的引用 变为 新节点的引用指向
                //Node node = new Node(e); //新的结点
                //node.next = pro.next;  //新结点就是 头部节点的引用指向
                //pro.next = node;

                pro.next = new Node(e, pro.next);
            }
            N++;
        }

        public void AddFrist(E e)
        {
            Add(0, e);
        }

        public void AddLast(E e)
        {
            Add(N, e);
        }

        public E Get(int index)
        {
            if (index < 0 || index > N)
                throw new ArgumentException("非法索引");

            Node cur = head;
            for (int i = 0; i < index; i++)
                cur = cur.next;

            return cur.e;
        }

        public E GetFirst()
        {
            return Get(0);
        }

        public E GetLast()
        {
            return Get(N - 1);
        }

        public void Set(int index, E newE)
        {
            if (index < 0 || index > N)
                throw new ArgumentException("非法索引");

            Node cur = head;
            for (int i = 0; i < index; i++)
                cur = cur.next;

            cur.e = newE;
        }

        public bool Containa(E e)
        {
            Node cur = head;
            while (cur != null)
            {
                if (cur.e.Equals(e))
                    return true;

                cur = cur.next;
            }
            return false;
        }

        public E RemoveAt(int index)
        {
            if (index < 0 || index > N)
                throw new ArgumentException("非法索引");

            if (index == 0)
            {
                Node DelCur = head;
                head = head.next;

                N--;
                return DelCur.e;
            }
            else
            {
                Node pre = head;
                for (int i = 0; i < index - 1; i++)
                    pre = pre.next;

                Node delcur = pre.next;
                pre.next = delcur.next;

                N--;
                return delcur.e;
            }
        }

        public E RemoveFirst()
        {
            return RemoveAt(0);
        }

        public E RemoveLast()
        {
            return RemoveAt(N - 1);
        }

        //两个指针，cur指向头部，pre指向null。
        //cur在前，pre在后。
        //当cur变成cur.next,那pre就是原来的cur
        public void Remove(E e)
        {
            if (head == null)
                return;

            if (head.e.Equals(e))
            {
                head = head.next;
                N--;
            }
            else
            {
                Node cur = head;
                Node pre = null;
                while (cur != null)
                {
                    if (cur.e.Equals(e))
                        break;

                    pre = cur;
                    cur = cur.next;
                }
                if (cur != null)
                {
                    pre.next = pre.next.next;
                    N--;
                }
            }
        }

        public override string ToString()
        {
            StringBuilder res = new StringBuilder();
            Node cur = head;
            while (cur!=null)
            {
                res.Append(cur + "->");
                cur = cur.next;
            }
            res.Append("null");
            return res.ToString();
        }
    }

链表Linked List2的底层代码

与第一代的区别在于，第二代具有尾指针 头：head（默认） 尾：tail 假设我要在尾部添加链表结点元素。 第一代必须通过cur = cur.next，遍历到尾部的前一个然后进行添加，但这样时间复杂度为O（N） 但第二代只需要，tail.next = NewCur , tail= NewCur ，时间复杂度为O（1） 两者在尾部添加数据有差别外，其余的在时间复杂度上没什么区别

 //第二版本的链表，具备头尾指针
    class LinkedList2<E>
    {
        private class Node
        {
            /// <summary>
            /// 结点中存储的元素
            /// </summary>
            public E e;
            /// <summary>
            /// 存储下一个结点的引用
            /// </summary>
            public Node next;

            /// <summary>
            /// 通过元素和下一个结点的引用创建结点
            /// </summary>
            public Node(E e, Node next)
            {
                this.e = e;
                this.next = next;
            }

            /// <summary>
            ///通过元素创建结点
            /// </summary>
            public Node(E e)
            {
                this.e = e;
                this.next = null;
            }

            /// <summary>
            /// 输出结点的信息
            /// </summary>
            public override string ToString()
            {
                return e.ToString();
            }
        }


        private Node head;//头指针标识链表的头部

        private Node tail;   //尾指针标记链表尾部结点
        private int N;

        //初始化链表一个结点也没有，head指向空，尾部指针指向空，N为0
        public LinkedList2()
        {
            head = null;
            tail = null;
            N = 0;
        }

        public int Count { get { return N; }}

        public bool IsEmpty { get { return N == 0; } }

        /// <summary>
        /// 往链表尾部添加元素
        /// </summary>
        /// <param name="e"></param>
        public void AddLast(E e)
        {

            Node node = new Node(e);
            if (IsEmpty)
            {
                head = node;
                tail = node;
            }
            else
            {
                tail.next = node;
                tail = node;
            }

            N++;
        }

        /// <summary>
        /// 删除链表头部结点
        /// </summary>
        /// <returns></returns>
        public E RemoveFirst()
        {
        if (IsEmpty)
                throw new InvalidOperationException("链表为空");

            E e = head.e;

            head = head.next;

            if (head == null)
                tail = null;

            N--;

            return e;
        }

        /// <summary>
        /// 获取链表头部结点
        /// </summary>
        /// <returns></returns>
        public E GetFirst()
        {
            if (IsEmpty)
            {
                throw new InvalidOperationException("链表为空");
            }
            return head.e;
        }

        public override string ToString()
        {
            StringBuilder res = new StringBuilder();
            Node cur = head;
            while (cur != null)
            {
                res.Append(cur + "->");
                cur = cur.next;
            }
            res.Append("null");
            return res.ToString();
        }
    }

链表LinkedList3的底层代码

不同于第一二代的泛型存储数据，它的存储方式是 字典（Dictionary） 并且有两个变量，Key、Value。同时key、Value是指向关系（Key➡Value），通过Key可以找到对应Value 但是这里 Key 代表存储进来的值，Value 代表该值出现的频率 之所以需要第三代，因为我们想要判断记事本中有多少 Key 以及它出现的频率 value

 /// <summary>
    /// 第三版的链表类，只具备头指针，存储键值对的数据
    /// </summary>
    /// <typeparam name="Key">代表存储进来的值</typeparam>
    /// <typeparam name="Value">代表存储进来的值，它的频率</typeparam>
    class LinkedList3<Key,Value>
    { 
        //私有的内部结点类
        //这个类相比较以前的LinkedList1的结点类多存储了一个value变量而已
        private class Node
        {
            public Key key;
            public Value value;
            public Node next;

            public Node(Key key, Value value,Node next)
            {
                this.key = key;
                this.value = value;
                this.next = next;
            }

            public override string ToString()
            {
                return key.ToString() + "    :   " + value.ToString();
            }
        }

        private Node head;
        private int N;

        public LinkedList3()
        {
            head = null;
            N = 0;
        }

        public int Count { get { return N; } }

        public bool IsEmpty { get { return N == 0; } }

        /// <summary>
        /// 私有的辅助函数，通过键查找对应的结点！
        ///  有了它作为前提，能更方便的实现增删改查相应的功能
        /// </summary>
        private Node GetNode(Key key)
        {
            Node cur = head;
            while (cur != null)
            {
                if (cur.key.Equals(key))
                    return cur;

                cur = cur.next;
            }
            return null;
        }

        /// <summary>
        /// 往链表添加键值对数据
        /// </summary>
        public void Add(Key key, Value value)
        {
            Node node = GetNode(key);

            //如果结点不存在，则创建新节点
            if (node == null)
            {
                head = new Node(key, value, head);
                N++;
            }
            else //存在的话，就更新一下键对应的值
                node.value = value;
        }

        /// <summary>
        /// 查看链表中是否包含指定键
        /// </summary>
        public bool Contains(Key key)
        {
            return GetNode(key) != null;
        }

        /// <summary>
        /// 通过键获取对应的值
        /// </summary>
        public Value Get(Key key)
        {
            Node node = GetNode(key);

            if (node == null)
                throw new ArgumentException("键" + key + "不存在");
            else
                return node.value;
        }

        /// <summary>
        /// 将键对应的值改成一个新的值
        /// </summary>
        public void Set(Key key,Value NewValue)
        {
            Node node = GetNode(key);
            if (node == null)
                throw new ArgumentException("键" + key + "不存在");
            else
                node.value = NewValue;
        }

        /// <summary>
        /// 通过键删除结点中存储的储键值对数据
        /// </summary>
        public void Remove(Key key)
        {
            if (head == null)
                return;

            if (head.key.Equals(key))
            {
                head = head.next;
                N--;
            }
            else
            {
                Node cur = head;
                Node pre = null;
                while (cur != null)
                {
                    if (cur.key.Equals(key))
                        break;

                    pre = cur;
                    cur = cur.next;
                }
                if (cur != null)
                {
                    pre.next = pre.next.next;
                    N--;
                }
            }
        }

    }

队列的应用

队列（Queue）：是一种先进先出的数据结构 只允许在队头删除元素（出队），在队尾添加元素（入队）

在队列中进行添加、删除元素的例子

与数组栈的区别： （1）数组栈可以在头部（时间复杂度O（1））或尾部进行删除元素（时间复杂度O（N）） （2）但队列只能队头进行删除（时间复杂度为O（N））

class Array1Queue<T>:IQueue<T>
    {
        private Array1<T> arr;

        public int Count { get{ return arr.Count; } }

        public bool IsEmpty { get{ return arr.IsEmpty; } }


        public Array1Queue(int capacity)
        {
            arr = new Array1<T>(capacity);
        }

        public Array1Queue()
        {
            arr = new Array1<T>();
        }

        /// <summary>
        /// 往队列添加元素
        /// </summary>
        public void Enqueue(T t)
        {
            arr.AddLast(t);
        }

        /// <summary>
        /// 删除队列的元素
        /// </summary>
        public T Dequeue()
        {
            return arr.RemoveFirst();
        }

        /// <summary>
        ///查看队列元素
        /// </summary>
        public T Peek()
        {
            return arr.GetFirst();
        }

        public override string ToString()
        {
            return "Queue：front  " + arr.ToString() + "tall";
        }
    }

class Program
    {
        private static void Main(string[] args)
        {

            Array1Queue<int> array1Queue = new Array1Queue<int>();
            for (int i = 0; i < 5; i++)
            {
                array1Queue.Enqueue(i);
                Console.WriteLine(array1Queue);
            }

            array1Queue.Dequeue();
            Console.WriteLine(array1Queue);

            Console.ReadKey();
        }
}

运行结果：

循环队列

因为队列出队是O（N）操作，那为了避免这种情况，循环队列出现了

**

循环队列的数组，其底层代码：

代码逻辑：假设一个容量（N）为五的数组（data），会有两个索引变量《first》、《last》。 刚初始化时，这两个变量都为零，当我添加元素时，first不变，last++， 如果我想删除元素，我只需要通过数组索引进行删除，然后first++，就行。 假设，目前数组元素是《null》《null》《2》《3》《null》，此时 first 是 data[2], last 是 data[4]，当我再次添加元素，last 就会回到 data[0] 如果数组满了，也就是（N == data.length），那旧数组 * 2，然后赋值给新数组 这里有个问题：假设数组元素《7》《8》《3》《4》《5》，赋值到新数组，就应该是《3》《4》《5》《6》《7》《null》《null》《null》《null》《null》 这里 first 的索引指向 data[0]，last 索引指向 data[N]（这里的 N ：旧数组的容量） 这里的代码：for(int i = 0; i<n;i++) newdata[i] = data[first + i] % data.length;

 class Array2<E>
    {
        private E[] data;
        private int first;
        private int last;
        private int N;


        public Array2(int capacity)
        {
            data = new E[capacity];

            first = 0;
            last = 0;
            N = 0;
        }

        public Array2() : this(10) { }


        public int Count { get { return N; } }

        public bool IsEmpty { get { return N == 0; } }

        public void AddLast(E e)
        {
            if (N == data.Length)
            {
                ResetCapacity(data.Length * 2);
            }

            data[last] = e;
            last = (last + 1) % data.Length;
            N++;
        }

        public E RemoveFirst()
        {
            if (IsEmpty)
                throw new InvalidOperationException("数组为空");

            if (N == data.Length / 4)
                ResetCapacity(data.Length / 2);


            E ret = data[first];
            data[first] = default(E);

            first = (first + 1) % data.Length;
            N--;

            return ret;
        }

        public E GetFirst()
        {
            if (IsEmpty)
                throw new InvalidOperationException("数组为空");

            return data[first];
        }

        private void ResetCapacity(int newCapacity)
        {
            E[] newdata = new E[newCapacity];

            for (int i = 0; i < N; i++)
                newdata[i] = data[(first + i) % data.Length];

            data = newdata;
            first = 0;
            last = N;
        }

        public override string ToString()
        {
            StringBuilder res = new StringBuilder();
            res.Append("[");
            for (int i = 0; i < N; i++)
            {
                res.Append(data[(first + i) % data.Length]);
                if ((first + i + 1) % data.Length != last)
                    res.Append("，");
            }
            res.Append("]");

            return res.ToString();
        }
    }

循环队列的例子：

循环队列的好处：原来数组队列的出队的时间复杂度是O(N),而循环数组队列，其出队的时间复杂度为O(1)。

 class Array2Queue<E>:IQueue<E>
    {
        private Array2<E> arr;

        public int Count { get { return arr.Count; } }

        public bool IsEmpty { get { return arr.IsEmpty; } }


        public Array2Queue(int capacity)
        {
            arr = new Array2<E>(capacity);
        }

        public Array2Queue()
        {
            arr = new Array2<E>();
        }

        /// <summary>
        /// 往队列添加元素
        /// </summary>
        public void Enqueue(E E)
        {
            arr.AddLast(E);
        }

        /// <summary>
        /// 删除队列的元素
        /// </summary>
        public E Dequeue()
        {
            return arr.RemoveFirst();
        }

        /// <summary>
        ///查看队列元素
        /// </summary>
        public E Peek()
        {
            return arr.GetFirst();
        }

        public override string ToString()
        {
            return "Queue：front  " + arr.ToString() + "tall";
        }
    }

 class Program
    {
        private static void Main(string[] args)
        {
            #region 往数组队列添加、删除元素
            Array2Queue<int> array2Queue = new Array2Queue<int>();
            for (int i = 0; i < 5; i++)
            {
                array2Queue.Enqueue(i);
                Console.WriteLine(array2Queue);
            }

            array2Queue.Dequeue();
            Console.WriteLine(array2Queue);
            #endregion

            Console.ReadKey();

        }
    }

运行结果：

数组队列与循环数组队列的性能对比：

他们之间的区别就是前者出队时间复杂度O（N），后者则为O（1），当数据达到几十万时，他们之间差距就会非常庞大！

class Program
    {
        public static long TestIQueue(IQueue<int> queue, int N)
        {
            Stopwatch t = new Stopwatch();
            t.Start();

            for (int i = 0; i < N; i++)
                queue.Enqueue(i);
            for (int i = 0; i < N; i++)
                queue.Dequeue();
            t.Stop();
            return t.ElapsedMilliseconds;
        }

        private static void Main(string[] args)
        {
            int n = 100000;

            Array1Queue<int> array1Queue = new Array1Queue<int>();
            long t1 = TestIQueue(array1Queue, n);
            Console.WriteLine("Array1Queue'Time'" + t1 + "ms");

            Array2Queue<int> array2Queue = new Array2Queue<int>();
            long t2 = TestIQueue(array2Queue, n);
            Console.WriteLine("Array2Queue'Time'" + t2 + "ms");



            Console.ReadKey();

        }
    }

运行结果：