Čo sú to stackové dátové štruktúry v Pythone?



Tento článok vám poskytne podrobné a komplexné znalosti o dátových štruktúrach zásobníka v Pythone s mnohými príkladmi.

Dátové štruktúry sú súborom údajových hodnôt, vzťahov medzi nimi a funkcií alebo operácií, ktoré je možné na údaje použiť. Teraz je k dispozícii veľa dátových štruktúr. Ale dnes sa zameriame na Stack Data Structures. Budem diskutovať o nasledujúcich témach:

Prečo dátové štruktúry?

Aby ste na to odpovedali, budete musieť premýšľať na veľkej úrovni. Popremýšľajte, ako vám mapy Google ukážu najlepšiu trasu už za zlomok sekúnd, ako vám vráti výsledok vyhľadávania v mikrosekundách. Nezaoberá sa iba 100 webovými stránkami, zaoberá sa viac ako miliardou webov a stále vám ukazuje výsledky tak rýchlo.





Aj keď použitý algoritmus hrá rozhodujúcu úlohu, základom tohto algoritmu je dátová štruktúra alebo použitý kontajner. V každej aplikácii je organizovanie a ukladanie údajov spôsobom alebo v štruktúre, ktorá je najvhodnejšia na ich použitie, kľúčom k efektívnemu prístupu a spracovaniu údajov.

Typy dátových štruktúr

Existuje niekoľko štandardných dátových štruktúr, ktoré možno použiť na efektívnu prácu s dátami. Môžeme ich dokonca prispôsobiť alebo vytvoriť úplne nové, aby vyhovovali našej aplikácii.



Typy dátových štruktúr

Čo je to Stack Data Structure?

Zvážte niekoľko príkladov z reálneho života:

  • Preprava v náklade
  • Dosky na podnose
  • Hromada mincí
  • Stoh zásuviek
  • Posun vlakov v koľajisku

plates-stacks-data-structure



Všetky tieto príklady nasledujú a Last-In-First-Out stratégia. Zvážte doštičky na podnose. Ak chcete vybrať doštičku, ste nútení vybrať doštičku zhora, zatiaľ čo keď sa doštičky držali na podnose, musia byť v opačnom poradí. Vyššie uvedené príklady, ktoré nasledujú Last-In-First-Out (LIFO) princíp sú známe ako Stoh .

Okrem doplnkových operácií môžem povedať, že hlavné možné operácie v zásobníku sú:

  1. Zatlačte alebo vložte prvok do hornej časti stohu
  2. Vysuňte alebo odstráňte prvok z hornej časti stohu

Vytvorenie dátovej štruktúry zásobníka

trieda Zásobník: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ top = -1
  • max_size je maximálny počet prvkov očakávaných v zásobníku.
  • Prvky zásobníka sú uložené v zozname pythónov.
  • Hore označuje najvyšší index zásobníka, ktorý sa pôvodne berie ako -1 na označenie prázdneho zásobníka.

Počiatočný stav zásobníka je viditeľný na obrázku, kde max_size = 5

Zatlačte prvok do stohu

Teraz, ak chcete vložiť alebo posunúť prvok do zásobníka, musíte si to uvedomiť

  • Horná časť bude ukazovať na index, do ktorého bude vložený prvok.
  • A že nebude vložený žiadny prvok, keď je zásobník plný, tj. Keď max_size = top.

Aký by mal byť teda algoritmus ??

# vráti maximálnu veľkosť stohu def get_max_size (self): return self .__ max_size # vráti boolovú hodnotu bez ohľadu na to, či je zásobník plný alebo nie, True ak je plný a False inak def is_full (self): return self.get_max_size () - 1 == self .__ top # posúva prvok do hornej časti zásobníka def push (self, data): if (self.is_full ()): print ('zásobník je už plný') else: self .__ top = self .__ top + int (1 ) self .__ elements [self .__ top] = data # Môžete použiť nasledujúci __str __ () na tlač prvkov DS objektu počas ladenia def __str __ (self): msg = [] index = self .__ top while (index> = 0): msg.append ((str) (self .__ elements [index])) index- = 1 msg = '' .join (msg) msg ​​= 'Stack data (zhora nadol):' + msg návratová správa

Teraz, keď vykonáte nasledujúce:

ako ukončiť program

stack1 = Stack (4)

# Zatlačte všetky požadované prvky.

stack1.push („A“)

stack1.push („B“)

stack1.push („C“)

stack1.push („E“)

print (stack1.is_full ())

tlačiť (stoh1)

Výkon:

zásobník je už plný
Pravdaže
Údaje o zásobníku (zhora nadol): D C B A

Popové prvky zo zásobníka

