Stack-Implementierung in Python verstehen

von

Datenstrukturen spielen in der Programmierwelt eine Schlüsselrolle. Sie helfen uns, unsere Daten so zu organisieren, dass sie effizient genutzt werden können. Der Stack ist eine der einfachsten Datenstrukturen.

Lassen Sie uns etwas über den Stack und seine Implementierung in Python lernen.

Was ist ein Stack?

Ein Stapel ähnelt im wirklichen Leben dem Stapel von Büchern, Stühlen usw. Und es folgt dem Last-in/First-out-Prinzip (LIFO). Es ist die einfachste Datenstruktur. Sehen wir uns das Szenario anhand eines realen Beispiels an.

Nehmen wir an, wir haben einen Stapel Bücher wie folgt.

Wenn wir dann das dritte Buch von oben wollen, müssen wir die ersten beiden Bücher von oben entfernen, um das dritte Buch herauszunehmen. Dabei kommt das oberste Buch als letztes auf den Stapel und kommt zuerst auf den Stapel. Der Datenstrukturstapel folgt dem gleichen Prinzip Last-in/First-out (LIFO) in der Programmierung.

Operationen im Stack

Es gibt hauptsächlich zwei Operationen in einem Stack

1. drücken (Daten)

Fügt die Daten in den Stapel hinzu oder schiebt sie in den Stapel.

2. Pop()

Entfernt oder entfernt das oberste Element aus dem Stapel.

Sehen Sie sich die folgenden Abbildungen von Push- und Pop-Vorgängen an.

Wir werden einige Hilfsfunktionen schreiben, die uns helfen, mehr Informationen über den Stack zu erhalten.

Lass sie uns sehen.

spähen()

Gibt das oberste Element aus dem Stapel zurück.

ist leer()

Gibt zurück, ob der Stack leer ist oder nicht.

Genug konzeptionelle Aspekte der Stack-Datenstruktur. Lassen Sie uns ohne weiteres in die Implementierung springen.

Ich nehme an, Sie haben Python auf Ihrem PC installiert, wenn nicht, können Sie auch den Online-Compiler ausprobieren.

Stack-Implementierung

Das Implementieren von Stack ist im Vergleich zu anderen Datenstrukturimplementierungen am einfachsten. Wir können einen Stapel in Python auf verschiedene Weise implementieren.

Sehen wir uns alle einzeln an.

#1. Aufführen

Wir werden den Stapel mithilfe der Liste in einer Klasse implementieren. Sehen wir uns die schrittweise Implementierung des Stacks an.

Schritt 1: Schreiben Sie eine Klasse namens Stack.

class Stack:
	pass

Schritt 2: Wir müssen die Daten in einer Liste pflegen. Lassen Sie uns eine leere Liste in der Stack-Klasse mit Namenselementen hinzufügen.

class Stack:
	def __init__(self):
		self.elements = []

Schritt 3: Um die Elemente in den Stack zu schieben, brauchen wir eine Methode. Lassen Sie uns eine Push-Methode schreiben, die Daten als Argument akzeptiert und an die Elementliste anhängt.

class Stack:
	def __init__(self):
		self.elements = []

	def push(self, data):
		self.elements.append(data)
		return data

Schritt 4: Lassen Sie uns auf ähnliche Weise die Pop-Methode schreiben, die das oberste Element aus dem Stapel herausholt. Wir können die Pop-Methode des Listendatentyps verwenden.

class Stack:
	## ...
	def pop(self):
		return self.elements.pop()

Wir haben die Stack-Implementierung mit den erforderlichen Operationen abgeschlossen. Lassen Sie uns nun die Hilfsfunktionen hinzufügen, um mehr Informationen über den Stapel zu erhalten.

Schritt 5: Mit dem negativen Index können wir das oberste Element aus dem Stapel holen. Das Codeelement [-1] gibt den letzten der Liste zurück. In unserem Fall ist es das oberste Element des Stacks.

class Stack:
	## ...

	def peek(self):
		return self.elements[-1]

