A verem implementáció megértése Pythonban

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.

  Yahoo e-mail cím megváltoztatása

Ó! 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 privát Wi-Fi MAC-címek letiltása iPhone-on és iPaden

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.

  Zenei streaming szolgáltatás használata riasztásként Androidon

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 🙂 👨‍💻