主頁(yè) > 知識(shí)庫(kù) > 算法系列15天速成 第九天 隊(duì)列

算法系列15天速成 第九天 隊(duì)列
熱門標(biāo)簽：電銷機(jī)器人怎么收費(fèi) 滄州智能外呼系統(tǒng)收費(fèi) 嘟聲的電銷機(jī)器人 醫(yī)院地圖標(biāo)注 地圖標(biāo)注和圖片標(biāo)注 忻州外呼系統(tǒng)接口對(duì)接 湖北穩(wěn)定外呼系統(tǒng) 洛陽(yáng)便宜外呼系統(tǒng)廠家 語(yǔ)音平臺(tái)系統(tǒng)

一：概念

          隊(duì)列是一個(gè)”先進(jìn)先出“的線性表，牛X的名字就是“First in First Out(FIFO)”，生活中有很多這樣的場(chǎng)景，比如讀書的時(shí)候去食堂打飯時(shí)的”排隊(duì)“。當(dāng)然我們拒絕插隊(duì)。

二：存儲(chǔ)結(jié)構(gòu)

         前幾天也說(shuō)過(guò)，線性表有兩種”存儲(chǔ)結(jié)構(gòu)“，① 順序存儲(chǔ),②鏈?zhǔn)酱鎯?chǔ)。當(dāng)然“隊(duì)列”也脫離不了這兩種服務(wù)，這里我就分享一下“順序存儲(chǔ)”。

     順序存儲(chǔ)時(shí)，我們會(huì)維護(hù)一個(gè)叫做”head頭指針“和”tail尾指針“，分別指向隊(duì)列的開(kāi)頭和結(jié)尾。


代碼段如下：

復(fù)制代碼 代碼如下:

#region 隊(duì)列的數(shù)據(jù)結(jié)構(gòu)
    /// summary>
/// 隊(duì)列的數(shù)據(jù)結(jié)構(gòu)
/// /summary>
/// typeparam name="T">/typeparam>
    public class SeqQueueT>
    {
        private const int maxSize = 100;

        public int MaxSize
        {
            get { return maxSize; }
        }

        /// summary>
/// 順序隊(duì)列的存儲(chǔ)長(zhǎng)度
/// /summary>
        public T[] data = new T[maxSize];

        //頭指針
        public int head;

        //尾指針
        public int tail;

    }
    #endregion

三：常用操作

      隊(duì)列的操作一般分為：

      ①： 初始化隊(duì)列。

      ②:   出隊(duì)。

      ③： 入隊(duì)。

      ④： 獲取隊(duì)頭。

      ⑤： 獲取隊(duì)長(zhǎng)。


1：初始化隊(duì)列

        這個(gè)很簡(jiǎn)單，剛才也說(shuō)過(guò)了，隊(duì)列是用一個(gè)head和tail的指針來(lái)維護(hù)。分別設(shè)置為0即可。

2：出隊(duì)

       看著“隊(duì)列”的結(jié)構(gòu)圖，大家都知道，出隊(duì)肯定跟head指針有關(guān)，需要做兩件事情，

       第一： 判斷隊(duì)列是否為空，這個(gè)我想大家都知道。
       第二： 將head頭指針向后移動(dòng)一位，返回head移動(dòng)前的元素，時(shí)間復(fù)雜度為O(1)。



代碼段如下：

復(fù)制代碼 代碼如下:

#region 隊(duì)列元素出隊(duì)
        /// summary>
/// 隊(duì)列元素出隊(duì)
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="seqQueue">/param>
/// returns>/returns>
        public T SeqQueueOutT>(SeqQueueT> seqQueue)
        {
            if (SeqQueueIsEmpty(seqQueue))
                throw new Exception("隊(duì)列已空，不能進(jìn)行出隊(duì)操作");

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

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

            return single;

        }
        #endregion

3：入隊(duì)

      這個(gè)跟”出隊(duì)“的思想相反，同樣也是需要做兩件事情。

      第一：判斷隊(duì)列是否已滿。

      第二：將tail指針向后移動(dòng)一位，時(shí)間復(fù)雜度為O(1)。

代碼段如下：

復(fù)制代碼 代碼如下:

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

            //入隊(duì)操作
            seqQueue.data[seqQueue.tail++] = data;

            return seqQueue;
        }
        #endregion

4： 獲取隊(duì)頭

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

       他是只讀操作，不會(huì)破壞”隊(duì)列“結(jié)構(gòu)，時(shí)間復(fù)雜度為O（1）。

 

