Python คิว: FIFO, LIFO ตัวอย่าง
โลแกน ยัง
⚡ สรุปอย่างชาญฉลาด
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