Schritt 6: Wenn die Länge der Elementliste 0 ist, dann ist der Stack leer. Lassen Sie uns eine Methode schreiben, die zurückgibt, ob das Element leer ist oder nicht.

class Stack:
	## ...
	def is_empty(self):
		return len(self.elements) == 0

Wir haben die Implementierung des Stapels mit dem Listendatentyp abgeschlossen.

  So kündigen Sie Ihr Stadia Pro-Abo

Oh! warte, wir haben es gerade implementiert. Aber ich habe nicht gesehen, wie man es benutzt. Wie benutzt man es dann?

Mal sehen, wie man es umsetzt. Wir müssen ein Objekt erstellen, damit die Stack-Klasse es verwenden kann. Es ist keine große Sache. Lass es uns zuerst tun.

class Stack: 
    ## ...

if __name__ == '__main__':
    stack = Stack()

Wir haben das Stack-Objekt erstellt und können es verwenden. Führen Sie die folgenden Schritte aus, um Stapeloperationen zu testen.

  • Prüfen Sie mit der Methode is_empty, ob der Stack leer ist oder nicht. Es sollte True zurückgeben.
  • Schieben Sie die Zahlen 1, 2, 3, 4, 5 mit der Push-Methode in den Stapel.
  • Die Methode is_empty sollte False zurückgeben. Prüfen Sie.
  • Drucken Sie das oberste Element mit der Peek-Methode.
  • Entnehmen Sie das Element mit der Pop-Methode aus dem Stapel.
  • Überprüfen Sie das Peek-Element. Es sollte das Element 4 zurückgeben.
  • Entfernen Sie nun alle Elemente aus dem Stapel.
  • Die is_empty-Methode sollte True zurückgeben. Prüfen Sie.

Unsere Stack-Implementierung ist abgeschlossen, wenn sie alle oben genannten Schritte besteht. Versuchen Sie, den Code für die obigen Schritte zu schreiben.

Hast du den Code geschrieben? Nein, keine Sorge, überprüfen Sie den Code unten.

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())

Hurra! Wir haben die Stack-Implementierung von Grund auf mit dem Listendatentyp abgeschlossen. Sie sehen die Ausgabe wie unten erwähnt, wenn Sie den obigen Code ausführen.

True
False
5
4
True

Wir können den Listendatentyp direkt als Stack verwenden. Die obige Implementierung von Stack hilft Ihnen, die Stack-Implementierung auch in anderen Programmiersprachen zu verstehen.

Sie können sich auch diese Artikel zu Listen ansehen.

Sehen wir uns die eingebaute deque aus dem eingebauten Modul collections an, die als Stack fungieren kann.

  Was sind die 7DS Grand Cross Geheimbox-Codes?

#2. Deque aus Sammlungen

Sie ist als doppelseitige Warteschlange implementiert. Da es das Hinzufügen und Entfernen von Elementen von beiden Seiten unterstützt. Daher können wir es als Stack verwenden. Wir können es dem LIFO-Prinzip des Stapels folgen lassen.

Es wird unter Verwendung anderer Datenstrukturen implementiert, die als doppelt verknüpfte Liste bezeichnet werden. Die Leistung beim Einfügen und Löschen von Elementen ist also konsistent. Der Zugriff auf Elemente aus der mittleren verknüpften Liste dauerte O(n) Zeit. Wir können es als Stack verwenden, da auf die mittleren Elemente nicht vom Stack aus zugegriffen werden muss.

Sehen wir uns vor der Implementierung des Stapels die Methoden an, die zum Implementieren des Stapels mithilfe der Warteschlange verwendet werden.

  • append(data) – wird verwendet, um die Daten auf den Stack zu schieben
  • pop() – wird verwendet, um das oberste Element aus dem Stapel zu entfernen

Es gibt keine alternativen Methoden für peek und is_empty. Wir können den gesamten Stapel anstelle der Peek-Methode drucken. Als nächstes können wir die Methode len verwenden, um zu prüfen, ob der Stack leer ist oder nicht.

