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

Szerző:
Tweet
Share
Share
Pin

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.

  A privát Wi-Fi MAC-címek letiltása iPhone-on és iPaden

Ó! 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.

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

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.

  Hogyan szerezhet be Robuxot egyszerűen és ingyen

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

Tweet
Share
Share
Pin