Python คิว: FIFO, LIFO ตัวอย่าง

ความหมายของ Python คิว?

คิวคือคอนเทนเนอร์ที่เก็บข้อมูล ข้อมูลที่ป้อนก่อนจะถูกลบออกก่อน และคิวจึงเรียกอีกอย่างว่า "เข้าก่อนออกก่อน" (FIFO) คิวมีสองปลายทั้งหน้าและหลัง รายการจะถูกป้อนจากด้านหลังและนำออกจากด้านหน้า

อย่างไร Python งานเข้าคิว?

สามารถเปรียบเทียบคิวกับตัวอย่างในชีวิตจริงได้อย่างง่ายดาย เช่น การต่อคิวที่เคาน์เตอร์จำหน่ายตั๋ว คนที่ยืนก่อนจะได้ตั๋วก่อน ตามด้วยคนถัดไป เป็นต้น ตรรกะเดียวกันนี้ใช้กับโครงสร้างข้อมูลคิวด้วย

นี่คือการแสดงคิวแบบไดอะแกรม:

การขอ ด้านหลัง แสดงถึงจุดที่รายการถูกแทรกเข้าไปในคิว ในตัวอย่างนี้ 7 คือค่าของค่านั้น

การขอ ด้านหน้า แสดงถึงจุดที่รายการออกจากคิวจะถูกลบออก หากคุณลบไอเท็มออกจากคิว องค์ประกอบแรกที่คุณจะได้รับคือ 1 ดังแสดงในรูป

รายการที่ 1 เป็นรายการแรกที่จะถูกแทรกลงในคิว และในขณะที่นำออกจะเป็นรายการแรกที่ออกมา ดังนั้นคิวจึงถูกเรียกว่า FIRST IN FIRST OUT (FIFO)

ในคิว รายการต่างๆ จะถูกลบออกตามลำดับ และไม่สามารถลบออกจากระหว่างนั้นได้ คุณไม่สามารถลบรายการที่ 5 แบบสุ่มออกจากคิวได้ โดยคุณจะต้องลบรายการทั้งหมดก่อนรายการที่ 5 รายการในคิวจะถูกลบออกตามลำดับที่แทรกไว้

ประเภทของคิวเข้า Python

ส่วนใหญ่จะมีคิวอยู่สองประเภท Python:

• เข้าก่อนออกก่อน: สำหรับสิ่งนี้ องค์ประกอบที่ไปก่อนจะเป็นคนแรกที่ออกมา หากต้องการทำงานกับ FIFO คุณต้องโทร คิว() คลาสจากโมดูลคิว
• เข้าคิวออกก่อน: ตรงนี้ องค์ประกอบที่ป้อนสุดท้ายจะเป็นคนแรกที่ออกมา หากต้องการทำงานกับ LIFO คุณต้องโทร LifoQueue() คลาสจากโมดูลคิว

Python การติดตั้งคิว

มันง่ายมากที่จะทำงานกับคิวในหลาม ต่อไปนี้เป็นขั้นตอนที่ต้องปฏิบัติตามเพื่อใช้คิวในโค้ดของคุณ

ขั้นตอน 1) คุณเพียงแค่ต้องนำเข้าโมดูลคิว ดังที่แสดงด้านล่าง:

import queue

โมดูลนี้ใช้งานได้ตามค่าเริ่มต้นกับ python และคุณไม่จำเป็นต้องติดตั้งเพิ่มเติมเพื่อเริ่มทำงานกับคิว คิว FIFO มี 2 ประเภท (เข้าก่อนออกก่อน) และ LIFO (เข้าก่อนออกก่อน)

ขั้นตอน 2) หากต้องการทำงานกับคิว FIFO ให้เรียกคลาส Queue โดยใช้โมดูลคิวที่นำเข้าตามที่แสดงด้านล่าง:

import queue
q1 = queue.Queue()

ขั้นตอน 3) หากต้องการทำงานกับคิว LIFO ให้เรียกคลาส LifoQueue() ดังที่แสดงด้านล่าง:

import queue
q1 = queue.LifoQueue()

วิธีการที่มีอยู่ในคลาส Queue และ LifoQueue

