今回は、Queueデータ構造のインタフェースであるPython Queueモジュールについて見ていきましょう。
Python Queue
キューは、最初に挿入される要素が最初にポップされるデータ構造です。
現実の待ち行列と同じで、最初に並んだものが最初に出てくるということです。
Pythonでは、オブジェクトのキューを作成するために queue モジュールを使用することができます。
これは Python の標準ライブラリの一部なので、 pip を使用する必要はありません。
このモジュールをインポートするには
import queue
|
Queue オブジェクトを作成するには、次のようにしてインスタンスを作成します。
q = queue.Queue()
|
デフォルトでは、このオブジェクトの容量は 0 ですが、もし、明示的に指定したい場合は
q = queue.Queue(max_capacity)
|
Queue.get() メソッドと Queue.put() メソッド
Queue.get()とqueue.put()` メソッドを使うと、Queue に値を挿入したり、値を取得したりすることができます。
それでは、キューを作成して、1から5までの数字を挿入してみましょう。
import queue
# Instantiate the Queue objectq = queue.Queue()
# Insert elements 1 to 5 in the queuefor i in range(1, 6):
q.put(i)
print('Now, q.qsize() =', q.qsize())
# Now, the queue looks like this:# (First) 1 <- 2 <- 3 <- 4 <- 5for i in range(q.qsize()):
print(q.get())
|
結果は以下の通りです。
Now, q.qsize() = 5
12345 |
見ての通り、出力では最初のインデックスが確かに1なので、これがQueueのトップです。
残りの要素も同じようにそれに続く。
Pythonのキューを空にする
キューオブジェクトを空にするには、 q.empty() を使用します。
これはサイズを 0 に設定し、キューを空にします。
import queue
# Instantiate the Queue objectq = queue.Queue()
# Insert elements 1 to 5 in the queuefor i in range(1, 6):
q.put(i)
print('Now, q.qsize() =', q.qsize())
# Empty queueq.empty()print('After emptying, size =', q.qsize())
for i in range(q.qsize()):
print(q.get())
|
結果は以下の通りです。
Now, q.qsize() = 5
After emptying, size = 0
|
ほとんどの典型的なキューの実装では、 pop (または dequeue) オペレーションがありますが、 queue モジュールはこのためのメソッドを持っていません。
したがって、キューから要素をポップしたい場合は、別のキュークラスを使用する必要があります。
簡単な解決策は、Pythonのリストを使うことです。
挿入は最後に行われるので、 list.append(value) を使ってキューに要素を挿入し、最初の要素が削除されるので、 list.pop(0) を使って要素を削除します。
class MyQueue():
# Using Python Lists as a Queue
def __init__(self):
self.queue = []
def enqueue(self, value):
# Inserting to the end of the queue
self.queue.append(value)
def dequeue(self):
# Remove the furthest element from the top,
# since the Queue is a FIFO structure
return self.queue.pop(0)
my_q = MyQueue()
my_q.enqueue(2)
my_q.enqueue(5)
my_q.enqueue(7)
for i in my_q.queue:
print(i)
print('Popped,', my_q.dequeue())
for i in my_q.queue:
print(i)
|
結果は以下の通りです。
257Popped, 2
57 |
これで dequeue 操作を持つ独自のキュークラスが書けました! では、他のタイプのキューを使用するために、他のモジュールをどのように使用できるかを紹介します。
Pythonで作る優先度待ち行列
優先度キューは、アイテムの優先度に基づいてキューに追加するタイプのキューで、通常整数値です。
優先順位が低い番号の項目はより高い優先順位を与えられ、キューの先頭に置かれ、他の項目は後ろに置かれます。
queue` モジュールは優先度キュー構造もサポートしているので、それをどのように使うか見てみましょう。
import queue
priority_q = queue.PriorityQueue()
priority_q.put((1, 'Hello'))
priority_q.put((3, 'Python'))
priority_q.put((2, 'from'))
for i in range(priority_q.qsize()):
print(priority_q.get())
|
結果は以下の通りです。
(1, 'Hello')
(2, 'from')
(3, 'Python')
|
見てわかるように、要素は優先順位に基づいて挿入されます。
Python heapq Queue
優先キューを実装するために heapq モジュールを使用することもできます。
>>> import heapq
>>> q = []
>>> heapq.heappush(q, (1, 'hi'))
>>> q[(1, 'hi')]
>>> heapq.heappush(q, (3, 'Python'))
>>> q[(1, 'hi'), (3, 'Python')]
>>> heapq.heappush(q, (2, 'from'))
>>> q[(1, 'hi'), (3, 'Python'), (2, 'from')]
>>> heapq.heappop(q)(1, 'hi')
>>> heapq.heappop(q)(2, 'from')
>>> heapq.heappop(q)(3, 'Python')
>>> heapq.heappop(q)Traceback (most recent call last): File "<stdin>", line 1, in <module>
IndexError: index out of range
|
つまり、優先キューを作成し、それが空になるまでそこからポッピングしているのです。
同じことは、以下のプログラムでも実現できます。
import heapq
q = []
heapq.heappush(q, (2, 'from'))
heapq.heappush(q, (1, 'Hello'))
heapq.heappush(q, (3, 'Python'))
while q:
# Keep popping until the queue is empty
item = heapq.heappop(q)
print(item)
|
結果は以下の通りです。
(1, 'Hello')
(2, 'from')
(3, 'Python')
|
まとめ
この記事では、Pythonで様々なQueueを実装して使用する方法について学びました。