代碼段如下：

復(fù)制代碼 代碼如下:

#region 獲取隊(duì)頭元素
        /// summary>
        /// 獲取隊(duì)頭元素
        /// /summary>
        /// typeparam name="T">/typeparam>
        /// param name="seqQueue">/param>
        /// returns>/returns>
        public T SeqQueuePeekT>(SeqQueueT> seqQueue)
        {
            if (SeqQueueIsEmpty(seqQueue))
                throw new Exception("隊(duì)列已空，不能進(jìn)行出隊(duì)操作");

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

5: 獲取隊(duì)長(zhǎng)

       大家都知道，我們是用數(shù)組來(lái)實(shí)現(xiàn)隊(duì)列，所以千萬(wàn)不要想當(dāng)然的認(rèn)為數(shù)組長(zhǎng)度是XXX，

       我們維護(hù)的是一個(gè)head和tail的指針，所以長(zhǎng)度自然就是tail-head咯，時(shí)間復(fù)雜度為O(1)。

代碼段如下：

復(fù)制代碼 代碼如下:

/// summary>
/// 獲取隊(duì)列長(zhǎng)度
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="seqQueue">/param>
/// returns>/returns>
        public int SeqQueueLenT>(SeqQueueT> seqQueue)
        {
            return seqQueue.tail - seqQueue.head;
        }

然后上一下總的運(yùn)行代碼：

復(fù)制代碼 代碼如下:

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

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

            SeqQueueClass queueManage = new SeqQueueClass();

            Console.WriteLine("目前隊(duì)列是否為空：" + queueManage.SeqQueueIsEmpty(seqQueue) + "\n");

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

            Display(seqQueue);

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

            Display(seqQueue);

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

            Console.Read();
        }
        //展示隊(duì)列元素
        static void Display(SeqQueueStudent> seqQueue)
        {
            Console.WriteLine("******************* 鏈表數(shù)據(jù)如下 *******************");

            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("******************* 鏈表數(shù)據(jù)展示完畢 *******************\n");
        }
    }

    #region 學(xué)生數(shù)據(jù)實(shí)體
    /// summary>
/// 學(xué)生數(shù)據(jù)實(shí)體
/// /summary>
    public class Student
    {
        public int ID { get; set; }

        public string Name { get; set; }

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

    #region 隊(duì)列的數(shù)據(jù)結(jié)構(gòu)
    /// summary>
/// 隊(duì)列的數(shù)據(jù)結(jié)構(gòu)
/// /summary>
/// typeparam name="T">/typeparam>
    public class SeqQueueT>
    {
        private const int maxSize = 100;

        public int MaxSize
        {
            get { return maxSize; }
        }

        /// summary>
/// 順序隊(duì)列的存儲(chǔ)長(zhǎng)度
/// /summary>
        public T[] data = new T[maxSize];

        //頭指針
        public int head;

        //尾指針
        public int tail;

    }
    #endregion

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

            return seqQueue;
        }
        #endregion

        #region 隊(duì)列是否為空
        /// summary>
/// 隊(duì)列是否為空
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="seqQueue">/param>
/// returns>/returns>
        public bool SeqQueueIsEmptyT>(SeqQueueT> seqQueue)
        {
            //如果兩指針重合，說(shuō)明隊(duì)列已經(jīng)清空
            if (seqQueue.head == seqQueue.tail)
                return true;
            return false;
        }
        #endregion

        #region 隊(duì)列是否已滿
        /// summary>
/// 隊(duì)列是否已滿
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="seqQueue">/param>
/// returns>/returns>
        public bool SeqQueueIsFullT>(SeqQueueT> seqQueue)
        {
            //如果尾指針到達(dá)數(shù)組末尾，說(shuō)明隊(duì)列已經(jīng)滿
            if (seqQueue.tail == seqQueue.MaxSize)
                return true;
            return false;
        }
        #endregion

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

            //入隊(duì)操作
            seqQueue.data[seqQueue.tail++] = data;

            return seqQueue;
        }
        #endregion

        #region 隊(duì)列元素出隊(duì)
        /// summary>
/// 隊(duì)列元素出隊(duì)
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="seqQueue">/param>
/// returns>/returns>
        public T SeqQueueOutT>(SeqQueueT> seqQueue)
        {
            if (SeqQueueIsEmpty(seqQueue))
                throw new Exception("隊(duì)列已空，不能進(jìn)行出隊(duì)操作");

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

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

            return single;

        }
        #endregion

        #region 獲取隊(duì)頭元素
        /// summary>