ต่อไปนี้เป็นวิธีการสำคัญที่มีอยู่ในคลาส Queue และ LifoQueue:

• ใส่(รายการ): นี่จะทำให้รายการอยู่ในคิว
• รับ(): นี่จะส่งคืนรายการให้คุณจากคิว
• ว่างเปล่า(): มันจะคืนค่าเป็นจริงหากคิวว่างเปล่าและเป็นเท็จหากมีรายการอยู่
• ขนาดไซส์(): ส่งกลับขนาดของคิว
• เต็ม(): คืนค่าเป็นจริงถ้าคิวเต็ม ไม่เช่นนั้นคืนค่าเท็จ

ตัวอย่างคิวเข้าก่อนออกก่อน

ในกรณีที่เข้าก่อนออกก่อน องค์ประกอบที่ไปก่อนจะเป็นคนแรกที่ออกมา

เพิ่มและรายการในคิว

ให้เราทำงานกับตัวอย่างเพื่อเพิ่มรายการในคิว หากต้องการเริ่มทำงานกับคิว ให้นำเข้าคิวโมดูลก่อน ดังที่แสดงในตัวอย่างด้านล่าง

หากต้องการเพิ่ม 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.

Output:

True

ตอนนี้ขนาดของคิวคือ 5 และจะใช้เวลาไม่เกิน 5 รายการ และเมธอด q1.full() จะคืนค่าเป็นจริง การเพิ่มรายการใดๆ จะไม่รันโค้ดอีกต่อไป

ลบรายการออกจากคิว

หากต้องการลบรายการออกจากคิว คุณสามารถใช้เมธอดที่เรียกว่า get() เมธอดนี้อนุญาตให้ไอเท็มจากคิวเมื่อถูกเรียก

ตัวอย่างต่อไปนี้จะแสดงวิธีลบรายการออกจากคิว

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

item1 = q1.get()

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

Output:

The item removed from the queue is  10

ตัวอย่างการเข้าคิวครั้งสุดท้ายเข้าก่อนออก

ในกรณีของลำดับสุดท้ายในคิวออกครั้งแรก องค์ประกอบที่ป้อนครั้งสุดท้ายจะเป็นคนแรกที่ออกมา

หากต้องการทำงานกับ LIFO เช่น อยู่ในคิวออกลำดับแรก เราจำเป็นต้องนำเข้าโมดูลคิวและใช้ประโยชน์จากเมธอด LifoQueue()

เพิ่มและรายการในคิว

ที่นี่เราจะเข้าใจวิธีการเพิ่มรายการลงในคิว LIFO

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

คุณต้องใช้เมธอด put() บน LifoQueue ดังที่แสดงในตัวอย่างข้างต้น

ลบรายการออกจากคิว

หากต้องการลบรายการออกจาก LIFOqueue คุณสามารถใช้เมธอด get() ได้

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

item1 = q1.get()

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

Output:

The item removed from the LIFO queue is  10

เพิ่มมากกว่า 1 รายการในคิว

ในตัวอย่างข้างต้น เราได้เห็นวิธีการเพิ่มรายการเดียวและลบรายการสำหรับ 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.

Output:

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.

Output:

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

Output:

3 4 5 10 11 21

Revกำลังเข้าคิว

หากต้องการกลับคิว คุณสามารถใช้คิวอื่นและการเรียกซ้ำได้

ตัวอย่างต่อไปนี้จะแสดงวิธีการย้อนลำดับคิว

ตัวอย่าง:

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

Output:

10 3 21 4 5 11

สรุป

• คิวคือคอนเทนเนอร์ที่เก็บข้อมูล คิวมีสองประเภท FIFO และ LIFO
• สำหรับ FIFO (เข้าก่อนออกก่อน) องค์ประกอบที่ไปก่อนจะเป็นคนแรกที่ออกมา
• สำหรับ LIFO (เข้าครั้งสุดท้ายก่อนออกคิว) องค์ประกอบที่ป้อนครั้งสุดท้ายจะเป็นคนแรกที่ออกมา
• รายการในคิวจะถูกเพิ่มโดยใช้วิธีใส่ (รายการ)
• หากต้องการลบรายการออก ให้ใช้เมธอด get()