翻譯: 嚴(yán)北，公眾號：devintest，轉(zhuǎn)載注明出處：http://www.itdecent.cn/p/4ca9b69ade19

class collections.deque([iterable[, maxlen]])

Deque 雙端隊列介紹

初始化時，傳入一個可迭代的數(shù)據(jù)，將返回一個從左到右的新的deque對象(可以理解為使用append()來遍歷并添加數(shù)據(jù)中的元素到隊列右端)。如果沒有指定一個初始值，則生成一個長度為0的deque。

雙端隊列（Deque）是堆棧和隊列的一般化(讀音是“deck”，是“double-end queue”的縮寫)。Deque是線程安全且高效的，從隊列兩端添加（append）或彈出（pop）元素的復(fù)雜度大約僅O(1)。

雖然list對象支持類似的操作，但是list的只是對固定長度的列表做優(yōu)化，在執(zhí)行改變數(shù)據(jù)元素位置和列表長度的操作（如pop(0)彈出第一個元素，insert(0,v)在某個位置插入元素）時，復(fù)雜度達(dá)到O(n)。

如果maxlen沒有指定或為None，那么deque可以增長到任意長度。否則，deque最大長度將限制為maxlen。一旦一個有界長度的deque被填滿，添加新元素時，相應(yīng)數(shù)目的元素就會從相反的一端被丟棄。有界雙端隊列提供了類似于Unix中的tail過濾器的功能。它們對于跟蹤事務(wù)和一些數(shù)據(jù)池也很有用，因為只有最近的活動才是程序關(guān)心的。

Deque 對象支持以下方法：

• append(x)
  將元素 x 添加到隊列右端

• appendleft(x)
  將元素 x 添加到隊列左端

• clear()
  清空隊列，并將隊列長度置0

• copy()
  淺復(fù)制該隊列

Python 3.5 的新特性

• count(x)
  計算隊列中，值等于 x 的個數(shù)

Python 3.2 的新特性

• extend(iterable)
  往隊列右端添加可迭代的元素

• extendleft(iterable)
  往隊列右端添加可迭代的元素。需要注意的是，可迭代的元素集將會以倒序形式體現(xiàn)在最終的隊列中：

>>> import collections
>>> d = collections.deque()  
>>> d.extendleft(range(6))  
>>> d
deque([5, 4, 3, 2, 1, 0])

• index(x[, start[, stop]])
  返回元素 x 在隊列中的坐標(biāo)。如果有 start 和 stop 參數(shù)，則在以 start 和 stop 為起止索引的子隊列中查找該元素 x ，若存在返回元素 x 在完整隊列中的坐標(biāo)。如果元素不在目標(biāo)隊列中，則觸發(fā) ValueError 錯誤

Python 3.5 的新特性

• insert(i, x)
  將元素 x 插入到隊列的 i 位置。
  若插入的位置超過有界雙端隊列長度，則會觸發(fā) IndexError

Python 3.5 的新特性

• pop()
  彈出（移除并返回）隊列最右端的元素。若隊列為空，則觸發(fā)IndexError錯誤

• popleft()
  彈出（移除并返回）隊列最左端的元素。若隊列為空，則觸發(fā)IndexError錯誤

• remove(value)
  移除隊列中第一個出現(xiàn)的值為 value 的元素。若不存在這樣的元素，則觸發(fā)ValueError錯誤

• reverse()
  反轉(zhuǎn)隊列中的元素，并返回None

Python 3.2 的新特性

• rotate(n=1)
  將deque視為首尾相連的隊列，若 n 為正整數(shù)，向右移 n 位。n 默認(rèn)為 1，即當(dāng)不指定 n 值時，默認(rèn)右移 1 位。n 可以取負(fù)值，表示向左移 n 位：

>>> from collections import deque
>>> d = deque(range(6))
>>> d
deque([0, 1, 2, 3, 4, 5])
>>> d.rotate()    # 向右移1位
>>> d
deque([5, 0, 1, 2, 3, 4])
>>> d.rotate(-3)    # 向左移3位
>>> d
deque([2, 3, 4, 5, 0, 1])

