队列(Queue)

数组实现队列

队列相关操作

void Enqueue(T t);//入队

T Dequeue();//出队

T Peek();//查看队首元素

int Count { get; }//查看元素个数

bool IsEmpty { get; }//查看队列是否为空

创建接口

创建接口IQueue

namespace AlgorithmTest10_队列Queue
{
    interface IQueue<T>
    {
        void Enqueue(T t);//入队
        T Dequeue();//出队
        T Peek();//查看队首元素
        int Count { get; }//查看元素个数
        bool IsEmpty { get; }//查看队列是否为空
    }
}

实现接口功能

新建**Array1Queue类,实现IQueue**接口功能

using AlgorithmTest06_List;

namespace AlgorithmTest10_队列Queue
{
    class Array1Queue<T> : IQueue<T>
    {
        private SeqList<T> arr;//引用06中的动态数组

        /// <summary>
        /// capacity:容量
        /// </summary>
        /// <param name="capacity"></param>
        public Array1Queue(int capacity)
        {
            arr = new SeqList<T>(capacity);//数组开辟空间
        }
        /// <summary>
        /// 默认容量:10
        /// </summary>
        public Array1Queue()
        {
            arr = new SeqList<T>();//数组开辟空间
        }
        /// <summary>
        /// 查询元素个数
        /// </summary>
        public int Count { get { return arr.GetCount(); } }
        /// <summary>
        /// 判空
        /// </summary>
        public bool IsEmpty { get { return arr.IsEmpty(); } }
        /// <summary>
        /// 出队
        /// </summary>
        /// <returns></returns>
        public T Dequeue()
        {
            return arr.Delete(0);
        }
        /// <summary>
        /// 入队
        /// </summary>
        /// <param name="t"></param>
        public void Enqueue(T t)
        {
            arr.AddLast(t);//末尾入队
        }
        /// <summary>
        /// 查询队首
        /// </summary>
        /// <returns></returns>
        public T Peek()
        {
            return arr.GetElem(0);
        }
        public override string ToString()
        {
            return "Queue: front " + arr.ToString();
        }
    }
}

效果展示

using System;
namespace AlgorithmTest10_队列Queue
{
    class Program
    {
        static void Main(string[] args)
        {
            Array1Queue<int> que = new Array1Queue<int>();
            Console.WriteLine("队列是否为空:" + que.IsEmpty);
            for (int i = 0; i < 5; i++)
            {
                que.Enqueue(i);
                Console.WriteLine(que);
            }

            Console.WriteLine("删除" + que.Dequeue());
            Console.WriteLine("队首" + que.Peek());
            Console.WriteLine("队列是否为空:" + que.IsEmpty);

            Console.ReadKey();
        }
    }
}

时间复杂度

可以看到按以上方法实现的出队时间复杂度为O(n)

所以我们需要循环队列优化复杂度

循环队列

新建类**Array2**实现循环数组

实现循环数组

using System;
using System.Text;

namespace AlgorithmTest10_队列Queue
{
    class Array2<T>
    {
        private T[] data;
        private int first;
        private int last;
        private int count;

        public Array2(int capacity)
        {
            data = new T[capacity];//数组预设空间
            first = 0;
            last = 0;
            count = 0;
        }
        public Array2() : this(10) { }

        /// <summary>
        /// 成员数量
        /// </summary>
        public int GetCount { get { return count; } }

        /// <summary>
        /// 判空,
        /// </summary>
        public bool IsEmpty { get { return count == 0; } }

        /// <summary>
        /// 数组末尾添加
        /// </summary>
        /// <param name="t"></param>
        public void AddLast(T t)
        {
            //如果元素数量与数组长度相等,则扩容
            if (count == data.Length)
            {
                RestCapacity(2 * data.Length);
            }

            data[last] = t;
            last = (last + 1) % data.Length;
            //如果last小于数组元素长度,则返回结果为last+1本身
            //如果last等于data.Length,则返回0
            count++;
        }
        /// <summary>
        /// 删除数组头部
        /// </summary>
        /// <returns></returns>
        public T RemoveFirst()
        {
            if (IsEmpty)
            {
                throw new InvalidOperationException("不能数组为空!");
            }

            T ret = data[first];//存储要删除的值用来返回显示
            data[first] = default(T);//设置为default ,c#会回收

            first = (first + 1) % data.Length;
            //如果first小于数组元素长度,则返回结果为first+1本身
            //如果first等于data.Length,则返回0
            count--;
            //如果元素个数为空间的四分之一,则缩容一半
            if (count == data.Length / 4)
            {
                RestCapacity(data.Length / 2);
            }
            return ret;
        }
        /// <summary>
        /// 查询数组头部内容
        /// </summary>
        /// <returns></returns>
        public T GetFirst()
        {
            if (IsEmpty)
            {
                throw new InvalidOperationException("不能数组为空!");
            }
            return data[first];
        }
        /// <summary>
        /// 扩容循环数组
        /// </summary>
        private void RestCapacity(int newCap)
        {
            T[] newData = new T[newCap];
            //旧数组赋值到新数组头部
            for (int i = 0; i < count; i++)
            {
                //newData[0]=data[first]
                newData[i] = data[(first + i) % data.Length];
            }
            data = newData;
            first = 0;
            last = count;
        }
        public override string ToString()
        {
            StringBuilder res = new StringBuilder();
            for (int i = 0; i < count - 1; i++)
            {
                res.Append(data[(first + i) % data.Length] + ",");
            }
            //最后一位单独打印,因为末尾不需要逗号
            res.Append(data[(first + count - 1) % data.Length]);
            return res.ToString();
        }
    }
}