Teraz, keď ste vložili prvky do zásobníka, chcete ich vyskočiť, takže je potrebné dbať na nasledovné:

  • Zásobník nie je prázdny, t. J. Top! = -1
  • Keď odstránite údaje, horná časť musí smerovať k predchádzajúcej hornej časti stohu.

Aký bude teda algoritmus?

#returns bool hodnota, či je zásobník prázdny alebo nie, True ak je prázdny a False inak def is_empty (self): return self .__ top == - 1 #returns popped value def pop (self): if (self.is_empty ()): print ('nothing to pop, already empty') else: a = self .__ elements [self .__ top] self .__ top = self .__ top-1 return a #display all the stack elements from top to bottom def display (self): pre i v rozsahu (self .__ top, -1, -1): print (self .__ elements [i], end = '') print ()

Teraz, berúc do úvahy predtým vytvorený zásobník, skúste popové prvky

print (stack1.pop ())

print (stack1.pop ())

tlačiť (stoh1)

print (stack1.pop ())

print (stack1.pop ())

print (stack1.pop ())

implementácia hashmap v java príklade

Výkon:

D

C.

Údaje o zásobníku (zhora nadol): B A

B

TO

popis úlohy správcu systému linux

nič, čo by vyskočilo, už prázdne

Aplikácie dátovej štruktúry zásobníka

  • Príklad 1:

Zásobník sa používa na implementáciu algoritmu párovania zátvoriek na vyhodnotenie aritmetického výrazu a tiež na implementáciu volaní metód.

Odpoveď na ktorú je 5.

  • Príklad 2:

Schránka vo Windows používa dva stohy na implementáciu operácií undo-redo (ctrl + z, ctrl + y). Pracovali by ste na textových editoroch Windows, ako sú MS-Word, Poznámkový blok atď. Tu je text napísaný v MS-Word. Sledujte, ako sa text zmenil po kliknutí na klávesy Ctrl-Z a Ctrl-Y.

Tu je kód, ktorý simuluje operáciu vrátenia späť. Prejdite si kód a sledujte, ako sa zásobník používa v tejto implementácii.

#creating class stack class Stack: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ top = -1 def is_full (self): if (self .__ top == self .__ max_size-1): return True return False def is_empty (self): if (self .__ top == - 1): return True return False def push (self, data): if (self.is_full ()): print ('Zásobník je plný !!') else: self .__ top + = 1 self .__ elements [self .__ top] = data def pop (self): if (self.is_empty ()): print ('Zásobník je prázdny! ! ') else: data = self .__ elements [self .__ top] self .__ top- = 1 return data def display (self): if (self.is_empty ()): print (' Stack is empty ') else: index = self .__ top while (index> = 0): print (self .__ elements [index]) index- = 1 def get_max_size (self): return self .__ max_size # Môžete použiť nasledujúci __str __ () na vytlačenie prvkov Objekt DS počas ladenia def __str __ (self): msg = [] index = self .__ top while (index> = 0): msg.append ((str) (self .__ elements [index])) index- = 1 msg = ' '.join (msg) msg ​​=' Zostaviť dáta (zhora nadol): '+ msg vrátiť ms g #function to implement remove or backspace operation def remove (): global clipboard, undo_stack data = clipboard [len (clipboard) -1] clipboard.remove (data) undo_stack.push (data) print ('Remove:', clipboard) #function to implement undo operation def undo (): global clipboard, undo_stack, redo_stack if (undo_stack.is_empty ()): print ('There are no data to undo') else: data = undo_stack.pop () clipboard.append ( data) redo_stack.push (data) print ('Undo:', schránka) #funkce na vykonanie operácie redo def redo (): globálna schránka, undo_stack, redo_stack if (redo_stack.is_empty ()): print ('Neexistujú žiadne dáta to redo ') else: data = redo_stack.pop () if (data nie sú v schránke): print (' Neexistujú žiadne dáta na opakovanie ') redo_stack.push (data) else: clipboard.remove (data) undo_stack.push ( data) print ('Znovu:', schránka) clipboard = ['A', 'B', 'C', 'D', 'E', 'F'] undo_stack = Zásobník (len (schránka)) redo_stack = Zásobník (len (schránka)) remove () undo () redo ()

Výkon:

Odstrániť: [„A“, „B“, „C“, „D“, „E“]

Späť: [„A“, „B“, „C“, „D“, „E“, „F“]

Znova: [„A“, „B“, „C“, „D“, „E“]

Týmto sa dostávame na koniec tohto článku Stack Data Structure in Python. Ak ste úspešne pochopili a spustili kódy sami, už nie ste v Stacks Data Structure nováčikom.

Máte na nás otázku? Uveďte to prosím v sekcii komentárov tohto článku a my sa vám ozveme čo najskôr.

Ak chcete získať podrobné informácie o Pythone a jeho rôznych aplikáciách, môžete sa zaregistrovať naživo s nepretržitou podporou a doživotným prístupom.