當(dāng)隊列不為空時，右移一位相當(dāng)于d.appendleft(d.pop())，而左移一位相當(dāng)于d.append(d.popleft())

Deque對象還提供了一個只讀屬性：

• maxlen
  如果隊列有界，返回隊列最大長度，否則返回None

Python 3.1 的新特性

除了上述的用法，deque同樣支持迭代、持久化，能夠用 len(d), reversed(d), copy.copy(d), copy.deepcopy(d)等方法，也能用 in 運算符操作deque對象中的元素，以及下標(biāo)索引例如d[-1]。對兩端的索引操作復(fù)雜度是O(1)，但是當(dāng)操作中間元素時，復(fù)雜度會上升到O(n)。想要快速隨機訪問隊列中的元素，用list更合適。

從 Python 3.5 開始，deque 支持 __add__() (兩個deque相加)、__mul__() (deque * n 倍)和 __imul__() (deque * n 倍后賦值給自身)。

方法示例：

>>> from collections import deque
>>> d = deque('ghi') # make a new deque with three items
>>> for elem in d: # iterate over the deque's elements
... print(elem.upper())
G
H
I
>>> d.append('j') # add a new entry to the right side
>>> d.appendleft('f') # add a new entry to the left side
>>> d # show the representation of the deque
deque(['f', 'g', 'h', 'i', 'j'])
>>> d.pop() # return and remove the rightmost item
'j'
>>> d.popleft() # return and remove the leftmost item
'f'
>>> list(d) # list the contents of the deque
['g', 'h', 'i']
>>> d[0] # peek at leftmost item
'g'
>>> d[-1] # peek at rightmost item
'i'
>>> list(reversed(d)) # list the contents of a deque in reverse
['i', 'h', 'g']
>>> 'h' in d # search the deque
True
>>> d.extend('jkl') # add multiple elements at once
>>> d
deque(['g', 'h', 'i', 'j', 'k', 'l'])
>>> d.rotate(1) # right rotation
>>> d
deque(['l', 'g', 'h', 'i', 'j', 'k'])
>>> d.rotate(-1) # left rotation
>>> d
deque(['g', 'h', 'i', 'j', 'k', 'l'])
>>> deque(reversed(d)) # make a new deque in reverse order
deque(['l', 'k', 'j', 'i', 'h', 'g'])
>>> d.clear() # empty the deque
>>> d.pop() # cannot pop from an empty deque
Traceback (most recent call last):
    File "<pyshell#6>", line 1, in -toplevel-
        d.pop()
IndexError: pop from an empty deque
>>> d.extendleft('abc') # extendleft() reverses the input order
>>> d
deque(['c', 'b', 'a'])

應(yīng)用場景

本節(jié)介紹幾種deque的具體應(yīng)用。

有界雙端隊列提供了一個類似Unix系統(tǒng)下的tail命令功能：

def tail(filename, n=10):
    'Return the last n lines of a file'
    with open(filename) as f:
        return deque(f, n)

deque的另一種使用場景可以是右進(jìn)左出，用于操作最近添加的幾個元素：

這是一個計算相鄰幾個元素平均值的函數(shù)

def moving_average(iterable, n=3):
    # moving_average([40, 30, 50, 46, 39, 44]) --> 40.0 42.0 45.0 43.0
    # http://en.wikipedia.org/wiki/Moving_average
    it = iter(iterable)
    d = deque(itertools.islice(it, n-1))
    d.appendleft(0)
    s = sum(d)
    for elem in it:
        s += elem - d.popleft()
        d.append(elem)
        yield s / n

deque的rotate()方法提供了一種切片和刪除的方法。舉個例子，使用純Python實現(xiàn)del d[n]功能（將某個位置的元素彈出）依賴于rotate()方法：

def delete_nth(d, n):
    d.rotate(-n)
    d.popleft()
    d.rotate(n)

將需要刪除的第 n 位元素用rotate()移至隊列最左端，然后用popleft()彈出最左端的這個元素，再將剩下的元素移位回去。

再對這個方法進(jìn)行一些小改動，還可以很容易地實現(xiàn)Forth語言中對堆棧的操作方法，例如dup, drop, swap, over, pick, rot, 和 roll。

翻譯自

[1] collections.deque