循环数组扩容

新建一个newData[],容量更大,将旧data[]数组中的first下标移到newData[0]完成扩容。

private void RestCapacity(int newCap)
{
    T[] newData = new T[newCap];
    //旧数组赋值到新数组头部
    for (int i = 0; i < count; i++)
    {
        //newData[0]=data[first]
        newData[i] = data[(first + i) % data.Length];
    }
    data = newData;
    first = 0;
    last = count;
}

重写ToString()

public override string ToString()
{
    StringBuilder res = new StringBuilder();
    for (int i = 0; i < count - 1; i++)
    {
        res.Append(data[(first + i) % data.Length] + ",");
    }
    //最后一位单独打印,因为末尾不需要逗号
    res.Append(data[(first + count - 1) % data.Length]);
    return res.ToString();
}

实现接口功能

创建Array2Queue

namespace AlgorithmTest10_队列Queue
{
    class Array2Queue<T> : IQueue<T>
    {
        private Array2<T> arr;

        /// <summary>
        /// capacity:容量
        /// </summary>
        /// <param name="capacity"></param>
        public Array2Queue(int capacity)
        {
            arr = new Array2<T>(capacity);//数组开辟空间
        }
        /// <summary>
        /// 默认容量:10
        /// </summary>
        public Array2Queue()
        {
            arr = new Array2<T>();//数组开辟空间
        }
        /// <summary>
        /// 查询元素个数
        /// </summary>
        public int Count { get { return arr.GetCount; } }
        /// <summary>
        /// 判空
        /// </summary>
        public bool IsEmpty { get { return arr.IsEmpty; } }
        /// <summary>
        /// 出队
        /// </summary>
        /// <returns></returns>
        public T Dequeue()
        {
            return arr.RemoveFirst();
        }
        /// <summary>
        /// 入队
        /// </summary>
        /// <param name="t"></param>
        public void Enqueue(T t)
        {
            arr.AddLast(t);//末尾入队
        }
        /// <summary>
        /// 查询队首
        /// </summary>
        /// <returns></returns>
        public T Peek()
        {
            return arr.GetFirst();
        }
        public override string ToString()
        {
            return "Queue: front " + arr.ToString();
        }
    }
}

效果展示

using System;
namespace AlgorithmTest10_队列Queue
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("=====使用循环数组=====");
            Array2Queue<int> que2 = new Array2Queue<int>();
            Console.WriteLine("队列是否为空:" + que2.IsEmpty);
            for (int i = 0; i < 5; i++)
            {
                que2.Enqueue(i);
                Console.WriteLine(que2);
            }
            Console.WriteLine("删除" + que2.Dequeue());
            Console.WriteLine("队首" + que2.Peek());
            Console.WriteLine("队列是否为空:" + que2.IsEmpty);
            Console.ReadKey();
        }
    }
}

数组队列、循环队列性能对比

Program.cs中创建方法TextQueue,并运行测试diamagnetic

        public static long TextQueue(IQueue<int> que, int N)
        {
            Stopwatch t = new Stopwatch();
            t.Start();
            for (int i = 0; i < N; i++)
            {
                que.Enqueue(i);
            }
            for (int i = 0; i < N; i++)
            {
                que.Dequeue();
            }
            t.Stop();
            return t.ElapsedMilliseconds;
        }
        static void Main(string[] args)
        {
#region 数组队列和循环队列性能对比
            Console.WriteLine("=====数组队列和循环队列性能对比=====");
            int N = 50000;
            //O(n^2)复杂度
            Array1Queue<int> arr1 = new Array1Queue<int>();
            long t1 = TextQueue(arr1, N);
            Console.WriteLine("array1queue'time:" + t1 + "ms");
            //O(n)复杂度
            Array2Queue<int> arr2 = new Array2Queue<int>();
            long t2 = TextQueue(arr2, N);
            Console.WriteLine("array2queue'time:" + t2 + "ms");
#endregion
            Console.ReadKey();
        }

测试结果

加上系统自带的Queue对比测试

Queue<int> que3 = new Queue<int>();
Stopwatch t = new Stopwatch();
t.Start();
for (int i = 0; i < N; i++)
{
    que3.Enqueue(i);
}
for (int i = 0; i < N; i++)
{
    que3.Dequeue();
}
t.Stop();
Console.WriteLine("Queue'time:" + t.ElapsedMilliseconds + "ms");

结论

O(n)和O(n^2)复杂度执行效率天差地别,样本越多相差会越大

