キューとスタック

キューとスタック

キューとスタック

 キュー (queue)スタック (stack) はコンピュータにおける最も基本的なデータ構造です。どちらも一列に並んだデータですが、取り出し方が異なります。

 キューの構造は FIFO (First In First Out : 先入れ先出し) とよばれ、下の概念図にあるように、格納順にデータを取り出せる仕組みになっています (一番古いデータから順に取り出します)。

キュー (queue) の構造:FIFO

 一方、スタックはキューとは逆に新しいデータから先に取り出します。この仕組みを LIFO (Last In First Out : 後入れ先出し) とよびます (下図参照)。

スタック (stack) の構造:LIFO

アルゴリズム図鑑 絵で見てわかる26のアルゴリズム

中古価格
¥2,011から
(2019/7/30 20:26時点)

queueモジュール

 Python では queue モジュールにキューとスタックが、それぞれ queue.Queue, queue.LifoQueue というクラス名で用意されています。

queue.Queue()

 queue.Queue() は FIFO (First in First out) キューオブジェクトのコンストラクタです。試しにキューを作成して、put() メソッドでデータを格納してみます。

# PYTHON_QUEUE-1

# queueモジュールをインポート
import queue

# キューを作成
q = queue.Queue()

# データを用意
data = ["red", "blue", "green"]

# キューにデータを格納する
for i in data:
    q.put(i)

 コンストラクタに引数 maxsize を指定していないので、要素の格納数に上限はありません。キューが満杯であるときに True を返す Queue.full() メソッドを使って確認してみましょう。

# PYTHON_QUEUE-2

# キューが満杯になっていることを確認
print(q.full())
False

 Queue.qsize() でキューのサイズ (要素数) を取得できます。

# PYTHON_QUEUE-3

# キューのサイズを取得
print(q.qsize())
3

 今度はキューが空になるまで要素を取り出してみます。

# PYTHON_QUEUE-4

# キューが空になるまで要素を取り出す
while not q.empty():
    print(q.get())
red
blue
green

 キューに入れた順に要素が取り出されています。
 さらに要素を取り出そうとすると、Empty エラーを送出します。

# PYTHON_QUEUE-5

# さらに要素を取り出す
print(q.get(block=False))
Empty:

 block 引数が True になっていると、要素が取り出せるようになるまで (新しい要素が追加されるまで) 待機を続けます。空のキューからデータを取り出すことを試みた場合に、即座にエラーを送出したいならば block に False を渡してください。timeout でエラーを送出するまでの時間を指定することもできます。

# PYTHON_QUEUE-6

# 5秒以内に要素を取り出せなければEmptyエラーを送出
print(q.get(timeout=5))
Empty:

 queue.empty() でキューが空になっていることを確認できます。

# PYTHON_QUEUE-7

# キューが空になっていることを確認
print(q.empty())
True

 次は maxsize=3 を指定して、格納上限数 3 のキューを生成して、10 個の要素を詰め込むことを試みます。

# PYTHON_QUEUE-8

# 格納上限数3のキューを作成
q = queue.Queue(3)

# キューにデータを格納する
for i in range(10):
    q.put(i, block=False)
Full:

 上限数を超えた段階で満杯であることを示す Full エラーが送出されました。queue.full() で上限まで詰め込まれていることを確認してみます。

# PYTHON_QUEUE-9

# キューが満杯であることを確認
print(q.full())
True

 キューの要素をすべて取り出してみます。

# PYTHON_QUEUE-10

# キューが空になるまで要素を取り出す
while not q.empty():
    print(q.get())
0
1
2

 

queue.LifoQueue()

 queue.LifoQueue() は LIFO (Last In First Out) のキュー、すなわちスタックのコンストラクタです。一番最後に格納された要素から順に取り出すことができます。

# PYTHON_LIFOQUEUE

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

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-1

import collections

q = collections.deque()

# デックに0~2の数字を右側から追加
for i in range(3):
    q.append(i)

# デックの中身を表示
print(q)
deque([0, 1, 2])

 左側 (先頭) に追加するときは、deque.leftappend() を使います。

# PYTHON_DEQUE-2

# デックに左側から文字列"a"を追加
q.appendleft("a")

print(q)
deque(['a', 0, 1, 2])

 deque.insert() は任意の位置にアイテムを追加します。

# PYTHON_DEQUE-3

# インデックス3の位置に"b"を追加
q.insert(3, "b")

print(q)
deque(['a', 0, 1, 'b', 2])

 deque.pop() は右側からアイテムを取り出します。

# PYTHON_DEQUE-4

# 右側から要素を1つ取り出す
print(q.pop())

print(q)
2
deque(['a', 0, 1, 'b'])

 deque.popleft() は左側からアイテムを取り出します。

# PYTHON_DEQUE-5

# 左側から要素を1つ取り出す
print(q.popleft())

print(q)
a
deque([0, 1, 'b'])

 deque はリストなどのイテラブルからデータをまとめて引き継ぐこともできます。

# PYTHON_DEQUE-6

# リストを定義
list_1 = ["a", "b", "c"]

# リストの要素をキューに格納する
q = collections.deque(list_1)

# キューの中身を表示
print(q)
deque(['a', 'b', 'c'])

 deque.extend() は右側からイテラブルを付け加えます。

# PYTHON_DEQUE-7

# リストを定義
list_2 = [0, 1]

# キューの右側にリストを付け加える
q.extend(list_2)

# キューの中身を表示
print(q)
deque(['a', 'b', 'c', 0, 1])

 deque.leftextend() は左側からイテラブルを付け加えます。

# PYTHON_DEQUE-8

# リストを定義
list_3 = [2, 3]

# キューの左側にリストを付け加える
q.extendleft(list_3)

# キューの中身を表示
print(q)
deque([3, 2, 'a', 'b', 'c', 0, 1])

 deque.rotate(n) はアイテムを右に n 個ずらします。

# PYTHON_DEQUE-9

# キューの要素を右に3個ずらす
q.rotate(3)

print(q)
deque(['c', 0, 1, 3, 2, 'a', 'b'])