Pythonのキュー（Queue）とは？FIFOの仕組みと3つの実装方法を例付きで解説

キュー（Queue）は、先入れ先出し（First In First Out：FIFO）の仕組みで動作する線形データ構造です。最初に追加された要素が、最初に処理されます。

身近な例で理解する

キューの動作は、バス停の行列にたとえると分かりやすくなります。バス停に最初に到着した人が列の先頭に立ち、その後に来た人々は順番に後ろへ並んでいきます。バスが到着すると、最初に並んだ人から順に乗車し、以降も到着順に乗っていきます。このように「先に入ったものが先に出る」というFIFOの仕組みが、まさにキューの動作そのものです。

Pythonにおけるキューの実装方法

Pythonでは、リストなどの基本的なデータ構造や標準ライブラリの組み込みモジュールを使って、複数の方法でキューを実装できます。

方法1：リストを使った実装

Pythonのリストを使えば手軽にキューを実装できますが、効率はあまり良くありません。リストの先頭への挿入や削除にはO(n)の時間がかかるため、他の方法と比べて処理速度が遅くなります。

主な操作

append() … キューの末尾に要素を追加します。

pop(0) … キューの先頭の要素を取り出して返します。

コード例

queue=[]
queue.append(1)
queue.append(2)
queue.append(3)
print("初期のキュー",queue)
print("取り出した要素")
print(queue.pop(0))
print(queue.pop(0))
print("要素を取り出した後のキュー",queue)

実行結果

初期のキュー [1, 2, 3]
取り出した要素
1
2
要素を取り出した後のキュー [3]

空になったキューからさらに要素を取り出そうとすると、例外が発生します。

queue.pop(0)
IndexError: pop from empty list

方法2：queue.Queueモジュールを使った実装

Pythonの標準ライブラリに含まれるqueueモジュールを使う方法です。from queue import Queueとしてインポートし、キューを生成する際に最大サイズを指定できます。サイズに0を指定すると、無制限のキューになります。

主な操作

maxsize … キューに格納できる最大要素数

get() … 先頭の要素を取り出して返します。キューが空の場合は、要素が入るまで待機します。

get_nowait() … 先頭の要素を取り出して返します。キューが空の場合は例外を発生させます。

put(item) … キューの末尾に要素を追加します。キューが満杯の場合は、空きが出るまで待機します。

put_nowait(item) … キューの末尾に要素を追加します。キューが満杯の場合は例外を発生させます。

full() … キューが満杯ならTrue、そうでなければFalseを返します。

empty() … キューが空ならTrue、そうでなければFalseを返します。

qsize() … 現在キューにある要素数を返します。

コード例

from queue import Queue
q=Queue(maxsize=3)
q.put(1)
q.put(2)
q.put(3)
print("キューは満杯か",q.full())
print("取り出した要素")
print(q.get())
print(q.get())
print("キュー内の要素数",q.qsize())
print("キューは空か",q.empty())

実行結果

キューは満杯か True
取り出した要素
1
2
キュー内の要素数 1
キューは空か False

方法3：collections.dequeを使った実装

もうひとつの効率的な方法が、collectionsモジュールのdeque（デック）を使う実装です。from collections import dequeとしてインポートします。

主な操作

append() … キューの末尾に要素を追加します。

popleft() … キューの先頭の要素を取り出して返します。O(1)の時間計算量で高速に処理できます。

コード例

from collections import deque
queue=deque()
queue.append(1)
queue.append(2)
queue.append(3)
print("初期のキュー：",queue)
print("取り出した要素")
print(queue.popleft())
print(queue.popleft())
print("要素を取り出した後のキュー：",queue)

実行結果

初期のキュー： deque([1, 2, 3])
取り出した要素
1
2
要素を取り出した後のキュー： deque([3])

なお、空のdequeに対してpopleft()を呼び出すと例外が発生するため、注意が必要です。