Python キュー: FIFO、LIFO の例

Python キューとは何ですか?

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

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

行列は、チケット カウンターで列に並んで待っている人々の列と簡単に比較できます。最初に立っていた人が最初にチケットを受け取り、その後に次の人がチケットを受け取ります。 同じロジックがキューのデータ構造にも当てはまります。

キューを図で表すと次のようになります。

Python キューの作業

また, リア 項目がキュー内に挿入されるポイントを表します。 この例では、7 がその値です。

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

項目 1 はキューに最初に挿入されたもので、削除中に最初に出てくるものです。 したがって、キューは FIRST IN FIRST OUT (FIFO) と呼ばれます。

Python キューの作業

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

Python のキューの種類

Python には主に XNUMX 種類のキューがあります。

  • 先入れ先出しキュー: この場合、最初に配置された要素が最初に出力されます。FIFO を使用するには、次の呼び出しを行う必要があります。 列() キューモジュールのクラス。
  • Last in First out 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 クラス内で使用可能なメソッド

Following Queue および LifoQueue クラス内で使用できる重要なメソッドは次のとおりです。

  • 置く(項目): これにより、項目がキュー内に配置されます。
  • 得る(): これにより、キューからアイテムが返されます。
  • 空の(): キューが空の場合は true を返し、項目が存在する場合は false を返します。
  • qsize(): キューのサイズを返します。
  • 満杯(): キューがいっぱいの場合は true を返し、それ以外の場合は false を返します。

先入れ先出しキューの例

先入れ先出しの場合、最初に出現した要素が最初に出力されます。

アイテムをキューに追加します

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

item を追加するには、例に示すように 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() というメソッドを使用できます。 このメソッドは、呼び出されたときにキューからの項目を許可します。

次のことwing 例は、キューから項目を削除する方法を示しています。

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 に対して XNUMX つの項目を追加し、その項目を削除する方法を説明しました。 次に、複数の項目を追加する方法と削除する方法を見てみましょう。

FIFOキューにアイテムを追加する

import queue
q1 = queue.Queue()

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

FIFOキューから項目を削除します

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 

ソートキュー

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

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

キューを逆転する

キューを逆にするには、別のキューと再帰を使用できます。

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

例:

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()

出力:

10 3 21 4 5 11

まとめ

  • キューはデータを保持するコンテナです。 キューには FIFO と LIFO の XNUMX 種類があります。
  • FIFO (先入れ先出しキュー) の場合、最初に配置された要素が最初に出力されます。
  • LIFO (後入れ先出しキュー) の場合、最後に入力された要素が最初に出力されます。
  • キュー内の項目は put(item) メソッドを使用して追加されます。
  • 項目を削除するには get() メソッドを使用します。