5.3.1 deque オブジェクト

deque( [iterable])
iterable で与えられるデータから、新しい deque オブジェクトを (append() をつかって) 左→右に初期化し、返します。 iterable が指定されない場合、新しい deque オブジェクトは空になります。

Deque とは、スタックとキューを一般化したものです (この名前は「デック」と 発音され、これは「double-ended queue」の省略形です)。Deque はどちらの側からも append と pop が可能で、スレッドセーフでメモリ効率がよく、どちらの方向からも およそ O(1) のパフォーマンスで実行できます。

list オブジェクトでも同様の操作を実現できますが、これは高速な 固定長の操作に特化されており、内部のデータ表現形式のサイズと位置を 両方変えるような "pop(0)" and "insert(0, v)" などの操作では メモリ移動のために O(n) のコストを必要とします。 バージョン 2.4 で 新たに追加 された仕様です。

Deque オブジェクトは以下のようなメソッドをサポートしています:

append( x)
x を deque の右側につけ加えます。

appendleft( x)
x を deque の左側につけ加えます。

clear( )
Deque からすべての要素を削除し、長さを 0 にします。

extend( iterable)
イテレータ化可能な引数 iterable から得られる要素を deque の右側に 追加し拡張します。

extendleft( iterable)
イテレータ化可能な引数 iterable から得られる要素を deque の左側に 追加し拡張します。注意: 左から追加した結果は、イテレータ引数の 順序とは逆になります。

pop( )
Deque の右側から要素をひとつ削除し、その要素を返します。 要素がひとつも存在しない場合は IndexError を発生させます。

popleft( )
Deque の左側から要素をひとつ削除し、その要素を返します。 要素がひとつも存在しない場合は IndexError を発生させます。

remove( value)
最初に現れる value を削除します。 要素がみつからないない場合は ValueError を発生させます。 バージョン 2.5 で 新たに追加 された仕様です。

rotate( n)
Deque の要素を全体で nステップだけ右にローテートします。 n が負の値の場合は、左にローテートします。Deque を ひとつ右にローテートすることは "d.appendleft(d.pop())" と同じです。

上記の操作のほかにも、deque は次のような操作をサポートしています: イテレータ化、pickle、"len(d)"、"reversed(d)"、 "copy.copy(d)"、 "copy.deepcopy(d)"、 in 演算子による 包含検査、そして "d[-1]" などの添え字による参照。

例:

>>> from collections import deque
>>> d = deque('ghi')                 # 3つの要素からなる新しい deque をつくる。
>>> for elem in d:                   # deque の要素をひとつずつたどる。
...     print elem.upper()	
G
H
I

>>> d.append('j')                    # 新しい要素を右側につけたす。
>>> d.appendleft('f')                # 新しい要素を左側につけたす。
>>> d                                # deque の表現形式。
deque(['f', 'g', 'h', 'i', 'j'])

>>> d.pop()                          # いちばん右側の要素を削除し返す。
'j'
>>> d.popleft()                      # いちばん左側の要素を削除し返す。
'f'
>>> list(d)                          # deque の内容をリストにする。
['g', 'h', 'i']
>>> d[0]                             # いちばん左側の要素をのぞく。
'g'
>>> d[-1]                            # いちばん右側の要素をのぞく。
'i'

>>> list(reversed(d))                # deque の内容を逆順でリストにする。
['i', 'h', 'g']
>>> 'h' in d                         # deque を検索。
True
>>> d.extend('jkl')                  # 複数の要素を一度に追加する。
>>> d
deque(['g', 'h', 'i', 'j', 'k', 'l'])
>>> d.rotate(1)                      # 右ローテート
>>> d
deque(['l', 'g', 'h', 'i', 'j', 'k'])
>>> d.rotate(-1)                     # 左ローテート
>>> d
deque(['g', 'h', 'i', 'j', 'k', 'l'])

>>> deque(reversed(d))               # 新しい deque を逆順でつくる。
deque(['l', 'k', 'j', 'i', 'h', 'g'])
>>> d.clear()                        # deque を空にする。
>>> d.pop()                          # 空の deque からは pop できない。
Traceback (most recent call last):
  File "<pyshell#6>", line 1, in -toplevel-
    d.pop()
IndexError: pop from an empty deque

>>> d.extendleft('abc')              # extendleft() は入力を逆順にする。
>>> d
deque(['c', 'b', 'a'])

ご意見やご指摘をお寄せになりたい方は、 このドキュメントについて... をご覧ください。