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.
Tartalomjegyzék
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 🙂 👨💻
