EN stak er en lineær datastruktur, der gemmer elementer i en Sidst ind/først ud (LIFO) eller First-In/Last-Out (FILO) måde. I stakken tilføjes et nyt element i den ene ende, og et element fjernes kun fra den ende. Indsæt- og sletningsoperationerne kaldes ofte push og pop.

Funktionerne forbundet med stack er:

• tom() – Returnerer om stakken er tom – Tidskompleksitet: O(1)
• størrelse() – Returnerer stakkens størrelse – Tidskompleksitet: O(1)
• top() / kig() – Returnerer en reference til det øverste element i stakken – Tidskompleksitet: O(1)
• skub (a) – Indsætter elementet 'a' i toppen af ​​stakken – Tidskompleksitet: O(1)
• pop() – Sletter det øverste element i stakken – Tidskompleksitet: O(1)

Implementering:

Der er forskellige måder, hvorfra en stak kan implementeres i Python. Denne artikel dækker implementeringen af ​​en stak ved hjælp af datastrukturer og moduler fra Python-biblioteket.
Stack i Python kan implementeres på følgende måder:

• liste
• Collections.deque
• kø.LifoKø

Implementering ved hjælp af liste:

Pythons indbyggede datastrukturliste kan bruges som en stak. I stedet for push(), bruges append() til at tilføje elementer til toppen af ​​stakken, mens pop() fjerner elementet i LIFO-rækkefølge.
Desværre har listen et par mangler. Det største problem er, at det kan løbe ind i hastighedsproblemer, efterhånden som det vokser. Elementerne på listen gemmes ved siden af ​​hinanden i hukommelsen, hvis stakken vokser sig større end den hukommelsesblok, der i øjeblikket rummer den, så skal Python udføre nogle hukommelsestildelinger. Dette kan føre til, at nogle append()-kald tager meget længere tid end andre.

# 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 ved hjælp af collections.deque:

Python stack kan implementeres ved hjælp af deque-klassen fra samlingsmodulet. Deque foretrækkes frem for listen i de tilfælde, hvor vi har brug for hurtigere tilføjelses- og pop-operationer fra begge ender af containeren, da deque giver en O(1)-tidskompleksitet for tilføjelses- og pop-handlinger sammenlignet med liste, der giver O(n) tidskompleksitet.

De samme metoder på deque, som ses på listen, bruges, append() og 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 vha. kømodul

Kø-modul har også en LIFO-kø, som grundlæggende er en stak. Data indsættes i køen ved hjælp af put()-funktionen og get() tager data ud fra køen.

Der er forskellige funktioner tilgængelige i dette modul:

• maxsize – Antal tilladte varer i køen.
• tom() – Returner True, hvis køen er tom, ellers False.
• fuld() – Returner True, hvis der er maxsize varer i køen. Hvis køen blev initialiseret med maxsize=0 (standard), returnerer full() aldrig True.
• få() – Fjern og returner en vare fra køen. Hvis køen er tom, skal du vente, indtil en vare er tilgængelig.
• get_nuwait() – Returner en vare, hvis en er tilgængelig med det samme, ellers hæv QueueEmpty.
• put(item) – Sæt en vare i køen. Hvis køen er fuld, skal du vente, indtil en ledig plads er tilgængelig, før du tilføjer varen.
• put_nuwait(vare) – Sæt en vare i køen uden at blokere. Hvis der ikke umiddelbart er nogen ledig plads, hæv QueueFull.
• qsize() – Returner antallet af varer i køen.

# 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 ved hjælp af en enkelt linket liste:

Den sammenkædede liste har to metoder addHead(item) og removeHead(), der kører konstant. Disse to metoder er velegnede til at implementere en stak.

• getSize() – Få antallet af genstande i stakken.
• er tom() – Returner True, hvis stakken er tom, ellers False.
• kig() – Returner det øverste element i stakken. Hvis stakken er tom, rejs en undtagelse.
• push (værdi) – Skub en værdi ind i hovedet på stakken.
• pop() – Fjern og returner en værdi i toppen af ​​stakken. Hvis stakken er tom, rejs en undtagelse.

Nedenfor er implementeringen af ​​ovenstående tilgang:

# 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] # Hent den aktuelle størrelse på stakken def getSize(self): return self.size # Tjek om stakken er tom def isEmpty(self): return self.size = = 0 # Få det øverste element i stakken def peek(self): # Hygiejnetjek for at se, om vi # kigger på en tom stak. if self.isEmpty(): return Ingen returner self.head.next.value # Skub en værdi ind i stakken. def push(selv, værdi): node = Node(værdi) node.next = self.head.next # Få den nye node til at pege på det aktuelle hoved self.head.next = node #!!! # Opdater hovedet til at være den nye node self.size += 1 # Fjern en værdi fra stakken og returner. def pop(selv): if self.isEmpty(): raise Undtagelse('Popping fra en tom stak') remove = self.head.next self.head.next = remove.next #!!! ændret self.size -= 1 returner remove.value # Driverkode hvis __navn__ == '__main__': stack = Stack() for i i område(1, 11): stack.push(i) print(f' Stak: {stak}') for _ i området(1, 6): top_value = stack.pop() print(f'Pop: {top_value}') # variabelnavn ændret print(f'Stack: { stak}')>

Produktion

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

Fordele ved Stack:

• Stakke er simple datastrukturer med et veldefineret sæt operationer, som gør dem nemme at forstå og bruge.
• Stabler er effektive til at tilføje og fjerne elementer, da disse operationer har en tidskompleksitet på O(1).
• For at vende rækkefølgen af ​​elementer bruger vi stakdatastrukturen.
• Stabler kan bruges til at implementere fortryd/gendan funktioner i applikationer.

Ulemper ved Stack:

• Begrænsning af størrelse i stakken er en ulempe, og hvis de er fulde, kan du ikke tilføje flere elementer til stakken.
• Stabler giver ikke hurtig adgang til andre elementer end det øverste element.
• Stabler understøtter ikke effektiv søgning, da du skal pop elementer et efter et, indtil du finder det element, du leder efter.