Python キュー:FIFO、LIFO の例

Python キューとは?

キューは、データを保持するコンテナーです。最初に入力されたデータが最初に削除されるため、キューは「先入れ先出し (FIFO)」とも呼ばれます。キューには前後に 2 つの端があります。項目は背面から入力され、前面から削除されます。

この Python チュートリアルでは、次のことを学びます:

Python Queue とは?
Python Queue はどのように機能しますか?
Python のキューの種類
Python キューのインストール
Queue および LifoQueue クラス内で使用可能なメソッド
先入れ先出しキューの例
後入れ先出しキューの例
キューに複数のアイテムを追加する
並べ替えキュー
リバースキュー

Python キューはどのように機能しますか?

キューは、実際の例と簡単に比較できます。たとえば、チケットカウンターの列に並んでいる人の列では、最初に立っている人が最初にチケットを受け取り、次に次の人が続きます。キューのデータ構造にも同じロジックが適用されます。

キューの図式表現は次のとおりです:

後部アイテムがキュー内に挿入されるポイントを表します。この例では、7 がその値です。

フロント キューからアイテムが削除されるポイントを表します。キューからアイテムを削除すると、図に示すように、取得する最初の要素は 1 になります。

アイテム 1 はキューに最初に挿入されたものであり、それを削除している間、最初に出てくるものです。したがって、キューは FIRST IN FIRST OUT (FIFO) と呼ばれます

キュー内のアイテムは順番に削除され、途中から削除することはできません。アイテム 5 をキューからランダムに削除することはできません。そのためには、5 より前のすべてのアイテムを削除する必要があります。キュー内のアイテムは、挿入された順序で削除されます。

Python のキューの種類

Python には主に 2 種類のキューがあります:

先入れ先出しキュー:このため、最初に移動した要素が最初に出てきます。
FIFO を使用するには、 Queue() を呼び出す必要がありますキューモジュールからのクラス。
後入れ先出しキュー:ここでは、最後に入力された要素が最初に出てきます。
LIFO を使用するには、 LifoQueue() を呼び出す必要がありますキューモジュールからのクラス。

Python キューのインストール

Python でキューを操作するのは非常に簡単です。コードでキューを利用するための手順は次のとおりです。

ステップ 1) 以下に示すように、キューモジュールをインポートするだけです。

import queue

モジュールは Python でデフォルトで利用可能であり、キューの使用を開始するために追加のインストールは必要ありません。キュー FIFO (先入れ先出し) と LIFO (後入れ先出し) の 2 種類があります。

ステップ 2) FIFO キューを操作するには、次に示すようにインポートされた queue モジュールを使用して Queue クラスを呼び出します。

import queue
q1 = queue.Queue()

ステップ 3) LIFO キューを操作するには、以下に示すように LifoQueue() クラスを呼び出します。

import queue
q1 = queue.LifoQueue()

Queue および LifoQueue クラス内で使用可能なメソッド

以下は、Queue および LifoQueue クラス内で使用できる重要なメソッドです:

put(項目): これにより、アイテムがキューに入れられます。
get(): これにより、キューからアイテムが返されます。
空(): キューが空の場合は true を返し、アイテムが存在する場合は false を返します。
qsize(): キューのサイズを返します。
full(): キューがいっぱいの場合は true、そうでない場合は false を返します。

先入れ先出しキューの例

先入れ先出しの場合、先に行った要素が先に出てきます。

アイテムをキューに追加

キューにアイテムを追加する例に取り組みましょう。キューの操作を開始するには、以下の例に示すように、まずモジュールキューをインポートします。

アイテムを追加するには、例に示すように put() メソッドを使用できます:

import queue
q1 = queue.Queue()
q1.put(10) #this will additem 10 to the queue.

デフォルトでは、キューのサイズは無限であり、アイテムをいくつでも追加できます。キューのサイズを定義したい場合は、次のように同じことができます

import queue
q1 = queue.Queue(5) #The max size is 5.
q1.put(1)
q1.put(2)
q1.put(3)
q1.put(4)
q1.put(5)
print(q1.full()) # will return true.

出力:

True

現在、キューのサイズは 5 であり、5 つ以上のアイテムを必要とせず、メソッド q1.full() は true を返します。これ以上アイテムを追加しても、コードはそれ以上実行されません。

キューからアイテムを削除する

キューから項目を削除するには、get() というメソッドを使用できます。このメソッドは、呼び出されたときにキューからアイテムを許可します。

