天天看點

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

可能大家都知道,線性表的變種非常非常多,比如今天講的“隊列”,灰常有意思啊。

一:概念

          隊列是一個”先進先出“的線性表,牛x的名字就是“first in first out(fifo)”,

      生活中有很多這樣的場景,比如讀書的時候去食堂打飯時的”排隊“。當然我們拒絕插隊。

二:存儲結構

         前幾天也說過,線性表有兩種”存儲結構“,① 順序存儲,②鍊式存儲。當然“隊列”也脫離

     不了這兩種服務,這裡我就分享一下“順序存儲”。

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

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

代碼段如下:

三:常用操作

      隊列的操作一般分為:

      ①: 初始化隊列。

      ②:   出隊。

      ③: 入隊。

      ④: 擷取隊頭。

      ⑤: 擷取隊長。

1:初始化隊列

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

2:出隊

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

       第一: 判斷隊列是否為空,這個我想大家都知道。

       第二: 将head頭指針向後移動一位,傳回head移動前的元素,時間複雜度為o(1)。

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

3:入隊

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

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

      第二:将tail指針向後移動一位,時間複雜度為o(1)。

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

4: 擷取隊頭

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

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

5: 擷取隊長

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

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

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

然後上一下總的運作代碼:

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

三:順序隊列的缺陷

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

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

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

四:循環隊列

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

1: 概念

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

       “圈圈”。

2:循環公式

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

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

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

3:對循環的改造

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

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

      改造後代碼如下:

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

繼續閱讀