Lassen Sie uns den Stapel mit deque aus dem Sammlungsmodul implementieren.

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)

Das ist es. Wir haben gelernt, wie man Stack mit der Deque aus dem integrierten Collections-Modul implementiert. Sie erhalten die unten erwähnte Ausgabe, wenn Sie das obige Programm ausführen.

True
False
deque([1, 2, 3, 4, 5])
deque([1, 2, 3, 4])
True

Bisher haben wir zwei Möglichkeiten gesehen, den Stack zu implementieren. Gibt es andere Möglichkeiten, einen Stack zu implementieren? Ja! Sehen wir uns in diesem Tutorial die endgültige Möglichkeit zum Implementieren eines Stacks an.

#3. LifoQueue

Der Name LifoQueue sagt schon, dass es dem LIFO-Prinzip folgt. Daher können wir es ohne Zweifel als Stack verwenden. Es stammt aus der integrierten Modulwarteschlange. Die LifoQueue bietet einige praktische Methoden, die bei der Stack-Implementierung nützlich sind. Lass sie uns sehen

  • put(data) – fügt die Daten der Warteschlange hinzu oder schiebt sie in die Warteschlange
  • get() – entfernt oder holt das oberste Element aus der Warteschlange
  • empty() – gibt zurück, ob der Stack leer ist oder nicht
  • qsize() – gibt die Länge der Warteschlange zurück

Lassen Sie uns den Stapel mit LifoQueue aus dem Warteschlangenmodul implementieren.

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())

Sie erhalten die unten erwähnte Ausgabe, wenn Sie das obige Programm ausführen, ohne es zu ändern.

True
False
5
4
3
Size 2
2
1
True

Anwendung von Stack

Jetzt haben Sie genügend Wissen über Stacks, um es bei Programmierproblemen anzuwenden. Sehen wir uns ein Problem an und lösen es mit einem Stack.

  Food Builder gibt Ihnen Nährwertinformationen basierend auf Ihren Zutaten

Schreiben Sie für einen gegebenen Ausdruck ein Programm, um zu prüfen, ob die Klammern, geschweiften und geschweiften Klammern korrekt ausbalanciert sind oder nicht.

Sehen wir uns einige Beispiele an.

Eingabe: „[{}]([])“

Ausgang: Ausgeglichen

Eingabe: „{[}]([])“

Ausgang: Nicht symmetrisch

Wir können den Stapel verwenden, um das obige Problem zu lösen. Sehen wir uns die Schritte zur Lösung des Problems an.

  • Erstellen Sie einen Stapel, um die Zeichen zu speichern.
  • Wenn die Länge des Ausdrucks ungerade ist, ist der Ausdruck nicht ausgeglichen
  • Durchlaufen Sie den angegebenen Ausdruck.
    • Wenn das aktuelle Zeichen die öffnende Klammer von ( oder { oder [, then push it to stack.
    • Else if the current character is a closing bracket ) or } or ]dann vom Stapel springen.
    • Wenn das geknallte Zeichen mit der Startklammer übereinstimmt, fahren Sie fort, sonst sind die Klammern nicht ausgeglichen.
  • Wenn der Stapel nach der Iteration leer ist, ist die Gleichung ausgeglichen, andernfalls ist die Gleichung nicht ausgeglichen.

Wir können den eingestellten Datentyp für die Übereinstimmungsprüfung von Klammern verwenden.

## 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")

Wir können den Stapel verwenden, um viele weitere Probleme zu lösen. Das obige Problem ist eines davon. Versuchen Sie, das Stack-Konzept dort anzuwenden, wo es Ihrer Meinung nach am besten zu Ihnen passt.

Fazit

Yah! Sie haben das Lernprogramm abgeschlossen. Ich hoffe, Sie haben das Tutorial genauso genossen wie ich, während ich es mache. Das war’s für das Tutorial.

Viel Spaß beim Programmieren 🙂 👨‍💻