次の例は、アイテムをキューから削除する方法を示しています。

import queue
q1 = queue.Queue()
q1.put(10)

item1 = q1.get()

print('The item removed from the queue is ', item1)

出力:

The item removed from the queue is  10

後入れ先出しキューの例

先出しキューの最後の場合、最後に入力された要素が最初に出てきます。

LIFO、つまり先出しキューの最後を操作するには、キューモジュールをインポートして LifoQueue() メソッドを使用する必要があります。

アイテムをキューに追加

ここでは、アイテムを LIFO キューに追加する方法を理解します。

import queue
q1 = queue.LifoQueue()
q1.put(10)

上記の例に示すように、LifoQueue で put() メソッドを使用する必要があります。

キューからアイテムを削除する

LIFOqueue からアイテムを削除するには、get() メソッドを使用できます。

import queue
q1 = queue.LifoQueue()
q1.put(10)

item1 = q1.get()

print('The item removed from the LIFO queue is ', item1)

出力:

The item removed from the LIFO queue is  10

キューに複数のアイテムを追加する

上記の例では、FIFO と LIFOqueue に対して単一のアイテムを追加し、アイテムを削除する方法を見てきました。次に、複数のアイテムを追加して削除する方法を見ていきます。

FIFOqueue に項目を追加して

import queue
q1 = queue.Queue()

for i in range(20):
    q1.put(i) # this will additem from 0 to 20 to the queue

FIFOqueue からアイテムを削除

import queue
q1 = queue.Queue()

for i in range(20):
    q1.put(i) # this will additem from 0 to 20 to the queue

while not q1.empty():
print("The value is ", q1.get()) # get() will remove the item from the queue.

出力:

The value is  0
The value is  1
The value is  2
The value is  3
The value is  4
The value is  5
The value is  6
The value is  7
The value is  8
The value is  9
The value is  10
The value is  11
The value is  12
The value is  13
The value is  14
The value is  15
The value is  16
The value is  17
The value is  18
The value is  19

LIFOqueue にアイテムを追加

import queue
q1 = queue.LifoQueue()
for i in range(20):
    q1.put(i) # this will additem from 0 to 20 to the queue

LIFOqueue からアイテムを削除する

import queue
q1 = queue.LifoQueue()

for i in range(20):
    q1.put(i) # this will additem from 0 to 20 to the queue


while not q1.empty():
print("The value is ", q1.get()) # get() will remove the item from the queue.

出力:

The value is  19
The value is  18
The value is  17
The value is  16
The value is  15
The value is  14
The value is  13
The value is  12
The value is  11
The value is  10
The value is  9
The value is  8
The value is  7
The value is  6
The value is  5
The value is  4
The value is  3
The value is  2
The value is  1
The value is  0

並べ替えキュー

次の例は、キューの並べ替えを示しています。並べ替えに使用されるアルゴリズムはバブルソートです。

import queue
q1 = queue.Queue()
#Addingitems to the queue
q1.put(11)
q1.put(5)
q1.put(4)
q1.put(21)
q1.put(3)
q1.put(10)

#using bubble sort on the queue
n =  q1.qsize()
for i in range(n):
    x = q1.get() # the element is removed
    for j in range(n-1):
        y = q1.get() # the element is removed
        if x > y :  
            q1.put(y)   #the smaller one is put at the start of the queue
        else:
            q1.put(x)  # the smaller one is put at the start of the queue
            x = y     # the greater one is replaced with x and compared again with nextelement
    q1.put(x)

while (q1.empty() == False): 
print(q1.queue[0], end = " ")  
        q1.get()

出力:

3 4 5 10 11 21

リバースキュー

キューを逆にするために、別のキューと再帰を利用できます。

次の例は、キューを逆にする方法を示しています。

例:

import queue
q1 = queue.Queue()

q1.put(11)
q1.put(5)
q1.put(4)
q1.put(21)
q1.put(3)
q1.put(10)

def reverseQueue (q1src, q2dest) :  
    buffer = q1src.get()
    if (q1src.empty() == False) :
reverseQueue(q1src, q2dest)      #using recursion
    q2dest.put(buffer)
return q2dest

q2dest = queue.Queue()
qReversed = reverseQueue(q1,q2dest)

while (qReversed.empty() == False): 
print(qReversed.queue[0], end = " ")  
        qReversed.get()

出力: