Python Red čekanja: FIFO, LIFO Primjer
Logan Young
Što je Python Red?
Red čekanja je spremnik koji sadrži podatke. Podaci koji su prvi uneseni bit će prvi uklonjeni, pa se stoga red čekanja naziva i "Prvi ušao, prvi izašao" (FIFO). Red čekanja ima dva kraja, prednji i stražnji. Predmeti se unose sa stražnje strane, a vade s prednje strane.
Kako Python Rad u redu?
Red se može lako usporediti s primjerom iz stvarnog svijeta, red ljudi koji čekaju u redu na šalteru za prodaju karata, osoba koja stoji prva dobit će kartu prva, a slijedi sljedeća osoba i tako dalje. Ista logika vrijedi i za strukturu podataka čekanja.
Ovdje je dijagramski prikaz reda:
Korištenje električnih romobila ističe Stražnji predstavlja točku u kojoj se stavke umeću unutar reda čekanja. U ovom primjeru, 7 je vrijednost za to.
Korištenje električnih romobila ističe Ispred predstavlja točku na kojoj će stavke iz reda biti uklonjene. Ako uklonite stavku iz reda čekanja, prvi element koji ćete dobiti je 1, kao što je prikazano na slici.
Stavka 1 je bila prva koja je umetnuta u red čekanja, a pri uklanjanju je prva koja je izašla. Stoga se red čekanja zove PRVI UĐE PRVI OUT (FIFO)
U redu čekanja, stavke se uklanjaju redom i ne mogu se ukloniti između. Samo ne možete nasumično ukloniti stavku 5 iz reda čekanja, da biste to učinili, morat ćete ukloniti sve stavke prije 5. Stavke u redu čekanja bit će uklonjene redoslijedom kojim su umetnute.
Vrste čekanja u Python
Uglavnom postoje dvije vrste čekanja u redu Python:
- First in First out Queue: Za ovo, element koji ide prvi bit će prvi koji će izaći. Da biste radili s FIFO-om, morate pozvati Red() klasa iz modula čekanja.
- Zadnji ušao, prvi izašao iz reda čekanja: Ovdje će element koji je posljednji unesen prvi izaći. Za rad s LIFO-om morate pozvati LifoQueue() klase iz modula čekanja.
Python Instalacija reda čekanja
Vrlo je jednostavno raditi s redom čekanja u pythonu. Evo koraka koje trebate slijediti da biste iskoristili red čekanja u svom kodu.
Korak 1) Samo trebate uvesti modul čekanja, kao što je prikazano u nastavku:
import queue
Modul je dostupan prema zadanim postavkama s pythonom i nije vam potrebna nikakva dodatna instalacija za početak rada s redom čekanja. Postoje 2 vrste reda čekanja FIFO (prvi ušao prvi izašao) i LIFO (zadnji ušao prvi izašao).
Korak 2) Za rad s FIFO redom čekanja, pozovite klasu Queue pomoću uvezenog modula čekanja kao što je prikazano u nastavku:
import queue q1 = queue.Queue()
Korak 3) Za rad s LIFO redom pozovite klasu LifoQueue() kao što je prikazano u nastavku:
import queue q1 = queue.LifoQueue()
Metode dostupne unutar klase Queue i LifoQueue
Slijede važne metode dostupne unutar Queue i LifoQueue klase:
- stavi(stavka): Ovo će stavku staviti u red čekanja.
- dobiti(): Ovo će vam vratiti stavku iz reda čekanja.
- prazan(): Vratit će true ako je red prazan i false ako su stavke prisutne.
- qsize(): vraća veličinu reda čekanja.
- puni(): vraća true ako je red čekanja pun, inače false.
Prvi ušao, prvi izašao primjer reda čekanja
U slučaju prvi ušao, prvi izašao, prvi će izaći element koji ide prvi.
Dodaj i stavku u redu čekanja
Poradimo na primjeru dodavanja stavke u red čekanja. Da biste počeli raditi s redom čekanja, prvo uvezite red čekanja modula, kao što je prikazano u primjeru u nastavku.
Da biste dodali stavku, možete koristiti put() metodu kao što je prikazano u primjeru:
import queue q1 = queue.Queue() q1.put(10) #this will additem 10 to the queue.
Prema zadanim postavkama, veličina reda je beskonačna i možete dodati bilo koji broj stavki u njega. U slučaju da želite definirati veličinu reda čekanja, isto možete učiniti na sljedeći način
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.
Izlaz:
True
Sada je veličina reda 5, i neće uzeti više od 5 stavki, a metoda q1.full() će vratiti true. Dodavanje još stavki neće dalje izvršavati kôd.
Uklonite stavku iz reda čekanja
Da biste uklonili stavku iz reda čekanja, možete koristiti metodu koja se zove get(). Ova metoda dopušta stavke iz reda kada se pozovu.
Sljedeći primjer pokazuje kako ukloniti stavku iz reda čekanja.
import queue
q1 = queue.Queue()
q1.put(10)
item1 = q1.get()
print('The item removed from the queue is ', item1)
Izlaz:
The item removed from the queue is 10
Primjer reda zadnji ušao prvi izišao
U slučaju zadnjeg u prvom izlaznom redu čekanja, element koji je posljednji unesen bit će prvi koji će izaći.
Da bismo radili s LIFO-om, tj. zadnji u redu čekanja, moramo uvesti modul čekanja i koristiti metodu LifoQueue().
Dodaj i stavku u redu čekanja
Ovdje ćemo razumjeti kako dodati stavku u LIFO red čekanja.
import queue q1 = queue.LifoQueue() q1.put(10)
Morate koristiti metodu put() na LifoQueue, kao što je prikazano u gornjem primjeru.
Uklonite stavku iz reda čekanja
Za uklanjanje stavke iz LIFOqueuea možete koristiti metodu get().
import queue
q1 = queue.LifoQueue()
q1.put(10)
item1 = q1.get()
print('The item removed from the LIFO queue is ', item1)
Izlaz:
The item removed from the LIFO queue is 10
Dodajte više od 1 stavke u red čekanja
U gornjim primjerima vidjeli smo kako dodati jednu stavku i ukloniti stavku za FIFO i LIFOqueue. Sada ćemo vidjeti kako dodati više od jedne stavke i ukloniti ih.
Dodaj i stavku u FIFOqueue
import queue
q1 = queue.Queue()
for i in range(20):
q1.put(i) # this will additem from 0 to 20 to the queue
Uklonite stavku iz FIFOqueuea
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.
Izlaz:
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
Dodaj i stavku u LIFOqueue
import queue
q1 = queue.LifoQueue()
for i in range(20):
q1.put(i) # this will additem from 0 to 20 to the queue
Uklonite stavku iz LIFOqueuea
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.
Izlaz:
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
Red čekanja za sortiranje
Sljedeći primjer prikazuje sortiranje u redu čekanja. Algoritam koji se koristi za sortiranje je sortiranje u obliku mjehurića.
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()
Izlaz:
3 4 5 10 11 21
Reversing Queue
Da biste preokrenuli red čekanja, možete koristiti drugi red čekanja i rekurziju.
Sljedeći primjer pokazuje kako vratiti red čekanja.
Primjer:
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()
Izlaz:
10 3 21 4 5 11
rezime
- Red čekanja je spremnik koji sadrži podatke. Postoje dvije vrste reda čekanja, FIFO i LIFO.
- Za FIFO (First in First Out Queue), element koji ide prvi bit će prvi koji će izaći.
- Za LIFO (Last in First Out Queue), element koji je posljednji unesen prvi će izaći.
- Stavka u red čekanja dodaje se metodom put(item).
- Za uklanjanje stavke koristi se metoda get().
