Was sind Stapeldatenstrukturen in Python?



Dieser Artikel bietet Ihnen ein detailliertes und umfassendes Wissen über Stapeldatenstrukturen in Python mit vielen Beispielen.

Datenstrukturen sind eine Sammlung von Datenwerten, den Beziehungen zwischen ihnen und den Funktionen oder Operationen, die auf die Daten angewendet werden können. Jetzt sind viele Datenstrukturen verfügbar. Heute konzentrieren wir uns jedoch auf Stack-Datenstrukturen. Ich werde die folgenden Themen diskutieren:

Warum Datenstrukturen?

Um dies zu beantworten, müssen Sie auf einer großen Ebene denken. Überlegen Sie, wie Google Maps Ihnen in Sekundenbruchteilen die beste Route anzeigt und wie Sie Ihr Suchergebnis in Mikrosekunden zurückgeben. Es werden nicht nur 100 Websites behandelt, sondern mehr als eine Milliarde Websites, und es werden immer noch so schnelle Ergebnisse angezeigt.





Nun, obwohl der verwendete Algorithmus eine entscheidende Rolle spielt, ist die Datenstruktur oder der verwendete Container die Grundlage dieses Algorithmus. In jeder Anwendung ist das Organisieren und Speichern von Daten auf eine Weise oder in einer Struktur, die für ihre Verwendung am besten geeignet ist, der Schlüssel für einen effizienten Zugriff und eine effiziente Verarbeitung von Daten.

Arten von Datenstrukturen

Es gibt einige Standarddatenstrukturen, mit denen effizient mit Daten gearbeitet werden kann. Wir können sie sogar an unsere Anwendung anpassen oder komplett neue erstellen.



Datenstrukturtypen

Was ist Stack-Datenstruktur?

Betrachten Sie einige Beispiele aus der Praxis:

  • Versand in Fracht
  • Teller auf einem Tablett
  • Münzstapel
  • Stapel Schubladen
  • Rangieren von Zügen in einem Bahnhof

plates-stacks-data-structure



Alle diese Beispiele folgen a Zuletzt rein, zuerst raus Strategie. Betrachten Sie Platten auf einem Tablett. Wenn Sie einen Teller auswählen möchten, müssen Sie einen Teller von oben auswählen, während die Platten in umgekehrter Reihenfolge sein müssen, wenn sie auf dem Tablett aufbewahrt wurden. Oben Beispiele, die dem folgen Last-In-First-Out (LIFO) Prinzip sind bekannt als Stapel .

Abgesehen von den komplementären Operationen kann ich sagen, dass die wichtigsten Operationen, die auf dem Stapel möglich sind, sind:

  1. Schieben oder setzen Sie ein Element oben auf den Stapel
  2. Pop oder entfernen Sie ein Element von der Oberseite des Stapels

Stapeldatenstruktur erstellen

Klassenstapel: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ top = -1
  • maximale Größe ist die maximale Anzahl von Elementen, die im Stapel erwartet werden.
  • Elemente des Stapels werden in der Python-Liste gespeichert.
  • Oben gibt den obersten Index des Stapels an, der anfänglich mit -1 belegt wird, um einen leeren Stapel zu markieren.

Der Anfangsstatus des Stapels ist in der Abbildung zu sehen, in der max_size = 5 ist

Schieben Sie das Element in den Stapel

Wenn Sie nun ein Element in den Stapel eingeben oder verschieben möchten, müssen Sie sich daran erinnern

  • Oben wird der Index angezeigt, in den das Element eingefügt wird.
  • Und dass kein Element eingefügt wird, wenn der Stapel voll ist, d. H. Wenn max_size = top ist.

Also, was sollte der Algorithmus sein?

# gibt die maximale Größe des Stapels zurück def get_max_size (self): return self .__ max_size # gibt den Bool-Wert zurück, ob der Stack voll ist oder nicht, True wenn voll und False andernfalls def is_full (self): return self.get_max_size () - 1 == self .__ top #pushes Element am oberen Rand des Stapels def push (self, data): if (self.is_full ()): print ('Stapel ist bereits voll') else: self .__ top = self .__ top + int (1 ) self .__ elements [self .__ top] = data #Sie können das folgende __str __ () verwenden, um die Elemente des DS-Objekts beim Debuggen von def __str __ (self) zu drucken: msg = [] index = self .__ top while (index> = 0): msg.append ((str) (self .__ elements [index])) index- = 1 msg = '' .join (msg) msg ​​= 'Stapeldaten (von oben nach unten):' + msg return msg

Nun, wenn Sie Folgendes ausführen:

Namespace in c ++

stack1 = Stack (4)

#Drücken Sie alle erforderlichen Elemente.

stack1.push ('A')

stack1.push ('B')

stack1.push ('C')

stack1.push ('E')

print (stack1.is_full ())

print (stack1)

Ausgabe:

Stapel ist bereits voll
Wahr
Stapeldaten (von oben nach unten): D C B A.

Unterschied zwischen flacher Kopie und tiefer Kopie in Java

Pop-Elemente aus dem Stapel

