A stapel is een lineaire datastructuur die items opslaat in a Laatste in/eerste uit (LIFO) of First-In/Last-Out (FILO) manier. Bij stapelen wordt aan één uiteinde een nieuw element toegevoegd en alleen aan dat uiteinde wordt een element verwijderd. De invoeg- en verwijderbewerkingen worden vaak push en pop genoemd.

De functies die verband houden met stapelen zijn:

• leeg() – Geeft terug of de stapel leeg is – Tijdcomplexiteit: O(1)
• maat() – Geeft de grootte van de stapel terug – Tijdcomplexiteit: O(1)
• top() / kijkje() – Geeft een verwijzing terug naar het bovenste element van de stapel – Tijdcomplexiteit: O(1)
• duwen(een) – Voegt het element ‘a’ bovenaan de stapel in – Tijdcomplexiteit: O(1)
• knal() – Verwijdert het bovenste element van de stapel – Tijdcomplexiteit: O(1)

Implementatie:

Er zijn verschillende manieren waarop een stack in Python kan worden geïmplementeerd. Dit artikel behandelt de implementatie van een stapel met behulp van datastructuren en modules uit de Python-bibliotheek.
Stack in Python kan op de volgende manieren worden geïmplementeerd:

• lijst
• Collecties.deque
• wachtrij.LifoQueue

Implementatie met behulp van lijst:

De ingebouwde datastructuurlijst van Python kan als stapel worden gebruikt. In plaats van push() wordt append() gebruikt om elementen bovenaan de stapel toe te voegen, terwijl pop() het element in LIFO-volgorde verwijdert.
Helaas heeft de lijst een aantal tekortkomingen. Het grootste probleem is dat het snelheidsproblemen kan tegenkomen naarmate het groeit. De items in de lijst worden naast elkaar in het geheugen opgeslagen. Als de stapel groter wordt dan het geheugenblok dat deze momenteel bevat, moet Python wat geheugentoewijzingen uitvoeren. Dit kan ertoe leiden dat sommige append()-aanroepen veel langer duren dan andere.

# Python program to # demonstrate stack implementation # using list stack = [] # append() function to push # element in the stack stack.append('a') stack.append('b') stack.append('c') print('Initial stack') print(stack) # pop() function to pop # element from stack in # LIFO order print('
Elements popped from stack:') print(stack.pop()) print(stack.pop()) print(stack.pop()) print('
Stack after elements are popped:') print(stack) # uncommenting print(stack.pop()) # will cause an IndexError # as the stack is now empty>

Initial stack ['a', 'b', 'c'] Elements popped from stack: c b a Stack after elements are popped: []>

Implementatie met collections.deque:

Python-stack kan worden geïmplementeerd met behulp van de deque-klasse uit de collectiemodule. Deque heeft de voorkeur boven de lijst in de gevallen waarin we snellere append- en pop-bewerkingen nodig hebben vanaf beide uiteinden van de container, omdat deque een O(1) tijdscomplexiteit biedt voor append- en pop-bewerkingen in vergelijking met list die O(n) biedt. tijd complexiteit.

Dezelfde methoden op deque als in de lijst worden gebruikt, append() en pop().

# Python program to # demonstrate stack implementation # using collections.deque from collections import deque stack = deque() # append() function to push # element in the stack stack.append('a') stack.append('b') stack.append('c') print('Initial stack:') print(stack) # pop() function to pop # element from stack in # LIFO order print('
Elements popped from stack:') print(stack.pop()) print(stack.pop()) print(stack.pop()) print('
Stack after elements are popped:') print(stack) # uncommenting print(stack.pop()) # will cause an IndexError # as the stack is now empty>

Initial stack: deque(['a', 'b', 'c']) Elements popped from stack: c b a Stack after elements are popped: deque([])>

Implementatie met behulp van wachtrijmodule

De wachtrijmodule heeft ook een LIFO-wachtrij, die in feite een stapel is. Gegevens worden in de wachtrij ingevoegd met behulp van de functie put() en get() haalt gegevens uit de wachtrij.

Er zijn verschillende functies beschikbaar in deze module:

• maximale grootte – Aantal toegestane items in de wachtrij.
• leeg() – Retourneert True als de wachtrij leeg is, anders False.
• vol() – Retourneert True als dit het geval is maximale grootte items in de wachtrij. Als de wachtrij is geïnitialiseerd met maxsize=0 (de standaardwaarde), retourneert full() nooit True.
• krijgen() – Een item uit de wachtrij verwijderen en terugsturen. Als de wachtrij leeg is, wacht dan tot er een item beschikbaar is.
• get_nowait() – Retourneer een item als het onmiddellijk beschikbaar is, of verhoog QueueEmpty.
• plaats(item) – Plaats een item in de wachtrij. Als de wachtrij vol is, wacht dan tot er een vrije plek beschikbaar is voordat u het item toevoegt.
• put_nowait(item) – Plaats een item in de wachtrij zonder te blokkeren. Als er niet onmiddellijk een vrij slot beschikbaar is, verhoogt u QueueFull.
• qgrootte() – Retourneer het aantal items in de wachtrij.

