home changes contents help options

127:スタックやキューを使う

両端キュー (deque, double-ended queue) にて

リスト型を用いてもスタックやキューとしての動作をさせることは可能ですが、 各データ型には得意苦手があります。この用途で酷使する場合リストを用いるのは得策ではありません。 とくに先端への追加、取り出しを行ったときのデータ再配列コストが問題です。

collections モジュールの deque のほうが適任です。 要素列の左への追加・削除、右への追加・削除をともに得意としています。 ちなみに Python のデキューは添え字によるランダムアクセス風の操作にも対応していますが、こちらは苦手としています。

   >>> stack = collections.deque() # スタック
   >>> stack.append('a')           # 追加: append を使用、右に追加
   >>> stack.append('b')
   >>> stack.append('c')
   >>> stack
   deque(['a', 'b', 'c'])
   >>> stack.pop()                 # 取得: pop を使用、右から取り出し
   'c'
   >>> stack.pop()
   'b'
   >>> stack.pop()
   'a'
   >>> stack.pop()
   Traceback (most recent call last):
     File "<stdin>", line 1, in <module>
   IndexError: pop from an empty deque
   >>>
   >>> queue = collections.deque() # キュー
   >>> queue.append('a')           # 追加 append を使用、右に追加
   >>> queue.append('b')
   >>> queue.append('c')
   >>> queue
   deque(['a', 'b', 'c'])
   >>> queue.popleft()             # 取得 popleft を使用、左から取り出し
   'a'
   >>> queue.popleft()
   'b'
   >>> queue.popleft()
   'c'
   >>> queue.popleft()
   Traceback (most recent call last):
     File "<stdin>", line 1, in <module>
   IndexError: pop from an empty deque

追加、取り出しの方向をそろえるとスタックに、 違えるとキューとして使えます。

deque([iterable]?)
デキューを作成します。引数にイテレータ化可能な型(リストなど)を与えるとその要素で初期化されます。
append(x)
x を右から追加します。
appendleft(x)
x を左から追加します。
pop()
右から要素を取り出します。要素がひとつもないと IndexError? となります。
popleft()
左から要素を取り出します。要素がひとつもないと IndexError? となります。

deque には以下のメソッドもあります。

clear()
デキューを空にします。
extend(iterable)
イテレータ化可能な型(リストなど)の要素すべてを順に右から追加します。
extendleft(iterable)
イテレータ化可能な型(リストなど)の要素すべてを順に左から追加します。
rotate(n)
要素を右へ n 個分ローテートします。負の値の指定も可能で、この場合左ローテートします。

deque はリストと同じような操作をいくつかサポートしています。

リスト にて

リスト型のメソッド2種を使うことで、リストをスタックやキューとして使うことができます。 パフォーマンスの問題がありますので酷使する場合は collections.deque を使うことを薦めます。

   >>> stack = []         # スタック
   >>> stack.append('a')  # 追加: append(x) を使用。引数 x が追加される。
   >>> stack.append('b')
   >>> stack.append('c')
   >>> stack.pop()        # 取得: pop() を使用。引数無し、もしくは -1 で呼ぶ。
   'c'
   >>> stack.pop()
   'b'
   >>> stack.pop()
   'a'
   >>> stack.pop()
   Traceback (most recent call last):
     File "<stdin>", line 1, in <module>
   IndexError: pop from empty list
   >>>
   >>> queue = []        # キュー
   >>> queue.append('a') # 追加: append(x) を使用。引数 x が追加される。
   >>> queue.append('b')
   >>> queue.append('c')
   >>> queue.pop(0)      # 取得: pop(0) を使用。引数 0 で呼ぶ。。
   'a'
   >>> queue.pop(0)
   'b'
   >>> queue.pop(0)
   'c'
   >>> queue.pop(0)
   Traceback (most recent call last):
     File "<stdin>", line 1, in <module>
   IndexError: pop from empty list
append(x)
リストの末尾に x を追加します
pop([i]?)
リストの i 番目を取り出します。省略時は -1 を指定したものとみなされ末尾を取り出します。 i 番目に該当する要素がないと IndexError? を送出します。