Python Sor: FIFO, LIFO Példa
Logan Young
Mi a Python Várólista?
A várólista egy tároló, amely adatokat tartalmaz. Az elsőként bevitt adatok törlődnek először, ezért a sort „First in First Out” (FIFO) is nevezik. A sornak két vége van elöl és hátul. Az elemeket hátulról lehet bevinni és elölről eltávolítani.
Hogyan működik Python Várólista munka?
A sor könnyen összehasonlítható a valós példával, a jegypénztárnál sorban álló emberek sorával, az elsőként álló kapja meg először a jegyet, őt követi a következő és így tovább. Ugyanez a logika vonatkozik a sor adatszerkezetére is.
Itt van a várólista diagramos ábrázolása:
A Hátulsó azt a pontot jelöli, ahol az elemek bekerülnek a sorba. Ebben a példában a 7 ennek értéke.
A Front azt a pontot jelöli, ahol a sorból a tételek eltávolításra kerülnek. Ha eltávolít egy elemet a sorból, az első elem, amelyet kap, az 1, ahogy az ábrán is látható.
Az 1. elem volt az első, amely bekerült a sorba, és az eltávolítása során először került ki. Ezért a sort FIFO-nak (FIRST IN FIRST OUT) hívják.
A sorban lévő elemek sorrendben kerülnek eltávolításra, és nem távolíthatók el a kettő közül. Az 5-ös elemet egyszerűen nem távolíthatja el véletlenszerűen a sorból, ehhez el kell távolítania az 5-ös előtti összes elemet. A sorban lévő elemek a beillesztésük sorrendjében kerülnek eltávolításra.
A várakozási sor típusai Python
Főleg kétféle sorbanállás létezik Python:
- First in First Out Queue: Ehhez az elsőként érkező elem fog kijönni először. A FIFO használatához meg kell hívnia sor() osztály a sormodulból.
- Last in First Out Queue: Itt az utoljára beírt elem jön ki először. A LIFO használatához meg kell hívnia LifoQueue() osztályt a sormodulból.
Python sor Telepítés
A pythonban nagyon könnyű a sorral dolgozni. Az alábbiakban bemutatjuk azokat a lépéseket, amelyeket követni kell a sor használatához a kódban.
Step 1) Csak importálnia kell a sormodult, az alábbiak szerint:
import queue
A modul alapértelmezés szerint elérhető a python-nal, és nincs szükség további telepítésre a sorral való munka megkezdéséhez. Kétféle FIFO (first in first out) és LIFO (last in first out) sor létezik.
Step 2) A FIFO queue használatához hívja meg a Queue osztályt az alábbiak szerint importált sormodul segítségével:
import queue q1 = queue.Queue()
Step 3) A LIFO sorral való munkához hívja a LifoQueue() osztályt az alábbiak szerint:
import queue q1 = queue.LifoQueue()
A Queue és a LifoQueue osztályon belül elérhető módszerek
Az alábbiakban felsoroljuk a Queue és LifoQueue osztályon belül elérhető fontos módszereket:
- put(elem): Ezzel az elem a sorba kerül.
- kap(): Ezzel visszaad egy elemet a sorból.
- üres(): Igaz, ha a sor üres, hamis értéket ad vissza, ha elemek vannak jelen.
- qsize(): visszaadja a sor méretét.
- teljes(): true értéket ad vissza, ha a sor megtelt, ellenkező esetben false értéket ad vissza.
Példa First In First Out Queue
A first in first out esetén az elsőként befutó elem jön ki először.
Hozzáadás és tétel a sorban
Nézzünk egy példát egy tétel hozzáadására a sorba. A sorral való munka megkezdéséhez először importálja a modulsort az alábbi példában látható módon.
Elem hozzáadásához használhatja a put() metódust a példában látható módon:
import queue q1 = queue.Queue() q1.put(10) #this will additem 10 to the queue.
Alapértelmezés szerint a sor mérete végtelen, és tetszőleges számú elemet adhat hozzá. Abban az esetben, ha meg akarja határozni a sor méretét, ugyanezt a következőképpen teheti meg
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
Most a sor mérete 5, és nem fog több mint 5 elemet igénybe venni, és a q1.full() metódus igaz értéket ad vissza. További elemek hozzáadása nem hajtja végre a kódot.
Elem eltávolítása a sorból
Egy elem eltávolításához a sorból használhatja a get() nevű metódust. Ez a módszer híváskor engedélyezi az elemeket a sorból.
A következő példa bemutatja, hogyan távolíthat el egy elemet a sorból.
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
Példa a Last In First Out sorra
Az első kimenő sor utolsó eleme esetén az utolsóként beírt elem fog először kimenni.
Ahhoz, hogy a LIFO-val dolgozhassunk, azaz az első kimenő sorban utolsóként, importálnunk kell a sormodult, és használnunk kell a LifoQueue() metódust.
Hozzáadás és tétel a sorban
Itt megtudjuk, hogyan adjunk hozzá egy elemet a LIFO-sorhoz.
import queue q1 = queue.LifoQueue() q1.put(10)
A fenti példában látható módon a put() metódust kell használnia a LifoQueue-n.
Elem eltávolítása a sorból
Egy elem eltávolításához a LIFOqueue-ból használhatja a get() metódust.
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-nél több elem hozzáadása a sorhoz
A fenti példákban láthattuk, hogyan lehet egyetlen elemet hozzáadni és eltávolítani a FIFO és LIFOqueue számára. Most meglátjuk, hogyan adjunk hozzá több elemet, és hogyan távolítsuk el.
Hozzáadás és tétel a FIFOsorban
import queue
q1 = queue.Queue()
for i in range(20):
q1.put(i) # this will additem from 0 to 20 to the queue
Távolítson el egy elemet a FIFO-sorból
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
Hozzáadás és elem a LIFOqueue-ban
import queue
q1 = queue.LifoQueue()
for i in range(20):
q1.put(i) # this will additem from 0 to 20 to the queue
Távolítson el egy elemet a LIFOqueue-ból
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
Rendezési sor
A következő példa a sorrendezést mutatja be. A rendezéshez használt algoritmus buborékos rendezés.
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
Reversing Queue
A sor megfordításához használhat egy másik sort és rekurziót.
A következő példa bemutatja, hogyan lehet megfordítani a sort.
Példa:
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
Összegzésként
- A várólista egy tároló, amely adatokat tartalmaz. Kétféle sor létezik, a FIFO és a LIFO.
- A FIFO (First in First Out Queue) esetén az elsőként érkező elem fog először kijönni.
- A LIFO (Last in First Out Queue) esetén az utoljára beírt elem jelenik meg először.
- A sorban lévő elemek a put(item) metódussal kerülnek hozzáadásra.
- Egy elem eltávolításához a get() metódust használjuk.