# Python program to # demonstrate stack implementation # using queue module from queue import LifoQueue # Initializing a stack stack = LifoQueue(maxsize=3) # qsize() show the number of elements # in the stack print(stack.qsize()) # put() function to push # element in the stack stack.put('a') stack.put('b') stack.put('c') print('Full: ', stack.full()) print('Size: ', stack.qsize()) # get() function to pop # element from stack in # LIFO order print('
Elements popped from the stack') print(stack.get()) print(stack.get()) print(stack.get()) print('
Empty: ', stack.empty())>

0 Full: True Size: 3 Elements popped from the stack c b a Empty: True>

Implementatie met behulp van een enkelvoudig gekoppelde lijst:

De gekoppelde lijst heeft twee methoden addHead(item) en removeHead() die in constante tijd worden uitgevoerd. Deze twee methoden zijn geschikt om een ​​stapel te implementeren.

• getSize() – Verkrijg het aantal items in de stapel.
• is leeg() – Retourneert True als de stapel leeg is, anders False.
• kijkje() – Plaats het bovenste item in de stapel terug. Als de stapel leeg is, maak dan een uitzondering.
• push(waarde) – Duw een waarde in de kop van de stapel.
• knal() – Verwijder en retourneer een waarde in de kop van de stapel. Als de stapel leeg is, maak dan een uitzondering.

Hieronder vindt u de implementatie van de bovenstaande aanpak:

# Python program to demonstrate # stack implementation using a linked list. # node class class Node: def __init__(self, value): self.value = value self.next = None class Stack: # Initializing a stack. # Use a dummy node, which is # easier for handling edge cases. def __init__(self): self.head = Node('head') self.size = 0 # String representation of the stack def __str__(self): cur = self.head.next out = '' while cur: out += str(cur.value) + '->' cur = cur.next return out[:-2] # Haal de huidige grootte van de stapel op def getSize(self): return self.size # Controleer of de stapel leeg is def isEmpty(self): return self.size = = 0 # Haal het bovenste item van de stapel op def peek(self): # Sanitaire controle om te zien of we # naar een lege stapel kijken. if self.isEmpty(): return Geen return self.head.next.value # Duw een waarde in de stapel. def push(self, value): node = Knooppunt(waarde) node.next = self.head.next # Zorg ervoor dat het nieuwe knooppunt naar het huidige hoofd verwijst self.head.next = knooppunt #!!! # Update de head zodat deze de nieuwe node self.size += 1 is # Verwijder een waarde uit de stapel en retourneer. def pop(self): if self.isEmpty(): raise Exception('Poppen uit een lege stapel') remove = self.head.next self.head.next = remove.next #!!! gewijzigd self.size -= 1 return remove.value # Stuurprogrammacode if __name__ == '__main__': stack = Stack() for i in bereik(1, 11): stack.push(i) print(f' Stack: {stack}') for _ in range(1, 6): top_value = stack.pop() print(f'Pop: {top_value}') # variabelenaam gewijzigd print(f'Stack: { stapel}')>

Uitvoer

Stack: 10->9->8->7->6->5->4->3->2->1 Pop: 10 Pop: 9 Pop: 8 Pop: 7 Pop: 6 Stack: 5->4->3->2->1>

Voordelen van stapel:

• Stacks zijn eenvoudige datastructuren met een goed gedefinieerde reeks bewerkingen, waardoor ze gemakkelijk te begrijpen en te gebruiken zijn.
• Stapels zijn efficiënt voor het toevoegen en verwijderen van elementen, aangezien deze bewerkingen een tijdscomplexiteit van O(1) hebben.
• Om de volgorde van de elementen om te keren, gebruiken we de stapeldatastructuur.
• Stapels kunnen worden gebruikt om functies voor ongedaan maken/opnieuw uitvoeren in applicaties te implementeren.

Nadelen van stapelen:

• Beperking van de grootte in Stack is een nadeel en als ze vol zijn, kun je geen elementen meer aan de stapel toevoegen.
• Stapels bieden geen snelle toegang tot andere elementen dan het bovenste element.
• Stapels ondersteunen geen efficiënt zoeken, omdat u elementen één voor één moet openen totdat u het element vindt waarnaar u op zoek bent.