A stack är en linjär datastruktur som lagrar objekt i en Sist in/först ut (LIFO) eller First-In/Last-Out (FILO) sätt. I stack läggs ett nytt element till i ena änden och ett element tas endast bort från den änden. Insert och delete-operationerna kallas ofta push och pop.

Funktionerna associerade med stack är:

• tömma() – Returnerar om stacken är tom – Tidskomplexitet: O(1)
• storlek() – Returnerar stackens storlek – Tidskomplexitet: O(1)
• top() / peek() – Returnerar en referens till det översta elementet i stacken – Tidskomplexitet: O(1)
• push(a) – Infogar elementet 'a' överst i stacken – Tidskomplexitet: O(1)
• pop() – Tar bort det översta elementet i stacken – Tidskomplexitet: O(1)

Genomförande:

Det finns olika sätt från vilka en stack kan implementeras i Python. Den här artikeln täcker implementeringen av en stack med hjälp av datastrukturer och moduler från Python-biblioteket.
Stack i Python kan implementeras på följande sätt:

• lista
• Collections.deque
• queue.LifoQueue

Implementering med hjälp av lista:

Pythons inbyggda datastrukturlista kan användas som en stack. Istället för push(), används append() för att lägga till element till toppen av stacken medan pop() tar bort elementet i LIFO-ordning.
Tyvärr har listan några brister. Det största problemet är att det kan stöta på hastighetsproblem när det växer. Objekten i listan lagras bredvid varandra i minnet, om stacken växer sig större än minnesblocket som för närvarande innehåller det, måste Python göra några minnesallokeringar. Detta kan leda till att vissa append()-anrop tar mycket längre tid än andra.

# 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: []>

Implementering med collections.deque:

Python-stack kan implementeras med hjälp av deque-klassen från samlingsmodulen. Deque föredras framför listan i de fall där vi behöver snabbare append- och pop-operationer från båda ändarna av behållaren, eftersom deque ger en O(1)-tidskomplexitet för append- och pop-operationer jämfört med list som ger O(n) tidskomplexitet.

Samma metoder på deque som visas i listan används, append() och 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([])>

Implementering med hjälp av kömodul

Kömodulen har också en LIFO-kö, som i grunden är en stack. Data infogas i Queue med put()-funktionen och get() tar ut data från Queue.

Det finns olika funktioner tillgängliga i denna modul:

• maxstorlek – Antal artiklar tillåtna i kön.
• tömma() – Returnera True om kön är tom, False annars.
• full() – Returnera True om det finns maxstorlek föremål i kön. Om kön initierades med maxsize=0 (standard), returnerar full() aldrig True.
• skaffa sig() – Ta bort och returnera en vara från kön. Om kön är tom, vänta tills ett objekt är tillgängligt.
• get_nuwait() – Returnera en vara om en är tillgänglig omedelbart, annars höj QueueEmpty.
• put(item) – Lägg en vara i kön. Om kön är full, vänta tills en ledig plats finns tillgänglig innan du lägger till föremålet.
• put_nuwait(artikel) – Lägg en vara i kön utan att blockera. Om ingen ledig slot är tillgänglig direkt, höj QueueFull.
• qsize() – Returnera antalet artiklar i kön.

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

Implementering med en enskild länkad lista:

Den länkade listan har två metoder addHead(item) och removeHead() som körs konstant. Dessa två metoder är lämpliga för att implementera en stack.

• getSize() – Få antalet föremål i högen.
• är tom() – Returnera True om stacken är tom, annars False.
• titt() – Lämna tillbaka det översta föremålet i högen. Om stacken är tom, höj ett undantag.
• push(värde) – Tryck in ett värde i högens huvud.
• pop() – Ta bort och returnera ett värde i toppen av stacken. Om stacken är tom, höj ett undantag.

Nedan är implementeringen av ovanstående tillvägagångssätt:

# 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] # Hämta den aktuella storleken på stacken def getSize(self): return self.size # Kontrollera om stacken är tom def isEmpty(self): return self.size = = 0 # Få det översta objektet i stacken def peek(self): # Sanitetskontroll för att se om vi # tittar på en tom stack. if self.isEmpty(): return None return self.head.next.value # Tryck in ett värde i stacken. def push(self, value): node = Node(värde) node.next = self.head.next # Få den nya noden att peka på det aktuella huvudet self.head.next = nod #!!! # Uppdatera huvudet till den nya noden self.size += 1 # Ta bort ett värde från stacken och returnera. def pop(self): if self.isEmpty(): höj Undantag('Poppar från en tom stack') remove = self.head.next self.head.next = remove.next #!!! ändrad self.size -= 1 returnera remove.value # Driver Code if __name__ == '__main__': stack = Stack() för i i intervallet(1, 11): stack.push(i) print(f' Stack: {stack}') för _ i intervallet(1, 6): top_value = stack.pop() print(f'Pop: {top_value}') # variabelnamn ändrat print(f'Stack: { stack}')>

Produktion

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>

Fördelar med Stack:

• Stackar är enkla datastrukturer med en väldefinierad uppsättning operationer, vilket gör dem lätta att förstå och använda.
• Stackar är effektiva för att lägga till och ta bort element, eftersom dessa operationer har en tidskomplexitet på O(1).
• För att vända ordningen på element använder vi stackdatastrukturen.
• Stackar kan användas för att implementera ångra/gör om funktioner i applikationer.

Nackdelar med Stack:

• Storleksbegränsning i Stack är en nackdel och om de är fulla kan du inte lägga till fler element i stacken.
• Staplar ger inte snabb åtkomst till andra element än det översta elementet.
• Stackar stöder inte effektiv sökning, eftersom du måste poppa element ett efter ett tills du hittar det element du letar efter.