キューとスタック
キュー (queue) と スタック (stack) はコンピュータにおける最も基本的なデータ構造です。どちらも一列に並んだデータですが、取り出し方が異なります。
キューの構造は FIFO (First In First Out : 先入れ先出し) とよばれ、下の概念図にあるように、格納順にデータを取り出せる仕組みになっています (一番古いデータから順に取り出します)。
一方、スタックはキューとは逆に新しいデータから先に取り出します。この仕組みを LIFO (Last In First Out : 後入れ先出し) とよびます (下図参照)。
Python には queue モジュールにキューとスタックが、それぞれ queue.Queue, queue.LifoQueue というクラス名で用意されています。
queue.Queue()
queue.Queue() は FIFO (First in First out) キューオブジェクトのコンストラクタです。試しにキューを作成して、put() メソッドでデータを格納してみます。
# PYTHON_QUEUE
# In[1]
# queueモジュールをインポート
import queue
# キューを作成
q = queue.Queue()
# データを用意
data = ["red", "blue", "green"]
# キューにデータを格納する
for i in data:
q.put(i)コンストラクタに引数 maxsize を指定していないので、要素の格納数に上限はありません。キューが満杯であるときに True を返す Queue.full() メソッドを使って確認してみましょう。
# In[2]
# キューが満杯になっていることを確認
print(q.full())False
Queue.qsize() でキューのサイズ (要素数) を取得できます。
# In[3]
# キューのサイズを取得
print(q.qsize())3
今度はキューが空になるまで要素を取り出してみます。
# In[4]
# キューが空になるまで要素を取り出す
while not q.empty():
print(q.get())red blue green
キューに入れた順に要素が取り出されています。
さらに要素を取り出そうとすると、Empty エラーを送出します。
# In[5]
# さらに要素を取り出す
print(q.get(block=False))Empty:
block 引数が True になっていると、要素が取り出せるようになるまで (新しい要素が追加されるまで) 待機を続けます。空のキューからデータを取り出すことを試みた場合に、即座にエラーを送出したいならば block に False を渡してください。timeout でエラーを送出するまでの時間を指定することもできます。
# In[6]
# 5秒以内に要素を取り出せなければEmptyエラーを送出
print(q.get(timeout=5))Empty:
queue.empty() でキューが空になっていることを確認できます。
# In[7]
# キューが空になっていることを確認
print(q.empty())True
次は maxsize=3 を指定して、格納上限数 3 のキューを生成して、10 個の要素を詰め込むことを試みます。
# In[8]
# 格納上限数3のキューを作成
q = queue.Queue(3)
# キューにデータを格納する
for i in range(10):
q.put(i, block=False)Full:
上限数を超えた段階で満杯であることを示す Full エラーが送出されました。queue.full() で上限まで詰め込まれていることを確認してみます。
# In[9]
# キューが満杯であることを確認
print(q.full())True
キューの要素をすべて取り出してみます。
# In[10]
# キューが空になるまで要素を取り出す
while not q.empty():
print(q.get())0 1 2
queue.LifoQueue()
queue.LifoQueue() は LIFO (Last In First Out) のキュー、すなわちスタックのコンストラクタです。一番最後に格納された要素から順に取り出すことができます。
# PYTHON_LIFOQUEUE
# In[1]
import queue
# LIFOキュー(スタック)を作成
s = queue.LifoQueue()
# データを用意
data = ["red", "blue", "green"]
# キューにデータを格納する
for i in data:
s.put(i)
# キューが空になるまで要素を取り出す
while not s.empty():
print(s.get())green blue red
queue.Queue() と同様に、引数 maxsize で格納できるデータの上限数を設定できます。備えるメソッドも queue.LifoQueue オブジェクトと同じです。
queue.PriorityQueue()
queue.PriorityQueue() は優先順位付きキューを生成します。データを格納するたびに、キューの内部が昇順ソートされます。たとえば、数値を格納すると、put() メソッドで小さい順に取り出せます。
# PYTHON_PRIORITYQUEUE
# In[1]
import queue
# 優先順位付きキューを生成
p = queue.PriorityQueue()
# データを用意
numbers = [5, 3, 7, 1, 4]
# キューにデータを格納
for i in numbers:
p.put(i)
# キューが空になるまで要素を取り出す
while not p.empty():
print(p.get(), end=" ")1 3 4 5 7
引数 maxsize で格納するデータの上限数を設定できます。備えるメソッドは queue.LifoQueue オブジェクトと同じです。
collections.deque()
collections モジュールには deque (デック) とよばれる特殊なキューが用意されています。deque は double-ended queue の省略形で、その名の通り、双方向から追加・削除が可能であることを意味しています。
ほぼ list と同じ機能を備えるコンテナですが、list が追加や削除に O(n) のコストを要するのに対し、deque は O(1) のコストで処理できます。
deque.append() はアイテムを右側 (後ろ) から追加します。
# PYTHON_DEQUE
# In[1]
import collections
q = collections.deque()
# デックに0～2の数字を右側から追加
for i in range(3):
q.append(i)
# デックの中身を表示
print(q)deque([0, 1, 2])
左側 (先頭) に追加するときは、deque.leftappend() を使います。
# In[2]
# デックに左側から文字列"a"を追加
q.appendleft("a")
print(q)deque(['a', 0, 1, 2])
deque.insert() は任意の位置にアイテムを追加します。
# In[3]
# インデックス3の位置に"b"を追加
q.insert(3, "b")
print(q)deque(['a', 0, 1, 'b', 2])
deque.pop() は右側からアイテムを取り出します。
# In[4]
# 右側から要素を1つ取り出す
print(q.pop())
print(q)2 deque(['a', 0, 1, 'b'])
deque.popleft() は左側からアイテムを取り出します。
# In[5]
# 左側から要素を1つ取り出す
print(q.popleft())
print(q)a deque([0, 1, 'b'])
deque はリストなどのイテラブルからデータをまとめて引き継ぐこともできます。
# In[6]
# リストを定義
list_1 = ["a", "b", "c"]
# リストの要素をキューに格納する
q = collections.deque(list_1)
# キューの中身を表示
print(q)deque(['a', 'b', 'c'])
deque.extend() は右側からイテラブルを付け加えます。
# In[7]
# リストを定義
list_2 = [0, 1]
# キューの右側にリストを付け加える
q.extend(list_2)
# キューの中身を表示
print(q)deque(['a', 'b', 'c', 0, 1])
deque.leftextend() は左側からイテラブルを付け加えます。
# In[8]
# リストを定義
list_3 = [2, 3]
# キューの左側にリストを付け加える
q.extendleft(list_3)
# キューの中身を表示
print(q)deque([3, 2, 'a', 'b', 'c', 0, 1])
deque.rotate(n) はアイテムを右に n 個ずらします。
# In[9]
# キューの要素を右に3個ずらす
q.rotate(3)
print(q)deque(['c', 0, 1, 3, 2, 'a', 'b'])