/// 獲取隊(duì)頭元素
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="seqQueue">/param>
/// returns>/returns>
        public T SeqQueuePeekT>(SeqQueueT> seqQueue)
        {
            if (SeqQueueIsEmpty(seqQueue))
                throw new Exception("隊(duì)列已空，不能進(jìn)行出隊(duì)操作");

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

        /// summary>
/// 獲取隊(duì)列長(zhǎng)度
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="seqQueue">/param>
/// returns>/returns>
        public int SeqQueueLenT>(SeqQueueT> seqQueue)
        {
            return seqQueue.tail - seqQueue.head;
        }
    }
    #endregion
}

三：順序隊(duì)列的缺陷

大家看這張圖，不知道可有什么異樣的感覺(jué)，在這種狀態(tài)下，我入隊(duì)操作，發(fā)現(xiàn)程序提示隊(duì)列

已滿，但是tnd我這個(gè)數(shù)組還有一個(gè)空間啊，是的，這就是所謂的“假溢出”。

四：循環(huán)隊(duì)列
 

俗話說(shuō)的好啊，“沒(méi)有跨不過(guò)的坎”。

1: 概念

       之所以叫“循環(huán)”，得益于神奇的“%”。他讓隊(duì)列的首位進(jìn)行相連，形成了一個(gè)我們思維中的

       “圈圈”。
 

2：循環(huán)公式

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

      多看幾眼，大家就看通了其中循環(huán)的道理，我要做成如下的圖:

3：對(duì)循環(huán)的改造

      先前看了一些資料，有的壓根就是錯(cuò)的，有的說(shuō)想要循環(huán)，就要犧牲一個(gè)單位的空間。

      我覺(jué)得沒(méi)必要。我既要循環(huán)又不犧牲空間，所以反射了一下framework中的Queue類。

      改造后代碼如下：

復(fù)制代碼 代碼如下:

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

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

            SeqQueueClass queueManage = new SeqQueueClass();

            Console.WriteLine("目前隊(duì)列是否為空：" + queueManage.SeqQueueIsEmpty(seqQueue) + "\n");

            Console.WriteLine("將ID=1，2，3的實(shí)體加入隊(duì)列\(zhòng)n");
            queueManage.SeqQueueIn(seqQueue, new Student() { ID = 1, Name = "hxc520", Age = 23 });
            queueManage.SeqQueueIn(seqQueue, new Student() { ID = 2, Name = "一線碼農(nóng)", Age = 23 });
            queueManage.SeqQueueIn(seqQueue, new Student() { ID = 3, Name = "51cto", Age = 23 });

            Console.WriteLine("\n當(dāng)前隊(duì)列個(gè)數(shù)：" + queueManage.SeqQueueLen(seqQueue) + "");

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

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

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

            Console.WriteLine("\n當(dāng)前隊(duì)列個(gè)數(shù)：" + queueManage.SeqQueueLen(seqQueue) + "");

            Console.Read();
        }
    }

    #region 學(xué)生數(shù)據(jù)實(shí)體
    /// summary>
/// 學(xué)生數(shù)據(jù)實(shí)體
/// /summary>
    public class Student
    {
        public int ID { get; set; }

        public string Name { get; set; }

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

    #region 隊(duì)列的數(shù)據(jù)結(jié)構(gòu)
    /// summary>
/// 隊(duì)列的數(shù)據(jù)結(jié)構(gòu)
/// /summary>
/// typeparam name="T">/typeparam>
    public class SeqQueueT>
    {
        private const int maxSize = 3;

        public int MaxSize
        {
            get { return maxSize; }
        }

        /// summary>
/// 順序隊(duì)列的存儲(chǔ)長(zhǎng)度
/// /summary>
        public T[] data = new T[maxSize];

        //頭指針
        public int head;

        //尾指針
        public int tail;

        //隊(duì)列中有效的數(shù)字個(gè)數(shù)
        public int size;
    }
    #endregion

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

            return seqQueue;
        }
        #endregion

        #region 隊(duì)列是否為空
        /// summary>
/// 隊(duì)列是否為空
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="seqQueue">/param>
/// returns>/returns>
        public bool SeqQueueIsEmptyT>(SeqQueueT> seqQueue)
        {
            //如果兩指針重合，說(shuō)明隊(duì)列已經(jīng)清空
            if (seqQueue.size == 0)
                return true;
            return false;
        }
        #endregion

        #region 隊(duì)列是否已滿
        /// summary>