链表实现队列

新建类LinkedList1Queue 继承接口 IQueue

实现单头链表队列

引用链表,实现接口功能LinkedList1Queue

using AlgorithmTest08_链表;

namespace AlgorithmTest10_队列Queue
{
    /// <summary>
    /// 链表队列
    /// </summary>
    /// <typeparam name="T"></typeparam>
    class LinkedList1Queue<T> : IQueue<T>
    {
        /// <summary>
        /// 引用链表
        /// </summary>
        private LinkedList1<T> list;

        public LinkedList1Queue()
        {
            list = new LinkedList1<T>();
        }

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

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

        public T Dequeue()
        {
            return list.RemoveFirst();
        }

        public void Enqueue(T t)
        {
            list.AddLast(t);
        }

        public T Peek()
        {
            return list.GetFirst();
        }
        public override string ToString()
        {

            return "Queue front " + list.ToString() + " tail";
        }
    }
}

复杂度分析

可以看出链表队列添加元素时复杂度O(n)过高,因为在尾部添加元素需要先遍历一遍元素。

优化链表队列

新加一个尾指针tail，单独用来实现尾部添加操作。

实现有头尾链表队列

新建链表

AlgorithmTest08_链表中新建**LinkedList2**类，只写队列相关操作

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

namespace AlgorithmTest08_链表
{
    class LinkedList2<T>
    {
        private class Node
        {
            public T t;
            public Node next;
            public Node(T t, Node next)
            {
                this.t = t;
                this.next = next;
            }
            public Node(T t)
            {
                this.t = t;
                this.next = null;
            }
            public override string ToString()
            {
                return t.ToString();
            }
        }

        /// <summary>
        /// 链表头
        /// </summary>
        private Node head;
        /// <summary>
        /// 链表尾
        /// </summary>
        private Node tail;

        /// <summary>
        /// 链表中存储了多少元素
        /// </summary>
        private int N;

        public LinkedList2()
        {
            head = null;
            tail = null;
            N = 0;
        }
        public int Count { get { return N; } }
        public bool IsEmpty { get { return N == 0; } }
        public void AddLast(T t)
        {
            Node node = new Node(t);
            if (IsEmpty)
            {
                head = node;
                tail = node;
            }
            else
            {
                //设置node在尾节点的右边
                tail.next = node;
                tail = node;
            }
            N++;
        }
        public T RemoveFirst()
        {
            if (IsEmpty)
            {
                throw new InvalidProgramException("链表为空");
            }
            T t = head.t;//存储要删除的数据
            head = head.next;//头部指向下一个节点(删除)
            N--;
            if (head == null)
            {//如果删除过后链表为空
                tail = null;//尾部设置也为空
            }
            return t;
        }
        public T GetFirst()
        {
            if (IsEmpty)
            {
                throw new InvalidProgramException("链表为空");
            }
            return head.t;
        }
        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();
        }
    }
}

引用链表,实现接口LinkedList2Queue

AlgorithmTest10_队列Queue中创建LinkedList2Queue实现接口IQueue(其实和LinkedList1Queue代码一样)

using AlgorithmTest08_链表;

namespace AlgorithmTest10_队列Queue
{
    class LinkedList2Queue<T> : IQueue<T>
    {
        /// <summary>
        /// 引用链表
        /// </summary>
        private LinkedList2<T> list;

        public LinkedList2Queue()
        {
            list = new LinkedList2<T>();
        }
        public int Count { get { return list.Count; } }

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

        public T Dequeue()
        {
            return list.RemoveFirst();
        }

        public void Enqueue(T t)
        {
            list.AddLast(t);
        }

        public T Peek()
        {
            return list.GetFirst();
        }
        public override string ToString()
        {
            return "Queue front " + list.ToString() + " tail";
        }
    }
}

单头链表队列和有尾的链表队列性能对比

#region 单头链表队列和有尾的链表队列性能对比
Console.WriteLine("=====单头链表队列和有尾的链表队列性能对比=====");

//O(n)复杂度
LinkedList1Queue<int> lk1 = new LinkedList1Queue<int>();
long tt1 = TextQueue(lk1, N);
Console.WriteLine("linkedlist1queue 'time " + tt1 + "ms");

//O(1)复杂度
LinkedList2Queue<int> lk2 = new LinkedList2Queue<int>();
long tt2 = TextQueue(lk2, N);
Console.WriteLine("linkedlist2queue 'time " + tt2 + "ms");

#endregion

数据结构-队列

队列(Queue)

数组实现队列

队列相关操作

创建接口

实现接口功能

效果展示

时间复杂度

循环队列

实现循环数组

循环数组扩容

重写ToString()

实现接口功能

效果展示

数组队列、循环队列性能对比

测试结果

结论

链表实现队列

实现单头链表队列

引用链表,实现接口功能LinkedList1Queue

复杂度分析

优化链表队列

实现有头尾链表队列

新建链表

引用链表,实现接口LinkedList2Queue

单头链表队列和有尾的链表队列性能对比