キューとスタック

【Pythonデータ構造】キューとスタック

キュー（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'])