Nachdem Sie die Elemente in den Stapel eingefügt haben, möchten Sie sie einfügen. Daher müssen Sie Folgendes beachten:

  • Der Stapel ist nicht leer, d. H. Oben! = -1
  • Wenn Sie die Daten löschen, muss die Oberseite auf die vorherige Oberseite des Stapels zeigen.

Also, was wird der Algorithmus sein?

# gibt den Bool-Wert zurück, ob der Stapel leer ist oder nicht, True, wenn leer und False, sonst def is_empty (self): return self .__ top == - 1 #returns popped value def pop (self): if (self.is_empty ()): print ('nichts zu knallen, bereits leer') else: a = self .__ elements [self .__ top] self .__ top = self .__ top-1 gibt ein #display aller Stapelelemente von oben nach unten zurück def display (self): für i im Bereich (self .__ top, -1, -1): print (self .__ elements [i], end = '') print ()

Versuchen Sie nun, unter Berücksichtigung des zuvor erstellten Stapels, Elemente zu platzieren

print (stack1.pop ())

print (stack1.pop ())

print (stack1)

print (stack1.pop ())

print (stack1.pop ())

print (stack1.pop ())

Ausgabe:

D.

C.

Stapeldaten (von oben nach unten): B A.

B.

ZU

nichts zu knallen, schon leer

Anwendungen der Stack-Datenstruktur

  • Beispiel 1:

Ein Stapel wird verwendet, um einen Bracket-Matching-Algorithmus für die Auswertung arithmetischer Ausdrücke und auch für die Implementierung von Methodenaufrufen zu implementieren.

Antwort auf die ist 5.

  • Beispiel 2:

Zwischenablage in Windows Verwendet zwei Stapel, um Undo-Redo-Operationen (Strg + Z, Strg + Y) zu implementieren. Sie hätten an Windows-Worteditoren wie MS-Word, Notepad usw. gearbeitet. Hier ist ein Text, der in MS-Word geschrieben ist. Beobachten Sie, wie sich der Text beim Klicken von Strg-Z und Strg-Y geändert hat.

Hier ist ein Code, der das Wiederherstellen und Wiederherstellen simuliert. Gehen Sie den Code durch und beobachten Sie, wie der Stapel in dieser Implementierung verwendet wird.

#creating class stack class Stapel: 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 ('Der Stapel ist voll !!') else: self .__ top + = 1 self .__ elements [self .__ top] = data def pop (self): if (self.is_empty ()): print ('Der Stapel ist leer! ! ') else: data = self .__ elements [self .__ top] self .__ top- = 1 return data def display (self): if (self.is_empty ()): print (' Der Stapel ist leer ') else: index = self .__ top while (index> = 0): print (self .__ elements [index]) index- = 1 def get_max_size (self): return self .__ max_size #Sie können das folgende __str __ () verwenden, um die Elemente des zu drucken DS-Objekt beim Debuggen def __str __ (self): msg = [] index = self .__ top while (index> = 0): msg.append ((str) (self .__ elements [index])) index- = 1 msg = ' '.join (msg) msg ​​=' Stapeldaten (von oben nach unten): '+ msg return ms g #Funktion zum Implementieren der Operation zum Entfernen oder Zurücksetzen def remove (): globale Zwischenablage, undo_stack data = clipboard [len (Zwischenablage) -1] clipboard.remove (Daten) undo_stack.push (Daten) print ('Remove:', Zwischenablage) #Funktion zum Implementieren der Undo-Operation def undo (): globale Zwischenablage, undo_stack, redo_stack if (undo_stack.is_empty ()): print ('Es sind keine Daten rückgängig zu machen') else: data = undo_stack.pop () clipboard.append ( data) redo_stack.push (data) print ('Undo:', Zwischenablage) # Funktion zum Implementieren der Wiederherstellungsoperation def redo (): globale Zwischenablage, undo_stack, redo_stack if (redo_stack.is_empty ()): print ('Es sind keine Daten vorhanden zu wiederholen ') else: data = redo_stack.pop () if (Daten nicht in der Zwischenablage): print (' Es sind keine Daten zu wiederholen ') redo_stack.push (Daten) else: clipboard.remove (Daten) undo_stack.push ( data) print ('Redo:', Zwischenablage) clipboard = ['A', 'B', 'C', 'D', 'E', 'F'] undo_stack = Stack (len (Zwischenablage)) redo_stack = Stack (len (Zwischenablage)) remove () rückgängig machen () wiederholen ()

Ausgabe:

Entfernen Sie: ['A', 'B', 'C', 'D', 'E']

wie man in Java nach Palindrom sucht

Rückgängig machen: ['A', 'B', 'C', 'D', 'E', 'F']

Wiederholen: ['A', 'B', 'C', 'D', 'E']

Damit sind wir am Ende dieser Stack-Datenstruktur in Python-Artikel angelangt. Wenn Sie die Codes erfolgreich verstanden und selbst ausgeführt haben, sind Sie kein Neuling mehr in der Stacks-Datenstruktur.

Hast du eine Frage an uns? Bitte erwähnen Sie es im Kommentarbereich dieses Artikels und wir werden uns so schnell wie möglich bei Ihnen melden.

Um detaillierte Informationen zu Python und seinen verschiedenen Anwendungen zu erhalten, können Sie sich live anmelden mit 24/7 Support und lebenslangem Zugriff.