Az adatstruktúrák kulcsszerepet játszanak a programozási világban. Segítenek abban, hogy adatainkat hatékonyan felhasználható módon rendszerezzük. A Queue az egyik legegyszerűbb elérhető adatstruktúra.
Ebben a cikkben megismerjük a Queue-t és annak Pythonban való megvalósítását.
Tartalomjegyzék
Mi az a várólista?
A Queue egy lineáris adatstruktúra, amely a First In/First Out (FIFO) elvet követi. Ellentétes a Stack adatszerkezettel.
Összehasonlíthatjuk a sort egy valós sorral a mozijegypénztárnál. Nézzük egy sor illusztrációját a következőképpen.
Ha megfigyeli a sorban állást a pultnál, a második személy csak akkor tud a pulthoz menni, ha az első befejezte a munkáját. Itt az első ember jön a pulthoz, majd a második személy. Tehát itt az emberek a FIFO (First In/First Out) elvet követik. Aki előbb jön, az előbb fejezi be a munkát. Hasonló sorokat láthatunk mindennapi életünkben.
A Queue adatstruktúra is ugyanezt az elvet követi. Most már tudja, mik a sorok, és annak elvét. Lássuk, milyen műveleteket lehet végrehajtani egy sor adatstruktúrán.
Műveletek a sorban
Hasonlóan a veremhez, két fő műveletet találunk egy sor adatstruktúrában.
sor(adat)
A végén új adatokat ad a sorhoz. Az oldalt hátsónak hívják.
dequeue()
Eltávolítja az adatokat a sor elejéről. Az oldalt elülsőnek nevezik.
Nézzük meg a sorműveletek illusztrációit a jobb megértés érdekében. Egy kép többet mond ezer szónál.
Írhatunk néhány segítő függvényt, hogy több információt kapjunk a sorról. Nincs korlátozva a segédfunkciók száma. Maradjunk most az alábbiakban említett legfontosabbnál.
hátulsó()
Visszaadja az első elemet a sor végéről.
elülső()
A sor elejétől az első elemet adja vissza.
üres()
Visszaadja, hogy a sor üres-e vagy sem.
Nem unalmas neked? Mármint a fogalmi témákra.
Nekem igen!
De nem tehetünk semmit a fogalmak ismerete nélkül. A megvalósítás előtt tudnunk kell. Ne aggódj, ideje bepiszkítani a kezünket valamilyen kóddal.
Feltételezem, hogy a python telepítve van a számítógépére, ha nem, akkor megpróbálhatja az online fordítót is.
Sor végrehajtása
A várólista megvalósítása egy programozónak nem tart tovább 15 percnél. Ha egyszer megtanultad, elmondod. Talán néhány percen belül megvalósíthatja ezt az oktatóanyagot követően.
A várólista Pythonban többféleképpen is implementálható. Lássuk lépésről lépésre a különböző sormegvalósításokat.
#1. Lista
A lista egy beépített adattípus a Pythonban. A lista adattípust fogjuk használni egy sor megvalósításához egy osztályban. Végigvezetjük a sor adatszerkezetének modulok nélküli, a semmiből történő megvalósításának különböző lépéseit. Ugorjunk bele.
1. lépés:
Írj egy osztályt Queue néven.
class Queue: pass
2. lépés:
Kell lennie valamilyen változónak a sor adatainak tárolására az osztályban. Nevezzük el elemeknek. És ez természetesen egy lista.
class Queue: def __init__(self): self.elements = []
3. lépés:
Adatok beszúrásához a sorba szükségünk van egy metódusra az osztályban. A módszer neve enqueue, amint azt az oktatóanyag előző részében már tárgyaltuk.
A metódus vesz néhány adatot, és hozzáadja a sorhoz (elemekhez). A lista adattípus append metódusát használhatjuk adatok hozzáadásához a sor végére.
class Queue: # ... def enqueue(self, data): self.elements.append(data) return data
4. lépés:
A sornak kijárattal kell rendelkeznie. És ezt hívják kimaradásnak. Azt hiszem, már sejtette, hogy a lista adattípus pop módszerét fogjuk használni. Ha kitaláltad, ha nem, egészségedre!
A lista adattípus pop metódusa töröl egy elemet az adott index listájából. Ha nem adtunk meg indexet, akkor törli a lista utolsó elemét.
Itt törölnünk kell a lista első elemét. Tehát a 0 indexet át kell adnunk a pop metódusnak.
class Queue: # ... def dequeue(self): return self.elements.pop(0)
Ez elég egy sorhoz. De szükségünk van a segítő függvényekre, hogy ellenőrizzük, hogy a sorműveletek megfelelően működnek-e vagy sem. Írjuk fel a segítő függvényeket is.
5. lépés:
A rear() metódus a sor utolsó elemének lekérésére szolgál. A lista adattípusú negatív indexelés segít abban, hogy megkapjuk a sor utolsó elemét.
class Queue: # ... def rear(self): return self.elements[-1]
6. lépés:
A front() metódus a sor első elemének lekérésére szolgál. A sor első elemét a listaindex segítségével kaphatjuk meg.
class Queue: # ... def front(self): return self.elements[0]
7. lépés:
Az is_empty() metódus annak ellenőrzésére szolgál, hogy a sor üres-e vagy sem. Ellenőrizhetjük a lista hosszát.
class Queue: # ... def is_empty(self): return len(self.elements) == 0
Fú! befejezte a sor adatstruktúra megvalósítási részét. Létre kell hoznunk egy objektumot a Queue osztály használatához.
Csináljuk.
class Queue: # ... if __name__ == '__main__': queue = Queue()
Most van egy Queue objektum. Teszteljük néhány műveletsorral.
- Az is_empty metódus segítségével ellenőrizze, hogy a sor üres-e vagy sem. Igaznak kell visszaadnia.
- Adja hozzá az 1, 2, 3, 4, 5 számokat a sorhoz az enqueue módszerrel.
- Az is_empty metódusnak False értéket kell adnia. Ellenőrizd.
- Nyomtassa ki az elülső és a hátsó elemeket az első és a hátsó módszerrel.
- Távolítsa el az elemet a sorból a dequeue módszerrel.
- Ellenőrizze az elülső elemet. A 2-es elemet kell visszaadnia.
- Most távolítsa el az összes elemet a sorból.
- Az is_empty metódusnak True értéket kell adnia. Ellenőrizd.
Azt hiszem, ez elég ahhoz, hogy teszteljük a sor megvalósítását. Írja be a kódot minden fent említett lépéshez a várólista teszteléséhez.
Megírtad a kódot?
Nem, ne aggódj.
Ellenőrizze az alábbi kódot.
class Queue: def __init__(self): self.elements = [] def enqueue(self, data): self.elements.append(data) return data def dequeue(self): return self.elements.pop(0) def rear(self): return self.elements[-1] def front(self): return self.elements[0] def is_empty(self): return len(self.elements) == 0 if __name__ == '__main__': queue = Queue() ## checking is_empty method -> True print(queue.is_empty()) ## adding the elements queue.enqueue(1) queue.enqueue(2) queue.enqueue(3) queue.enqueue(4) queue.enqueue(5) ## again checking is_empty method -> False print(queue.is_empty()) ## printing the front and rear elements using front and rear methods respectively -> 1, 5 print(queue.front(), end=' ') print(queue.rear()) ## removing the element -> 1 queue.dequeue() ## checking the front and rear elements using front and rear methods respectively -> 2 5 print(queue.front(), end=' ') print(queue.rear()) ## removing all the elements queue.dequeue() queue.dequeue() queue.dequeue() queue.dequeue() ## checking the is_empty method for the last time -> True print(queue.is_empty())
Szerintem futtasd a fenti programot. A következő eredményhez hasonló kimenetet kaphat.
True False 1 5 2 5 True
A lista adattípust közvetlenül használhatjuk sor adatstruktúraként. A várólista fenti megvalósítása segít jobban megérteni a sor implementációját más programozási nyelveken.
Használhatja a várólista fenti osztályú implementációját egy projekt másik programjában is, ha egyszerűen létrehozza az objektumot, ahogy korábban tettük.
A sort a nulláról valósítottuk meg a lista adattípus használatával. Vannak beépített modulok a sorhoz? Igen! beépített sormegvalósításaink vannak. Lássuk őket.
#2. deque gyűjteményekből
Kétvégű várólistaként van megvalósítva. Mivel mindkét végéről támogatja az elemek hozzáadását és eltávolítását, így veremként és sorként is használhatjuk. Lássuk a sormegvalósítást a dequeue használatával.
Más adatstruktúrák segítségével valósul meg, amelyeket duplán linkelt listának neveznek. Tehát az elemek beillesztésének és törlésének teljesítménye konzisztens. A középső linkelt lista elemeinek elérése O(n) időt vett igénybe. Használhatjuk sorként, mivel nem kell a sorból elérni a középső elemeket.
Vizsgáljuk meg a dequeue által kínált különböző módszereket.
- append(data) – az adatok hozzáadására szolgál a sorhoz
- popleft() – az első elem eltávolítására szolgál a sorból
Nincsenek alternatív módszerek az elülső, a hátsó és az is_empty számára. Az elülső és hátsó metódusok helyett a teljes sort kinyomtathatjuk. Ezután a len módszerrel ellenőrizhetjük, hogy a sor üres-e vagy sem.
Az előzőekben egy sor lépést követtünk a várólista megvalósításának tesztelésére. Kövessük itt is ugyanezt a lépéssort.
from collections import deque ## creating deque object queue = deque() ## checking whether queue is empty or not -> True print(len(queue) == 0) ## pushing the elements queue.append(1) queue.append(2) queue.append(3) queue.append(4) queue.append(5) ## again checking whether queue is empty or not -> False print(len(queue) == 0) ## printing the queue print(queue) ## removing the element -> 1 queue.popleft() ## printing the queue print(queue) ## removing all the elements queue.popleft() queue.popleft() queue.popleft() queue.popleft() ## checking the whether queue is empty or not for the last time -> True print(len(queue) == 0)
A következő kimenethez hasonló eredményt kap.
True False deque([1, 2, 3, 4, 5]) deque([2, 3, 4, 5]) True
#3. Sor a sorból
A Python rendelkezik egy queue nevű beépített modullal, amely a Queue nevű osztályt szolgálja ki a sor megvalósításához. Hasonló ahhoz, amit korábban megvalósítottunk.
Először nézzük meg a Queue osztály különböző metódusait.
- put(data) – hozzáadja vagy elküldi az adatokat a sorba
- get() – eltávolítja az első elemet a sorból, és visszaadja
- üres() – visszaadja, hogy a verem üres-e vagy sem
- qsize() – a sor hosszát adja vissza.
Valósítsuk meg a sort a fenti módszerekkel.
from queue import Queue
## creating Queue object
queue_object = Queue()
## checking whether queue is empty or not -> True
print(queue_object.empty())
## adding the elements
queue_object.put(1)
queue_object.put(2)
queue_object.put(3)
queue_object.put(4)
queue_object.put(5)
## again checking whether queue is empty or not -> False
print(queue_object.empty())
## removing all the elements
print(queue_object.get())
print(queue_object.get())
print(queue_object.get())
## checking the queue size
print("Size", queue_object.qsize())
print(queue_object.get())
print(queue_object.get())
## checking the whether queue_object is empty or not for the last time -> True
print(queue_object.empty())
Ellenőrizze a fenti kód kimenetét.
True False 1 2 3 Size 2 4 5 True
Van néhány más metódus is a Queue osztályban. A dir beépített funkcióval fedezheti fel őket.
Következtetés
Remélem, tanult a sor adatszerkezetéről és annak megvalósításáról. Ennyit a sorról. A sort különböző helyeken használhatja, ahol FIFO (First In/First Out) sorrendben kell feldolgozni. Használja a queue-t a problémamegoldásban, amikor az esetet használja.
Érdekli a Python elsajátítása? Tekintse meg ezeket a tanulási forrásokat.
Boldog kódolást 🙂 👨💻