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 はリストと同じような操作をいくつかサポートしています。
- len の引数に与えるとリスト同様に現在の長さを得ることができます。
- イテレータ化可能のため for 文で要素のすべてにアクセスできます。
- for 文と reversed の併用で逆順にすべてアクセスできます。
- in 演算子が適用可能です。 "a" in d でデキュー d に文字列 "a" が含まれているか確認できます。
- d[1]? のような添え字によるアクセスが可能です。
リスト にて
リスト型のメソッド２種を使うことで、リストをスタックやキューとして使うことができます。 パフォーマンスの問題がありますので酷使する場合は 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? を送出します。