スタックと同様に、キューはアイテムを先入れ先出し ( FIFO ）のやり方。キューを使用すると、最後に追加された項目が最初に削除されます。キューの良い例は、最初に来たコンシューマが最初に処理されるリソースのコンシューマのキューです。

キューに関連付けられた操作は次のとおりです。

• エンキュー: 項目をキューに追加します。キューがいっぱいの場合、オーバーフロー状態であると言われます – 時間複雑さ : O(1)
• それに応じて： キューから項目を削除します。項目は、プッシュされたのと同じ順序でポップされます。キューが空の場合、それはアンダーフロー状態であると言われます – 時間複雑さ : O(1)
• フロント： キューから先頭のアイテムを取得 – 時間計算量 : O(1)
• 後方： キューから最後のアイテムを取得 – 時間計算量 : O(1)

Python でキューを実装する

キューを実装するにはさまざまな方法があります パイソン。 この記事では、Python ライブラリのデータ構造とモジュールを使用したキューの実装について説明します。 Python キューは次の方法で実装できます。

• リスト
• コレクション.deque
• 尾.尾

リストを使った実装

List は、キューとして使用できる Python の組み込みデータ構造です。 enqueue() の代わりに それに応じて （） 、 追加() そして ポップ（） 関数が使用されます。ただし、先頭に要素を挿入または削除するには、他のすべての要素を 1 つずつシフトする必要があり、O(n) 時間がかかるため、リストはこの目的では非常に遅くなります。
このコードは、Python リストを使用してキューをシミュレートします。要素を追加してくれる 「あ」 、 「b」 、 そして 「c」 キューに追加してからデキューすると、最後には空のキューが生成されます。出力には、最初のキュー、デキューされた要素が表示されます ( 「あ」 、 「b」 、 「c」 )、キューの空の状態。

Python3

>

>

出力：

Initial queue ['a', 'b', 'c'] Elements dequeued from queue a b c Queue after removing elements []>

Traceback (most recent call last):  File '/home/ef51acf025182ccd69d906e58f17b6de.py', line 25, in   print(queue.pop(0)) IndexError: pop from empty list>

collections.dequeを使用した実装

Python のキューは、コレクション モジュールの deque クラスを使用して実装できます。コンテナの両端からの追加操作とポップ操作をより迅速に行う必要がある場合は、リストよりも Deque の方が優先されます。これは、deque の追加操作とポップ操作の複雑さが O(n) 時間であるリストと比較して O(1) 時間であるためです。 。 enqueue と deque の代わりに、append() 関数と Popleft() 関数が使用されます。
コードでは、deque>からcollections>キューを表すモジュール。追加します 「あ」 、 「b」 、 そして 「c」 キューに追加し、次のようにデキューします。 q.popleft()> 、空のキューが生成されます。コメントを解除する q.popleft()> キューが空になると、IndexError>。このコードはキュー操作を示し、空のキューのシナリオを処理します。

Python3

>

>

出力：

アルファ ベータ プルーニングの例

Initial queue deque(['a', 'b', 'c']) Elements dequeued from the queue a b c Queue after removing elements deque([])>

Traceback (most recent call last):  File '/home/b2fa8ce438c2a9f82d6c3e5da587490f.py', line 23, in   q.popleft() IndexError: pop from an empty deque>

queue.Queueを使用した実装

Queue は、キューを実装するために使用される Python の組み込みモジュールです。 queue.Queue(maxsize) は、変数を最大サイズ maxsize に初期化します。 maxsize がゼロの「0」は、無限キューを意味します。このキューは FIFO ルールに従います。
このモジュールではさまざまな機能が使用できます。

• 最大サイズ – キュー内で許可される項目の数。
• 空の（） – キューが空の場合は True を返し、それ以外の場合は False を返します。
• 満杯（） – キュー内に maxsize 項目がある場合は True を返します。キューが maxsize=0 (デフォルト) で初期化された場合、full() は True を返しません。
• 得る（） – キューからアイテムを削除して返します。キューが空の場合は、アイテムが使用可能になるまで待ちます。
• get_nowait() – すぐに利用できる場合は項目を返し、それ以外の場合は QueueEmpty を発生させます。
• 置く(アイテム) – アイテムをキューに入れます。キューがいっぱいの場合は、空きスロットが利用可能になるまで待ってから項目を追加します。
• put_nowait(アイテム) – ブロックせずにアイテムをキューに入れます。すぐに使用できる空きスロットがない場合は、QueueFull を上げます。
• qsize() – キュー内の項目の数を返します。

例： このコードでは、Queue>からのクラスqueue>モジュール。空のキューから始まり、「」で埋められます。 あ、 「b」 、 そして 「c」 。デキュー後、キューは空になり、「1」が追加されます。最大サイズが 3 に設定されているため、以前は空でしたが、満杯のままです。このコードは、満杯と空のチェックを含むキューの操作を示しています。

Python3

>

>

出力：

0 Full: True Elements dequeued from the queue a b c Empty: True Empty: False Full: False>