隊(duì)列和棧

前面講了線性和鏈?zhǔn)浇Y(jié)構(gòu)，如果你順利掌握了，下邊的隊(duì)列和棧就小菜一碟了。因?yàn)槲覀儠们皟烧轮v到的東西來實(shí)現(xiàn)隊(duì)列和棧。
之所以放到一起講是因?yàn)檫@兩個東西很類似，隊(duì)列是先進(jìn)先出結(jié)構(gòu)(FIFO, first in first out)，
棧是后進(jìn)先出結(jié)構(gòu)(LIFO, last in first out)。

生活中的數(shù)據(jù)結(jié)構(gòu)：

• 隊(duì)列。沒錯就是咱平常排隊(duì)，第一個來的第一個走

本章我們詳細(xì)講講常用的隊(duì)列

隊(duì)列 Queue

這里賣個關(guān)子，如果你熟悉了上兩節(jié)講的內(nèi)容，這里你會選取哪個數(shù)據(jù)結(jié)構(gòu)作為隊(duì)列的底層存儲？
還記得第一章講的如何實(shí)現(xiàn) ADT 嗎？我視頻了說了三個注意事項(xiàng)：

• 1.如何選用恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)作為存儲？
• 2.選取的數(shù)據(jù)結(jié)構(gòu)能否滿足 ADT 的功能需求
• 3.實(shí)現(xiàn)效率如何？

我們先來看看 list 可以不？對照這個三個需求，看看能否滿足：

• 1.我們選擇了 list
• 2.看起來隊(duì)列需要從頭刪除，向尾部增加元素，也就是 list.pop(0) 和 list.append(element)
• 3.嗯，貌似 list.pop(0) 會導(dǎo)致所有其后所有元素向前移動一個位置，O(n)復(fù)雜度。append 平均倒是O(1)，但是如果內(nèi)存不夠還要重新分配內(nèi)存。

你看，使用了 list 的話頻繁 pop(0) 是非常低效的。(當(dāng)然list 實(shí)現(xiàn)還有另一種方式就是插入用 list.insert(0, item)，刪除用list.pop())

腦子再轉(zhuǎn)轉(zhuǎn)， 我們第二章實(shí)現(xiàn)了 鏈表 LinkedList，看看能否滿足要求：

• 1.這里選擇 LinkedList
• 2.刪除頭元素 LinkedList.popleft()，追加 append(element)。都可以滿足
• 3.哇歐，這兩個操作都是 O(1) 的，完美。

好， 就用 LinkedList 了，我們開始實(shí)現(xiàn)，具體看視頻。這次實(shí)現(xiàn)我們還將演示自定義異常和測試異常。

用數(shù)組實(shí)現(xiàn)隊(duì)列

難道用數(shù)組就不能實(shí)現(xiàn)隊(duì)列了嗎？其實(shí)還是可以的。只不過數(shù)組是預(yù)先分配固定內(nèi)存的，所以如果你知道了隊(duì)列的最大長度，也是
可以用數(shù)組來實(shí)現(xiàn)的。

想象一下，隊(duì)列就倆操作，進(jìn)進(jìn)出出，一進(jìn)一出，pop 和 push 操作。
似乎只要兩個下標(biāo) head, tail 就可以了。 當(dāng)我們 push 的時候賦值并且前移 head，pop 的時候前移 tail 就可以了。你可以在紙上
模擬下試試。列隊(duì)的長度就是 head-pop，這個長度必須不能大于初始化的最大程度。

如果 head 先到了數(shù)組末尾咋辦？重頭來唄，只要我們保證 tail 不會超過 head 就行。

head = 0,1,2,3,4 … 0,1,2,3,4 …

重頭再來，循環(huán)往復(fù)，仿佛一個輪回。。。。
怎么重頭來呢？看上邊數(shù)組的規(guī)律你如果還想不起來用取模，估計(jì)小學(xué)數(shù)學(xué)是體育老師教的。

maxsize = 5
for i in range(100):print(i % maxsize)

我們來實(shí)現(xiàn)一個空間有限的循環(huán)隊(duì)列。ArrayQueue，它的實(shí)現(xiàn)很簡單，但是缺點(diǎn)是需要預(yù)先知道隊(duì)列的長度來分配內(nèi)存。

雙端隊(duì)列 Double ended Queue

看了視頻相信你已經(jīng)會實(shí)現(xiàn)隊(duì)列了，你可能還聽過雙端隊(duì)列。上邊講到的隊(duì)列 隊(duì)頭出，尾尾進(jìn)，我們?nèi)绻腩^部和尾巴都能進(jìn)能出呢？
這就是雙端隊(duì)列了，如果你用過 collections.deque 模塊，就是這個東西。他能高效在兩頭操作。

假如讓你實(shí)現(xiàn)你能想起來嘛？
似乎我們需要一個能 append() appendleft() popleft() pop() 都是 O(1) 的數(shù)據(jù)結(jié)構(gòu)。

上邊我們實(shí)現(xiàn) 隊(duì)列的 LinkedList 可以嗎？貌似就差一個 pop() 最后邊的元素?zé)o法實(shí)現(xiàn)了。
對，我們還有雙端鏈表。它有這幾個方法：

• append
• appendleft
• headnode()
• tailnode()
• remove(node) # O(1)

啊哈，似乎刪除頭尾都可以啦，而且都是 O(1) 的，完美。
交給你一個艱巨的任務(wù)，實(shí)現(xiàn)雙端隊(duì)列 Deque（） ADT。你可以參考前幾章的任何代碼，挑戰(zhàn)一下這個任務(wù)，別忘記寫單元測試呦。當(dāng)然如果沒想出來也沒關(guān)系，后邊我們實(shí)現(xiàn)棧的時候還會用到它，那里我們會實(shí)現(xiàn)這個代碼。

源碼

# -*- coding: utf-8 -*-# NOTE: 從 array_and_list 第一章拷貝的代碼
class Array(object):def __init__(self, size=32):self._size = sizeself._items = [None] * sizedef __getitem__(self, index):return self._items[index]def __setitem__(self, index, value):self._items[index] = valuedef __len__(self):return self._sizedef clear(self, value=None):for i in range(len(self._items)):self._items[i] = valuedef __iter__(self):for item in self._items:yield itemclass FullError(Exception):passclass ArrayQueue(object):def __init__(self, maxsize):self.maxsize = maxsizeself.array = Array(maxsize)self.head = 0self.tail = 0def push(self, value):if len(self) >= self.maxsize:raise FullError('queue full')self.array[self.head % self.maxsize] = valueself.head += 1def pop(self):value = self.array[self.tail % self.maxsize]self.tail += 1return valuedef __len__(self):return self.head - self.taildef test_queue():import pytest    # pip install pytestsize = 5q = ArrayQueue(size)for i in range(size):q.push(i)with pytest.raises(FullError) as excinfo:   # 我們來測試是否真的拋出了異常q.push(size)assert 'full' in str(excinfo.value)assert len(q) == 5assert q.pop() == 0assert q.pop() == 1q.push(5)assert len(q) == 4assert q.pop() == 2assert q.pop() == 3assert q.pop() == 4assert q.pop() == 5assert len(q) == 0

思考題

• 你能用 python 的 deque 來實(shí)現(xiàn) queue ADT 嗎？
• 哪些經(jīng)典算法里用到了隊(duì)列呢？