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 verem az egyik legegyszerűbb adatstruktúra.
Tanuljunk meg a veremről és annak Pythonban való megvalósításáról.
Mi az a verem?
A halom a való életben hasonló a könyvhalomhoz, székhez stb. És ez az utolsó be/első ki (LIFO) elvet követi. Ez a legegyszerűbb adatstruktúra. Lássuk a forgatókönyvet egy valós példával.
Tegyük fel, hogy van egy halom könyvünk a következőképpen.
Amikor felülről szeretnénk a harmadik könyvet, akkor el kell távolítanunk az első két könyvet felülről, hogy kivegyük a harmadik könyvet. Itt a legfelső könyv utoljára kerül a kupacba, és az első a halomban. Az adatszerkezeti verem ugyanazt az elvet követi, hogy a programozásban a Last-in/First-out (LIFO).
Műveletek a Stackben
Főleg két művelet van egy veremben
1. push(adat)
Hozzáadja vagy a verembe tolja az adatokat.
2. pop()
Eltávolítja vagy kiemeli a verem legfelső elemét.
Lásd az alábbi ábrákat a push és pop műveletekről.
Leírunk néhány segédfüggvényt, amelyek segítségével több információhoz juthatunk a veremről.
Lássuk őket.
kandikál()
A verem legfelső elemét adja vissza.
üres()
Visszaadja, hogy a verem üres-e vagy sem.
Elég fogalmi vonatkozásai a verem adatszerkezetének. Minden további nélkül vágjunk bele a megvalósításba.
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.
Stack megvalósítás
A verem megvalósítása a legegyszerűbb a többi adatstruktúra-megvalósításhoz képest. A Pythonban többféle módon is megvalósíthatunk veremeket.
Lássuk mindegyiket egyenként.
#1. Lista
A veremet a lista segítségével fogjuk megvalósítani egy osztályban. Lássuk a verem lépésről lépésre történő megvalósítását.
1. lépés: Írj egy Stack nevű osztályt.
class Stack: pass
2. lépés: Az adatokat listában kell tartanunk. Adjunk hozzá egy üres listát a Stack osztályban névelemekkel.
class Stack: def __init__(self): self.elements = []
3. lépés: Ahhoz, hogy az elemeket a verembe toljuk, szükségünk van egy módszerre. Írjunk egy push metódust, amely az adatokat argumentumként veszi, és hozzáfűzi az elemek listájához.
class Stack: def __init__(self): self.elements = [] def push(self, data): self.elements.append(data) return data
4. lépés: Hasonlóképpen írjuk meg a pop módszert, amely a verem legfelső elemét ugrik ki. Használhatjuk a lista adattípus pop módszerét.
class Stack: ## ... def pop(self): return self.elements.pop()
A verem megvalósítását a szükséges műveletekkel befejeztük. Most adjuk hozzá a segédfunkciókat, hogy további információkat kapjunk a veremről.
5. lépés: A negatív index segítségével megkaphatjuk a verem legfelső elemét. A kód elem[-1] a lista utolsó részét adja vissza. Esetünkben ez a verem legfelső eleme.
class Stack: ## ... def peek(self): return self.elements[-1]
6. lépés: Ha az elemlista hossza 0, akkor a verem üres. Írjunk egy metódust, amely visszaadja, hogy az elem üres-e vagy sem.
class Stack: ## ... def is_empty(self): return len(self.elements) == 0
Befejeztük a verem megvalósítását a lista adattípus használatával.
Ó! várjunk csak megvalósítottuk. De nem láttam, hogyan kell használni. Akkor hogyan kell használni?
Gyere, nézzük meg, hogyan kell megvalósítani. Létre kell hoznunk egy objektumot a Stack osztály használatához. Ez nem egy nagy dolog. Először csináljuk meg.
class Stack: ## ... if __name__ == '__main__': stack = Stack()
Létrehoztuk a veremobjektumot, és készen állunk a használatra. Kövesse az alábbi lépéseket a veremműveletek teszteléséhez.
- Az is_empty metódus segítségével ellenőrizze, hogy a verem üres-e vagy sem. Igaznak kell visszaadnia.
- Tolja be a verembe az 1, 2, 3, 4, 5 számokat a push módszerrel.
- Az is_empty metódusnak False értéket kell adnia. Ellenőrizd.
- Nyomtassa ki a legfelső elemet a peek módszerrel.
- Az elemet a veremből pop módszerrel helyezze elő.
- Ellenőrizze a peek elemet. A 4-es elemet kell visszaadnia.
- Most emelje ki az összes elemet a veremből.
- Az is_empty metódusnak True értéket kell adnia. Ellenőrizd.
A verem megvalósítása akkor fejeződik be, ha az összes fenti lépésen túl van. Próbálja meg megírni a kódot a fenti lépésekhez.
Megírtad a kódot? Nem, ne aggódjon, ellenőrizze az alábbi kódot.
class Stack: def __init__(self): self.elements = [] def push(self, data): self.elements.append(data) return data def pop(self): return self.elements.pop() def peek(self): return self.elements[-1] def is_empty(self): return len(self.elements) == 0 if __name__ == '__main__': stack = Stack() ## checking is_empty method -> true print(stack.is_empty()) ## pushing the elements stack.push(1) stack.push(2) stack.push(3) stack.push(4) stack.push(5) ## again checking is_empty method -> false print(stack.is_empty()) ## printing the topmost element of the stack -> 5 print(stack.peek()) ## popping the topmost element -> 5 stack.pop() ## checking the topmost element using peek method -> 4 print(stack.peek()) ## popping all the elements stack.pop() stack.pop() stack.pop() stack.pop() ## checking the is_empty method for the last time -> true print(stack.is_empty())
Hurrá! a verem megvalósítását a nulláról végeztük el a lista adattípus használatával. Ha futtatja a fenti kódot, az alábbiakban említett kimenetet fogja látni.
True False 5 4 True
A lista adattípust közvetlenül használhatjuk veremként. A verem fenti megvalósítása segít megérteni a verem megvalósítását más programozási nyelveken is.
Ezeket a listával kapcsolatos cikkeket is megtekintheti.
Lássuk a beépített deque-t a gyűjteményekből. Beépített modul, amely veremként is működhet.
#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. Ezért veremként használhatjuk. Követhetjük a verem LIFO elvét.
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 veremként, mivel a középső elemekhez nem kell hozzáférni a veremből.
A verem implementálása előtt nézzük meg azokat a metódusokat, amelyekkel a verem a várólista segítségével valósítható meg.
- append(data) – az adatok verembe helyezésére szolgál
- pop() – a legfelső elem eltávolítására szolgál a veremből
Nincsenek alternatív módszerek a peek és az is_empty számára. A peek módszer helyett a teljes köteget kinyomtathatjuk. Ezután a len módszerrel ellenőrizhetjük, hogy a verem üres-e vagy sem.
Valósítsuk meg a veremet a deque segítségével a gyűjtemények modulból.
from collections import deque ## creating deque object stack = deque() ## checking whether stack is empty or not -> true print(len(stack) == 0) ## pushing the elements stack.append(1) stack.append(2) stack.append(3) stack.append(4) stack.append(5) ## again checking whether stack is empty or not -> false print(len(stack) == 0) ## printing the stack print(stack) ## popping the topmost element -> 5 stack.pop() ## printing the stack print(stack) ## popping all the elements stack.pop() stack.pop() stack.pop() stack.pop() ## checking the whether stack is empty or not for the last time -> true print(len(stack) == 0)
Ez az. Megtanultuk a verem megvalósítását a gyűjtemények beépített moduljából származó deque segítségével. Az alábbiakban említett kimenetet kapja, ha végrehajtja a fenti programot.
True False deque([1, 2, 3, 4, 5]) deque([1, 2, 3, 4]) True
Eddig két módot láttunk a verem megvalósítására. Vannak más módok a verem megvalósítására? Igen! Lássuk a verem megvalósításának végső módját ebben az oktatóanyagban.
#3. LifoQueue
Maga a LifoQueue név azt mondja, hogy a LIFO elvet követi. Ezért kétség nélkül használhatjuk veremként. A beépített modulsorból származik. A LifoQueue néhány praktikus módszert kínál, amelyek hasznosak a verem megvalósításában. Lássuk őket
- put(data) – hozzáadja vagy elküldi az adatokat a sorba
- get() – eltávolítja vagy kidobja a sor legfelső elemét
- üres() – visszaadja, hogy a verem üres-e vagy sem
- qsize() – a sor hosszát adja vissza
Valósítsuk meg a verem LifoQueue segítségével a sor modulból.
from queue import LifoQueue ## creating LifoQueue object stack = LifoQueue() ## checking whether stack is empty or not -> true print(stack.empty()) ## pushing the elements stack.put(1) stack.put(2) stack.put(3) stack.put(4) stack.put(5) ## again checking whether stack is empty or not -> false print(stack.empty()) ## popping all the elements print(stack.get()) print(stack.get()) print(stack.get()) ## checking the stack size print("Size", stack.qsize()) print(stack.get()) print(stack.get()) ## checking the whether stack is empty or not for the last time -> true print(stack.empty())
Az alábbiakban említett kimenetet akkor kapja meg, ha a fenti programot változtatás nélkül végrehajtja.
True False 5 4 3 Size 2 2 1 True
A Stack alkalmazása
Most már elegendő tudással rendelkezik a veremekről ahhoz, hogy programozási problémákban alkalmazhassa. Nézzünk meg egy problémát, és oldjuk meg egy verem segítségével.
Adott egy kifejezés, írjon programot annak ellenőrzésére, hogy a zárójelek, kapcsos zárójelek, kapcsos kapcsos zárójelek helyesen vannak-e kiegyensúlyozva vagy sem.
Lássunk néhány példát.
Bemenet: „[{}]([])”
Kimenet: Kiegyensúlyozott
Bemenet: „{[}]([])”
Kimenet: Nem kiegyensúlyozott
A verem segítségével megoldhatjuk a fenti problémát. Lássuk a probléma megoldásának lépéseit.
- Hozzon létre egy köteget a karakterek tárolására.
- Ha a kifejezés hossza páratlan, akkor a kifejezés nem kiegyensúlyozott
- Iteráljon a megadott kifejezésen keresztül.
- Ha az aktuális karakter a kezdő zárójel a ( vagy { vagy [, then push it to stack.
- Else if the current character is a closing bracket ) or } or ]majd pattintsa ki a veremből.
- Ha az előugró karakter megegyezik a kezdő zárójellel, akkor folytassa, különben a zárójelek nincsenek kiegyensúlyozva.
- Az iteráció után, ha a verem üres, akkor az egyenlet Kiegyensúlyozott, ellenkező esetben az egyenlet nem kiegyensúlyozott.
A beállított adattípust használhatjuk a zárójeles egyezés ellenőrzésére.
## stack class Stack: def __init__(self): self.elements = [] def push(self, data): self.elements.append(data) return data def pop(self): return self.elements.pop() def peek(self): return self.elements[-1] def is_empty(self): return len(self.elements) == 0 def balance_check(expression): ## checking the length of the expression if len(expression) % 2 != 0: ## not balanced if the length is odd return False ## for checking opening_brackets = set('([{') pairs = set([ ('(',')'), ('[',']'), ('{','}') ]) ## stack initialization stack = Stack() ## iterating through the given expression for bracket in expression: ## checking whether the current bracket is opened or not if bracket in opening_brackets: ## adding to the stack stack.push(bracket) else: ## popping out the last bracket from the stack popped_bracket = stack.pop() ## checking whether popped and current bracket pair if (popped_bracket, bracket) not in pairs: return False return stack.is_empty() if __name__ == '__main__': if balance_check('[{}]([])'): print("Balanced") else: print("Not Balanced") if balance_check('{[}]([])'): print("Balanced") else: print("Not Balanced")
A verem segítségével még sok probléma megoldható. A fenti probléma az egyik. Próbálja meg alkalmazni a verem koncepcióját, ahol úgy gondolja, hogy a legjobban megfelel Önnek.
Következtetés
Jaj! Befejezted az oktatóanyagot. Remélem, nektek is annyira tetszett a bemutató, mint nekem. Ennyi a tutorial.
Boldog kódolást 🙂 👨💻