/// 隊(duì)列是否已滿
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="seqQueue">/param>
/// returns>/returns>
        public bool SeqQueueIsFullT>(SeqQueueT> seqQueue)
        {
            //采用循環(huán)隊(duì)列后，頭指針
            if (seqQueue.size == seqQueue.MaxSize)
                return true;
            return false;
        }
        #endregion

        #region 隊(duì)列元素入隊(duì)
        /// summary>
/// 隊(duì)列元素入隊(duì)
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="seqQueue">/param>
/// param name="data">/param>
/// returns>/returns>
        public SeqQueueT> SeqQueueInT>(SeqQueueT> seqQueue, T data)
        {
            //如果隊(duì)列已滿，則不能進(jìn)行入隊(duì)操作
            if (SeqQueueIsFull(seqQueue))
                throw new Exception("隊(duì)列已滿，還入啥隊(duì)列??！");

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

            //隊(duì)列實(shí)際元素增加
            seqQueue.size++;

            return seqQueue;
        }
        #endregion

        #region 隊(duì)列元素出隊(duì)
        /// summary>
/// 隊(duì)列元素出隊(duì)
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="seqQueue">/param>
/// returns>/returns>
        public T SeqQueueOutT>(SeqQueueT> seqQueue)
        {
            if (SeqQueueIsEmpty(seqQueue))
                throw new Exception("隊(duì)列已空，大哥，不要在出隊(duì)了！");

            //循環(huán)隊(duì)列出隊(duì)，展現(xiàn)的是head的靈活性
            seqQueue.head = (seqQueue.head + 1) % seqQueue.MaxSize;

            //隊(duì)列實(shí)際元素遞減
            seqQueue.size--;

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

        #region 獲取隊(duì)頭元素
        /// summary>
/// 獲取隊(duì)頭元素
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="seqQueue">/param>
/// returns>/returns>
        public T SeqQueuePeekT>(SeqQueueT> seqQueue)
        {
            if (SeqQueueIsEmpty(seqQueue))
                throw new Exception("隊(duì)列已空，不能進(jìn)行出隊(duì)操作");

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

        #region 獲取隊(duì)列長(zhǎng)度
        /// summary>
/// 獲取隊(duì)列長(zhǎng)度
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="seqQueue">/param>
/// returns>/returns>
        public int SeqQueueLenT>(SeqQueueT> seqQueue)
        {
            return seqQueue.size;
        }
        #endregion
    }
    #endregion
}



您可能感興趣的文章:
  • 算法系列15天速成 第十四天 圖【上】
  • 算法系列15天速成——第十三天 樹(shù)操作【下】
  • 算法系列15天速成 第十二天 樹(shù)操作【中】
  • 算法系列15天速成 第十一天 樹(shù)操作（上）
  • 算法系列15天速成 第十天 棧
  • 算法系列15天速成 第八天 線性表【下】
  • 算法系列15天速成 第七天 線性表【上】
  • 算法系列15天速成 第六天 五大經(jīng)典查找【下】
  • 算法系列15天速成 第五天 五大經(jīng)典查找【中】
  • 算法系列15天速成 第四天 五大經(jīng)典查找【上】
  • 算法系列15天速成 第三天 七大經(jīng)典排序【下】
  • 算法系列15天速成 第二天 七大經(jīng)典排序【中】
  • 算法系列15天速成 第一天 七大經(jīng)典排序【上】
  • 算法系列15天速成——第十五天 圖【下】（大結(jié)局）

標(biāo)簽：山南 日照 巴彥淖爾 定州 防城港 96 內(nèi)蒙古 宜賓

巨人網(wǎng)絡(luò)通訊聲明：本文標(biāo)題《算法系列15天速成 第九天 隊(duì)列》，本文關(guān)鍵詞  算法,系列,15天,速成,第,；如發(fā)現(xiàn)本文內(nèi)容存在版權(quán)問(wèn)題，煩請(qǐng)?zhí)峁┫嚓P(guān)信息告之我們，我們將及時(shí)溝通與處理。本站內(nèi)容系統(tǒng)采集于網(wǎng)絡(luò)，涉及言論、版權(quán)與本站無(wú)關(guān)。
  • 相關(guān)文章
  • 下面列出與本文章《算法系列15天速成 第九天 隊(duì)列》相關(guān)的同類信息！
  • 本頁(yè)收集關(guān)于算法系列15天速成 第九天 隊(duì)列的相關(guān)信息資訊供網(wǎng)民參考！
    • 推薦文章