<em id="hanht"></em>

    <dd id="hanht"></dd>

    <em id="hanht"><acronym id="hanht"></acronym></em>
    
    <button id="hanht"></button>
    <rp id="hanht"><object id="hanht"><blockquote id="hanht"></blockquote></object></rp><em id="hanht"></em>

    首頁 > 學院 > 邏輯算法 > 正文

    算法系列15天速成 第九天 隊列

    2020-10-08 16:14:32
    字體:
    來源:轉載
    供稿:網友

    一:概念

              隊列是一個”先進先出“的線性表,牛X的名字就是“First in First Out(FIFO)”,生活中有很多這樣的場景,比如讀書的時候去食堂打飯時的”排隊“。當然我們拒絕插隊。

    二:存儲結構

             前幾天也說過,線性表有兩種”存儲結構“,① 順序存儲,②鏈式存儲。當然“隊列”也脫離不了這兩種服務,這里我就分享一下“順序存儲”。

         順序存儲時,我們會維護一個叫做”head頭指針“和”tail尾指針“,分別指向隊列的開頭和結尾。


    代碼段如下:

    復制代碼 代碼如下:

    #region 隊列的數據結構
        /// <summary>
    /// 隊列的數據結構
    /// </summary>
    /// <typeparam name="T"></typeparam>
        public class SeqQueue<T>
        {
            private const int maxSize = 100;

            public int MaxSize
            {
                get { return maxSize; }
            }

            /// <summary>
    /// 順序隊列的存儲長度
    /// </summary>
            public T[] data = new T[maxSize];

            //頭指針
            public int head;

            //尾指針
            public int tail;

        }
        #endregion

    三:常用操作

          隊列的操作一般分為:

          ①: 初始化隊列。

          ②:   出隊。

          ③: 入隊。

          ④: 獲取隊頭。

          ⑤: 獲取隊長。


    1:初始化隊列

            這個很簡單,剛才也說過了,隊列是用一個head和tail的指針來維護。分別設置為0即可。

    2:出隊

           看著“隊列”的結構圖,大家都知道,出隊肯定跟head指針有關,需要做兩件事情,

           第一: 判斷隊列是否為空,這個我想大家都知道。
           第二: 將head頭指針向后移動一位,返回head移動前的元素,時間復雜度為O(1)。



    代碼段如下:

    復制代碼 代碼如下:

    #region 隊列元素出隊
            /// <summary>
    /// 隊列元素出隊
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="seqQueue"></param>
    /// <returns></returns>
            public T SeqQueueOut<T>(SeqQueue<T> seqQueue)
            {
                if (SeqQueueIsEmpty(seqQueue))
                    throw new Exception("隊列已空,不能進行出隊操作");

                var single = seqQueue.data[seqQueue.head];

                //head指針自增
                seqQueue.data[seqQueue.head++] = default(T);

                return single;

            }
            #endregion

    3:入隊

          這個跟”出隊“的思想相反,同樣也是需要做兩件事情。

          第一:判斷隊列是否已滿。

          第二:將tail指針向后移動一位,時間復雜度為O(1)。

    代碼段如下:

    復制代碼 代碼如下:

    #region 隊列元素入隊
            /// <summary>
    /// 隊列元素入隊
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="seqQueue"></param>
    /// <param name="data"></param>
    /// <returns></returns>
            public SeqQueue<T> SeqQueueIn<T>(SeqQueue<T> seqQueue, T data)
            {
                //如果隊列已滿,則不能進行入隊操作
                if (SeqQueueIsFull(seqQueue))
                    throw new Exception("隊列已滿,不能入隊操作");

                //入隊操作
                seqQueue.data[seqQueue.tail++] = data;

                return seqQueue;
            }
            #endregion

    4: 獲取隊頭

           知道”出隊“和”入隊“的原理,相信大家都懂的如何進行”獲取隊頭“操作,唯一不一樣的就是

           他是只讀操作,不會破壞”隊列“結構,時間復雜度為O(1)。

     

    代碼段如下:

    復制代碼 代碼如下:

    #region 獲取隊頭元素
            /// <summary>
            /// 獲取隊頭元素
            /// </summary>
            /// <typeparam name="T"></typeparam>
            /// <param name="seqQueue"></param>
            /// <returns></returns>
            public T SeqQueuePeek<T>(SeqQueue<T> seqQueue)
            {
                if (SeqQueueIsEmpty(seqQueue))
                    throw new Exception("隊列已空,不能進行出隊操作");

                return seqQueue.data[seqQueue.head];
            }
            #endregion

    5: 獲取隊長

           大家都知道,我們是用數組來實現隊列,所以千萬不要想當然的認為數組長度是XXX,

           我們維護的是一個head和tail的指針,所以長度自然就是tail-head咯,時間復雜度為O(1)。

    代碼段如下:

    復制代碼 代碼如下:

    /// <summary>
    /// 獲取隊列長度
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="seqQueue"></param>
    /// <returns></returns>
            public int SeqQueueLen<T>(SeqQueue<T> seqQueue)
            {
                return seqQueue.tail - seqQueue.head;
            }

    然后上一下總的運行代碼:

    復制代碼 代碼如下:

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

    namespace SeqQueue
    {
        public class Program
        {
            static void Main(string[] args)
            {
                SeqQueue<Student> seqQueue = new SeqQueue<Student>();

                SeqQueueClass queueManage = new SeqQueueClass();

                Console.WriteLine("目前隊列是否為空:" + queueManage.SeqQueueIsEmpty(seqQueue) + "/n");

                Console.WriteLine("將ID=1和ID=2的實體加入隊列");
                queueManage.SeqQueueIn(seqQueue, new Student() { ID = 1, Name = "hxc520", Age = 23 });
                queueManage.SeqQueueIn(seqQueue, new Student() { ID = 2, Name = "一線碼農", Age = 23 });

                Display(seqQueue);

                Console.WriteLine("將隊頭出隊");
                //將隊頭出隊
                var student = queueManage.SeqQueueOut(seqQueue);

                Display(seqQueue);

                //獲取隊頂元素
                student = queueManage.SeqQueuePeek(seqQueue);

                Console.Read();
            }
            //展示隊列元素
            static void Display(SeqQueue<Student> seqQueue)
            {
                Console.WriteLine("******************* 鏈表數據如下 *******************");

                for (int i = seqQueue.head; i < seqQueue.tail; i++)
                    Console.WriteLine("ID:" + seqQueue.data[i].ID +
                                      ",Name:" + seqQueue.data[i].Name +
                                      ",Age:" + seqQueue.data[i].Age);

                Console.WriteLine("******************* 鏈表數據展示完畢 *******************/n");
            }
        }

        #region 學生數據實體
        /// <summary>
    /// 學生數據實體
    /// </summary>
        public class Student
        {
            public int ID { get; set; }

            public string Name { get; set; }

            public int Age { get; set; }
        }
        #endregion

        #region 隊列的數據結構
        /// <summary>
    /// 隊列的數據結構
    /// </summary>
    /// <typeparam name="T"></typeparam>
        public class SeqQueue<T>
        {
            private const int maxSize = 100;

            public int MaxSize
            {
                get { return maxSize; }
            }

            /// <summary>
    /// 順序隊列的存儲長度
    /// </summary>
            public T[] data = new T[maxSize];

            //頭指針
            public int head;

            //尾指針
            public int tail;

        }
        #endregion

        #region 隊列的基本操作
        /// <summary>
    /// 隊列的基本操作
    /// </summary>
        public class SeqQueueClass
        {
            #region 隊列的初始化操作
            /// <summary>
    /// 隊列的初始化操作
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="seqQueue"></param>
            public SeqQueue<T> SeqQueueInit<T>(SeqQueue<T> seqQueue)
            {
                seqQueue.head = 0;
                seqQueue.tail = 0;

                return seqQueue;
            }
            #endregion

            #region 隊列是否為空
            /// <summary>
    /// 隊列是否為空
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="seqQueue"></param>
    /// <returns></returns>
            public bool SeqQueueIsEmpty<T>(SeqQueue<T> seqQueue)
            {
                //如果兩指針重合,說明隊列已經清空
                if (seqQueue.head == seqQueue.tail)
                    return true;
                return false;
            }
            #endregion

            #region 隊列是否已滿
            /// <summary>
    /// 隊列是否已滿
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="seqQueue"></param>
    /// <returns></returns>
            public bool SeqQueueIsFull<T>(SeqQueue<T> seqQueue)
            {
                //如果尾指針到達數組末尾,說明隊列已經滿
                if (seqQueue.tail == seqQueue.MaxSize)
                    return true;
                return false;
            }
            #endregion

            #region 隊列元素入隊
            /// <summary>
    /// 隊列元素入隊
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="seqQueue"></param>
    /// <param name="data"></param>
    /// <returns></returns>
            public SeqQueue<T> SeqQueueIn<T>(SeqQueue<T> seqQueue, T data)
            {
                //如果隊列已滿,則不能進行入隊操作
                if (SeqQueueIsFull(seqQueue))
                    throw new Exception("隊列已滿,不能入隊操作");

                //入隊操作
                seqQueue.data[seqQueue.tail++] = data;

                return seqQueue;
            }
            #endregion

            #region 隊列元素出隊
            /// <summary>
    /// 隊列元素出隊
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="seqQueue"></param>
    /// <returns></returns>
            public T SeqQueueOut<T>(SeqQueue<T> seqQueue)
            {
                if (SeqQueueIsEmpty(seqQueue))
                    throw new Exception("隊列已空,不能進行出隊操作");

                var single = seqQueue.data[seqQueue.head];

                //head指針自增
                seqQueue.data[seqQueue.head++] = default(T);

                return single;

            }
            #endregion

            #region 獲取隊頭元素
            /// <summary>
    /// 獲取隊頭元素
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="seqQueue"></param>
    /// <returns></returns>
            public T SeqQueuePeek<T>(SeqQueue<T> seqQueue)
            {
                if (SeqQueueIsEmpty(seqQueue))
                    throw new Exception("隊列已空,不能進行出隊操作");

                return seqQueue.data[seqQueue.head];
            }
            #endregion

            /// <summary>
    /// 獲取隊列長度
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="seqQueue"></param>
    /// <returns></returns>
            public int SeqQueueLen<T>(SeqQueue<T> seqQueue)
            {
                return seqQueue.tail - seqQueue.head;
            }
        }
        #endregion
    }

    三:順序隊列的缺陷

    大家看這張圖,不知道可有什么異樣的感覺,在這種狀態下,我入隊操作,發現程序提示隊列

    已滿,但是tnd我這個數組還有一個空間啊,是的,這就是所謂的“假溢出”。

    四:循環隊列
     

    俗話說的好啊,“沒有跨不過的坎”。

    1: 概念

           之所以叫“循環”,得益于神奇的“%”。他讓隊列的首位進行相連,形成了一個我們思維中的

           “圈圈”。
     

    2:循環公式

          tail=(tail+1)%array.Length;

          多看幾眼,大家就看通了其中循環的道理,我要做成如下的圖:

    3:對循環的改造

          先前看了一些資料,有的壓根就是錯的,有的說想要循環,就要犧牲一個單位的空間。

          我覺得沒必要。我既要循環又不犧牲空間,所以反射了一下framework中的Queue類。

          改造后代碼如下:

    復制代碼 代碼如下:

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

    namespace SeqQueue
    {
        public class Program
        {
            static void Main(string[] args)
            {
                SeqQueue<Student> seqQueue = new SeqQueue<Student>();

                SeqQueueClass queueManage = new SeqQueueClass();

                Console.WriteLine("目前隊列是否為空:" + queueManage.SeqQueueIsEmpty(seqQueue) + "/n");

                Console.WriteLine("將ID=1,2,3的實體加入隊列/n");
                queueManage.SeqQueueIn(seqQueue, new Student() { ID = 1, Name = "hxc520", Age = 23 });
                queueManage.SeqQueueIn(seqQueue, new Student() { ID = 2, Name = "一線碼農", Age = 23 });
                queueManage.SeqQueueIn(seqQueue, new Student() { ID = 3, Name = "51cto", Age = 23 });

                Console.WriteLine("/n當前隊列個數:" + queueManage.SeqQueueLen(seqQueue) + "");

                Console.WriteLine("/n*********************************************/n");

                Console.WriteLine("我要出隊了/n");
                queueManage.SeqQueueOut(seqQueue);

                Console.WriteLine("哈哈,看看跟順序隊列異樣之處,我再入隊,看是否溢出/n");
                queueManage.SeqQueueIn(seqQueue, new Student() { ID = 4, Name = "博客園", Age = 23 });
                Console.WriteLine("/n....一切正常,入隊成功");

                Console.WriteLine("/n當前隊列個數:" + queueManage.SeqQueueLen(seqQueue) + "");

                Console.Read();
            }
        }

        #region 學生數據實體
        /// <summary>
    /// 學生數據實體
    /// </summary>
        public class Student
        {
            public int ID { get; set; }

            public string Name { get; set; }

            public int Age { get; set; }
        }
        #endregion

        #region 隊列的數據結構
        /// <summary>
    /// 隊列的數據結構
    /// </summary>
    /// <typeparam name="T"></typeparam>
        public class SeqQueue<T>
        {
            private const int maxSize = 3;

            public int MaxSize
            {
                get { return maxSize; }
            }

            /// <summary>
    /// 順序隊列的存儲長度
    /// </summary>
            public T[] data = new T[maxSize];

            //頭指針
            public int head;

            //尾指針
            public int tail;

            //隊列中有效的數字個數
            public int size;
        }
        #endregion

        #region 隊列的基本操作
        /// <summary>
    /// 隊列的基本操作
    /// </summary>
        public class SeqQueueClass
        {
            #region 隊列的初始化操作
            /// <summary>
    /// 隊列的初始化操作
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="seqQueue"></param>
            public SeqQueue<T> SeqQueueInit<T>(SeqQueue<T> seqQueue)
            {
                seqQueue.size = seqQueue.head = seqQueue.tail = 0;

                return seqQueue;
            }
            #endregion

            #region 隊列是否為空
            /// <summary>
    /// 隊列是否為空
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="seqQueue"></param>
    /// <returns></returns>
            public bool SeqQueueIsEmpty<T>(SeqQueue<T> seqQueue)
            {
                //如果兩指針重合,說明隊列已經清空
                if (seqQueue.size == 0)
                    return true;
                return false;
            }
            #endregion

            #region 隊列是否已滿
            /// <summary>
    /// 隊列是否已滿
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="seqQueue"></param>
    /// <returns></returns>
            public bool SeqQueueIsFull<T>(SeqQueue<T> seqQueue)
            {
                //采用循環隊列后,頭指針
                if (seqQueue.size == seqQueue.MaxSize)
                    return true;
                return false;
            }
            #endregion

            #region 隊列元素入隊
            /// <summary>
    /// 隊列元素入隊
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="seqQueue"></param>
    /// <param name="data"></param>
    /// <returns></returns>
            public SeqQueue<T> SeqQueueIn<T>(SeqQueue<T> seqQueue, T data)
            {
                //如果隊列已滿,則不能進行入隊操作
                if (SeqQueueIsFull(seqQueue))
                    throw new Exception("隊列已滿,還入啥隊列??!");

                //采用循環隊列,必須先賦值,在自增tail指針
                seqQueue.data[seqQueue.tail] = data;
                seqQueue.tail = (seqQueue.tail + 1) % seqQueue.MaxSize;

                //隊列實際元素增加
                seqQueue.size++;

                return seqQueue;
            }
            #endregion

            #region 隊列元素出隊
            /// <summary>
    /// 隊列元素出隊
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="seqQueue"></param>
    /// <returns></returns>
            public T SeqQueueOut<T>(SeqQueue<T> seqQueue)
            {
                if (SeqQueueIsEmpty(seqQueue))
                    throw new Exception("隊列已空,大哥,不要在出隊了!");

                //循環隊列出隊,展現的是head的靈活性
                seqQueue.head = (seqQueue.head + 1) % seqQueue.MaxSize;

                //隊列實際元素遞減
                seqQueue.size--;

                return seqQueue.data[seqQueue.head];
            }
            #endregion

            #region 獲取隊頭元素
            /// <summary>
    /// 獲取隊頭元素
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="seqQueue"></param>
    /// <returns></returns>
            public T SeqQueuePeek<T>(SeqQueue<T> seqQueue)
            {
                if (SeqQueueIsEmpty(seqQueue))
                    throw new Exception("隊列已空,不能進行出隊操作");

                return seqQueue.data[seqQueue.head];
            }
            #endregion

            #region 獲取隊列長度
            /// <summary>
    /// 獲取隊列長度
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="seqQueue"></param>
    /// <returns></returns>
            public int SeqQueueLen<T>(SeqQueue<T> seqQueue)
            {
                return seqQueue.size;
            }
            #endregion
        }
        #endregion
    }



    發表評論 共有條評論
    用戶名: 密碼:
    驗證碼: 匿名發表
    一级特黄大片欧美久久久久_一本一道久久综合狠狠老_JLZZ日本人年轻护士_欧美男男作爱VIDEOS可播放
      <em id="hanht"></em>

      <dd id="hanht"></dd>

      <em id="hanht"><acronym id="hanht"></acronym></em>
      
      <button id="hanht"></button>
      <rp id="hanht"><object id="hanht"><blockquote id="hanht"></blockquote></object></rp><em id="hanht"></em>