Datové struktury jsou souborem datových hodnot, vztahů mezi nimi a funkcí nebo operací, které lze na data použít. Nyní je k dispozici spousta datových struktur. Ale dnes se budeme soustředit na Stack Data Structures. Budu diskutovat o následujících tématech:
- Proč datové struktury?
- Typy datových struktur
- Co je to Stack Data Structure?
- Vytvoření datové struktury zásobníku
- Zatlačte prvky do zásobníku
- Popové prvky ze zásobníku
- Aplikace datové struktury zásobníku
Proč datové struktury?
Chcete-li na to odpovědět, budete muset přemýšlet na velké úrovni. Přemýšlejte, jak vám Google mapy ukazují nejlepší trasu za pouhý zlomek sekund, jak vám vrátí výsledek vyhledávání v mikrosekundách. Nezabývá se pouze 100 webovými stránkami, zabývá se více než miliardami webů a stále vám ukazuje výsledky tak rychle.
I když použitý algoritmus hraje zásadní roli, základem tohoto algoritmu je datová struktura nebo použitý kontejner. V jakékoli aplikaci je organizování a ukládání dat způsobem nebo ve struktuře, která je nejvhodnější pro jeho použití, klíčem k efektivnímu přístupu a zpracování dat.
Typy datových struktur
Existuje několik standardních datových struktur, které lze použít k efektivní práci s daty. Můžeme je dokonce přizpůsobit nebo vytvořit zcela nové, aby vyhovovaly naší aplikaci.
Co je to Stack Data Structure?
Zvažte několik příkladů z reálného života:
- Zásilka v nákladu
- Talíře na podnose
- Hromadu mincí
- Stoh zásuvek
- Posun vlaků v kolejišti
Všechny tyto příklady následují a Last-In-First-Out strategie. Vezměte v úvahu talíře na tácku. Pokud chcete vybrat talíř, jste nuceni vybrat talíř shora, zatímco když byly talíře drženy na talíři, musí být v opačném pořadí. Nad příklady, které následují Last-In-First-Out (LIFO) princip jsou známy jako Zásobník .
Kromě doplňkových operací mohu říci, že hlavní možné operace v zásobníku jsou:
- Zatlačte nebo vložte prvek do horní části stohu
- Vysuňte nebo odeberte prvek z horní části zásobníku
Vytvoření datové struktury zásobníku
třída Stack: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ top = -1
- max_size je maximální počet prvků očekávaných v zásobníku.
- Prvky zásobníku jsou uloženy v seznamu pythonů.
- Nahoře označuje nejvyšší index zásobníku, který je původně odebrán -1 k označení prázdného zásobníku.
Počáteční stav zásobníku je vidět na obrázku, kde max_size = 5
Zatlačte prvek do zásobníku
Nyní, pokud chcete zadat nebo posunout prvek do zásobníku, musíte si to pamatovat
- Horní část bude ukazovat na index, do kterého bude prvek vložen.
- A že žádný prvek nebude vložen, když je zásobník plný, tj. Když max_size = top.
Jaký by měl být algoritmus?
# vrací maximální velikost zásobníku def get_max_size (self): return self .__ max_size # vrací bool hodnotu, ať už je zásobník plný nebo ne, True pokud je plný a False jinak def is_full (self): return self.get_max_size () - 1 == self .__ top #pushes element v horní části zásobníku def push (self, data): if (self.is_full ()): print ('stack is already full') else: self .__ top = self .__ top + int (1 ) self .__ elements [self .__ top] = data # Následující __str __ () můžete použít k tisku prvků objektu DS při ladění def __str __ (self): msg = [] index = self .__ top while (index> = 0): msg.append ((str) (self .__ elements [index])) index- = 1 msg = '' .join (msg) msg = 'Stack data (top to bottom):' + msg return msgNyní, když provedete následující:
nastavení cesty třídy v Javě
stack1 = Stack (4)
# Zatlačte všechny požadované prvky.
stack1.push („A“)
stack1.push („B“)
stack1.push („C“)
stack1.push („E“)
print (stack1.is_full ())
tisk (stoh1)
Výstup:
zásobník je již plný
Skutečný
Data zásobníku (shora dolů): D C B A
Popové prvky ze zásobníku
Nyní, když jste vložili prvky do zásobníku, je chcete vyskočit, takže je třeba se postarat o následující:
- Zásobník není prázdný, tj. Nahoře! = -1
- Když odstraníte data, horní část musí ukazovat na předchozí horní část zásobníku.
Jaký bude tedy algoritmus ??
#returns bool hodnota, zda je zásobník prázdný nebo ne, True, pokud je prázdný, a False, jinak 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): pro i v rozsahu (self .__ top, -1, -1): print (self .__ elements [i], end = '') print ()Nyní, vzhledem k dříve vytvořenému zásobníku, zkuste popovat prvky
print (stack1.pop ())
print (stack1.pop ())
tisk (stoh1)
print (stack1.pop ())
print (stack1.pop ())
print (stack1.pop ())
jak inicializovat objekt v pythonu
Výstup:
D
C
Stack data (shora dolů): B A
B
NA
pole objektů java příklad
nic k prasknutí, už prázdné
Aplikace datové struktury zásobníku
- Příklad 1:
Zásobník se používá k implementaci algoritmu párování závorek pro vyhodnocení aritmetického výrazu a také při implementaci volání metod.
Odpověď na kterou je 5.
- Příklad 2:
Schránka ve Windows používá dva zásobníky k implementaci operací zpět a znovu (ctrl + z, ctrl + y). Pracovali byste na textových editorech Windows, jako je MS-Word, Poznámkový blok atd. Zde je text psaný v MS-Wordu. Sledujte, jak se text změnil kliknutím Ctrl-Z a Ctrl-Y.
Zde je kód, který simuluje operaci vrácení zpět. Projděte si kód a sledujte, jak se zásobník používá v této implementaci.
#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ázdný! ! ') else: data = self .__ elements [self .__ top] self .__ top- = 1 return data def display (self): if (self.is_empty ()): print (' The 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žít níže uvedený __str __ () k tisku prvků Objekt DS při ladění def __str __ (self): msg = [] index = self .__ top while (index> = 0): msg.append ((str) (self .__ elements [index])) index- = 1 msg = ' '.join (msg) msg =' Stack data (shora dolů): '+ msg vrátit ms g #funkce implementace operace odebrání nebo backspace def remove (): globální schránka, undo_stack data = schránka [len (schránka) -1] clipboard.remove (data) undo_stack.push (data) tisk ('Odstranit:', schránka) #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 implementovat operaci redo def redo (): globální schránka, undo_stack, redo_stack if (redo_stack.is_empty ()): print ('Neexistují žádná data to redo ') else: data = redo_stack.pop () if (data nejsou ve schránce): print (' Neexistují žádná data k opakování ') 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ýstup:
Odstranit: [„A“, „B“, „C“, „D“, „E“]
Zpět: [„A“, „B“, „C“, „D“, „E“, „F“]
Znovu: [„A“, „B“, „C“, „D“, „E“]
S tímto se dostáváme na konec této Stack Data Structure v článku v Pythonu. Pokud jste úspěšně pochopili a spustili kódy sami, už nejste nováčkem v Stacks Data Structure.
Máte na nás dotaz? Uveďte to prosím v sekci komentářů tohoto článku a my se vám ozveme co nejdříve.
Chcete-li získat podrobné znalosti o Pythonu a jeho různých aplikacích, můžete se zaregistrovat naživo s nepřetržitou podporou a doživotním přístupem.