隊(duì)列與前天的棧是表親關(guān)系拐辽，也是一種基本的數(shù)據(jù)結(jié)構(gòu)减噪，與棧不同的是赞庶，它是遵循先進(jìn)先出的原則(FIFO)伏蚊，即只能在隊(duì)首刪除元素，隊(duì)尾插入元素膛虫。

通常我們把插入元素的一段稱為對(duì)尾，刪除元素的一端稱為隊(duì)頭钓猬。

這個(gè)很容易理解稍刀，想象肯德基排隊(duì)點(diǎn)餐：你從隊(duì)尾開始排隊(duì)，正在點(diǎn)餐的人在隊(duì)頭敞曹。

隊(duì)列在很多場(chǎng)景都有應(yīng)用账月，且廣泛的應(yīng)用于很多計(jì)算機(jī)設(shè)備中，比如網(wǎng)絡(luò)打印機(jī)澳迫，web服務(wù)器等局齿。

同樣的，先來分析下隊(duì)列應(yīng)該有哪些方法橄登，對(duì)于隊(duì)列Q抓歼，抽象數(shù)據(jù)類型ADT應(yīng)該包含兩種主要的方法出隊(duì)列、進(jìn)隊(duì)列：

• Q.enqueue(e) 入隊(duì)列拢锹，在隊(duì)尾插入一個(gè)元素谣妻。
• Q.dequeue 出隊(duì)列，在隊(duì)列中有元素的情況下卒稳，將隊(duì)頭元素返回蹋半，并從隊(duì)列中移除，在隊(duì)列為空是充坑，返回錯(cuò)誤减江。
  對(duì)于我們使用來說他應(yīng)該還包括以下的方法：
• Q.frist() 返回隊(duì)列的隊(duì)頭元素染突，但是不移除隊(duì)頭元素，這有點(diǎn)像棧的pop()
• Q.is_empty() 如果隊(duì)列為空則返回True
• len(Q) 返回隊(duì)列中的元素個(gè)數(shù)
  為了方便我們學(xué)習(xí)這種數(shù)據(jù)結(jié)構(gòu)辈灼，我還實(shí)現(xiàn)了str()方法份企，用來打印隊(duì)列。

同樣的定義了茵休，隊(duì)列為空的一個(gè)異常類薪棒，繼承自Exception。

我們的隊(duì)列名稱叫做ArrayQueue榕莺，因?yàn)槲覀兊年?duì)列使用列表實(shí)現(xiàn)的俐芯。

我們用數(shù)組實(shí)現(xiàn)隊(duì)列有一個(gè)很不方便的地方就是出隊(duì)列的時(shí)候，我們?cè)谠O(shè)計(jì)時(shí)钉鸯，是將列表的前面作為隊(duì)頭的吧史，所以我們將元素出隊(duì)列的時(shí)候，很簡(jiǎn)單的實(shí)現(xiàn)是pop（0）,但是我在前面學(xué)習(xí)的過程中了解到唠雕，pop（）不帶參數(shù)的話時(shí)間復(fù)雜度為O(1)贸营，但是如果有參數(shù)，傳入索引岩睁，這會(huì)導(dǎo)致時(shí)間復(fù)雜度提高钞脂，變?yōu)镺(n-k+1)，k是元素的索引捕儒，因?yàn)楸校绻覀儚棾隽饲懊娴脑兀斜砭托枰獙⑦@個(gè)洞補(bǔ)上刘莹，來保證整個(gè)列表的索引的正確性阎毅，而在我們實(shí)現(xiàn)隊(duì)列出隊(duì)列的情況下，如果用pop（0）則會(huì)大大增加時(shí)間復(fù)雜度点弯，達(dá)到O(n)扇调。越簡(jiǎn)單的實(shí)現(xiàn)，則效率越低抢肛。

我們用新的方法來避免調(diào)用pop（0）狼钮。用一個(gè)指代為空的指針替代這個(gè)出隊(duì)列的元素，即用None來代替這個(gè)元素的位置捡絮，然后用一個(gè)成員變量self._front來標(biāo)識(shí)隊(duì)頭的位置燃领，這樣的話對(duì)于出隊(duì)操作就變成了O(1)，但是這樣子出隊(duì)列幾次后就會(huì)變成這樣：

隊(duì)頭     None    |    None    |    None    |    1    |    2    |    ········    |    6    |   隊(duì)尾 

因?yàn)榱斜碓诘讓邮怯脭?shù)組實(shí)現(xiàn)的锦援，隨著進(jìn)隊(duì)出隊(duì)的操作猛蔽，這個(gè)列表將變的越來越大，最終的大小是這個(gè)隊(duì)列自創(chuàng)建以來入隊(duì)元素的總數(shù)量。這是很可怕的曼库。
這種設(shè)計(jì)會(huì)對(duì)那種所需隊(duì)列大小相對(duì)穩(wěn)定区岗，但經(jīng)常入隊(duì)出隊(duì)的應(yīng)用非常不友好，會(huì)造成很大的內(nèi)存浪費(fèi)毁枯。
于是我們就考慮利用前面的這些None慈缔，——循環(huán)的使用列表，當(dāng)列表的隨后一個(gè)位置被使用之后种玛，將下一個(gè)保存的位置變?yōu)榱斜淼那懊妗?/p>

這樣就會(huì)出一個(gè)問題藐鹤，就是前面的對(duì)頭位置怎么確定，我們用這個(gè)公式 (self._front + 1) % N赂韵，N是當(dāng)前底層數(shù)組的長(zhǎng)度娱节。比如，我們的隊(duì)列底層數(shù)組的長(zhǎng)度為10:

None    |    None    |    None    |    1（self._front）    |    2    |    3    |    6    |    7    |    8    |    9    |

現(xiàn)在我們要?jiǎng)h除隊(duì)頭元素祭示，self._front = (self._front + 1) % N => (self._front = 3 + 1) % 10 = 4肄满，這樣就得到了我們的新的隊(duì)頭。

如果要新插入一個(gè)元素 ：

1    |    None    |    None    |    1（self._front）    |    2    |    3    |    6    |    7    |    8    |    9    |

就要用(self._front + self._size) % N來確定新加入元素的索引质涛。
這你自己算吧稠歉。

接下來就是動(dòng)態(tài)數(shù)組的問題了，當(dāng)所有的空間都滿了汇陆，我們需要擴(kuò)展空間怒炸，就需要將底層數(shù)組的大小變?yōu)樵瓉淼膬杀叮瑏斫档拖乱淮胃淖償?shù)組大小的概率毡代。

如果隊(duì)列中的元素個(gè)數(shù)小于等于空間的四分之一阅羹，就把底層數(shù)組的大小減小一半。

在改變數(shù)組大小的時(shí)候月趟，我們其實(shí)是用了一個(gè)新的數(shù)組灯蝴，將舊的數(shù)組值復(fù)制到新的數(shù)組中恢口，但是這不是單純的復(fù)制孝宗，因?yàn)槲覀冎霸谟?jì)算self._front時(shí)用到了當(dāng)前數(shù)組的大小，如果直接復(fù)制們就會(huì)出大問題耕肩，所以我們需要將原來的隊(duì)頭放到新數(shù)組的第一個(gè)因妇。

放出代碼：

class Empty(Exception):
    pass


class ArrayQueue:
    DEFAULT_CAPACITY = 10

    def __init__(self):
        self._data = [None] * ArrayQueue.DEFAULT_CAPACITY
        self._size = 0
        self._front = 0

    def __len__(self):
        return self._size

    def is_empty(self):
        return self._size == 0

    def first(self):
        if self.is_empty():
            raise Empty('Queue is empty!')
        return self._data[self._front]

    def enqueue(self, e):
        if self._size == len(self._data):
            self._resize(2 * len(self._data))  # 當(dāng)隊(duì)列滿了，就把隊(duì)列容量擴(kuò)大一倍
        avail = (self._front + self._size) % len(self._data)
        self._data[avail] = e
        self._size += 1

    def dequeue(self):
        if self.is_empty():
            raise Empty('Queue is empty!')
        answer = self._data[self._front]
        self._data[self._front] = None
        self._front = (self._front + 1) % len(self._data)
        self._size -= 1
        if 0 < self._size <len(self._data) // 4:
            self._resize(len(self._data)//2)  # 在隊(duì)列元素不足隊(duì)列容量的四分之一時(shí)猿诸，將隊(duì)列長(zhǎng)度縮小一半
        return answer

    def _resize(self, capacity):
        old = self._data
        walk = self._front
        self._data = [None] * capacity
        for k in range(self._size):
            self._data[k] = old[walk]
            walk = (1 + walk) % len(old)
        self._front = 0

    def __str__(self):
        return str(self._data)   # 為了方便我們觀察隊(duì)列內(nèi)部

這個(gè)隊(duì)列的每一種操作的時(shí)間復(fù)雜度都為O(1)婚被，其中入隊(duì)出隊(duì)的時(shí)間復(fù)雜的計(jì)算用到了會(huì)計(jì)學(xué)中攤銷算法。這里自行百度梳虽。

下面我們來測(cè)試一下這個(gè)隊(duì)列:

if __name__ == '__main__':
    my_queue = ArrayQueue()
    my_queue.enqueue(1)
    my_queue.enqueue(5)
    print(my_queue)
    my_queue.dequeue()
    my_queue.dequeue()
    print(my_queue)
    my_queue.enqueue(0)
    my_queue.enqueue(3)
    my_queue.enqueue(19)
    my_queue.enqueue(0)
    my_queue.enqueue(4)
    my_queue.enqueue(66)
    my_queue.enqueue(88)
    my_queue.enqueue(111)
    print(my_queue)
    my_queue.dequeue()
    my_queue.dequeue()
    my_queue.dequeue()
    my_queue.dequeue()
    print(my_queue)
    my_queue.enqueue(0)
    my_queue.enqueue(4)
    my_queue.enqueue(6)
    my_queue.enqueue(8)
    print(my_queue)
    my_queue.enqueue(11)
    print(my_queue)
    my_queue.enqueue(0)
    my_queue.enqueue(4)
    my_queue.enqueue(6)
    my_queue.enqueue(8)
    print(my_queue)

這涉及了所有需要改變隊(duì)列底層數(shù)組大小的情況址芯。

結(jié)果：

image.png

我在之前跟著書也寫過隊(duì)列，跟著個(gè)比起來，簡(jiǎn)直是垃圾——《python程序員算法寶典》張波谷炸、楚秦編著北专。

現(xiàn)在真是什么人都敢出來寫書。
垃圾Ｑ浮Ｍ赝恰！描孟！

我寫文章也就自己看看驶睦，你們竟然厚顏無恥出書！Ｄ湫选３『健！