EN stable er en lineær datastruktur som lagrer elementer i en Sist inn/først ut (LIFO) eller First-In/Last-Out (FILO) måte. I stabel legges et nytt element til i den ene enden, og et element fjernes bare fra den enden. Sett inn og slett-operasjoner kalles ofte push og pop.

Funksjonene knyttet til stack er:

• tømme() – Returnerer om stabelen er tom – Tidskompleksitet: O(1)
• størrelse() – Returnerer størrelsen på stabelen – Tidskompleksitet: O(1)
• topp() / kikk() – Returnerer en referanse til det øverste elementet i stabelen – Tidskompleksitet: O(1)
• push(a) – Setter inn elementet ‘a’ på toppen av stabelen – Tidskompleksitet: O(1)
• pop() – Sletter det øverste elementet i stabelen – Tidskompleksitet: O(1)

Gjennomføring:

Det er forskjellige måter en stack kan implementeres fra i Python. Denne artikkelen dekker implementeringen av en stabel ved hjelp av datastrukturer og moduler fra Python-biblioteket.
Stack i Python kan implementeres på følgende måter:

• liste
• Collections.deque
• queue.LifoQueue

Implementering ved hjelp av liste:

Pythons innebygde datastrukturliste kan brukes som en stabel. I stedet for push(), brukes append() til å legge til elementer på toppen av stabelen mens pop() fjerner elementet i LIFO-rekkefølge.
Dessverre har listen noen mangler. Det største problemet er at det kan støte på hastighetsproblemer etter hvert som det vokser. Elementene i listen er lagret ved siden av hverandre i minnet, hvis stabelen vokser seg større enn minneblokken som for øyeblikket inneholder den, må Python gjøre noen minneallokeringer. Dette kan føre til at noen append()-kall tar mye lengre tid enn 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 hjelp av collections.deque:

Python-stack kan implementeres ved å bruke deque-klassen fra samlingsmodulen. Deque foretrekkes fremfor listen i tilfeller der vi trenger raskere append- og pop-operasjoner fra begge ender av beholderen, da deque gir en O(1)-tidskompleksitet for append- og pop-operasjoner sammenlignet med liste som gir O(n) tidskompleksitet.

De samme metodene på deque som vist i listen brukes, 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 ved bruk av kømodul

Kømodulen har også en LIFO-kø, som i utgangspunktet er en stabel. Data settes inn i køen ved å bruke put()-funksjonen og get() tar data ut fra køen.

Det er ulike funksjoner tilgjengelig i denne modulen:

• maxsize – Antall varer tillatt i køen.
• tømme() – Returner True hvis køen er tom, False ellers.
• full() – Returner True hvis det er maxsize varer i køen. Hvis køen ble initialisert med maxsize=0 (standard), returnerer aldri full() True.
• få() – Fjern og returner en vare fra køen. Hvis køen er tom, vent til en vare er tilgjengelig.
• get_nowait() – Returner en vare hvis en er umiddelbart tilgjengelig, ellers hev QueueEmpty.
• put(item) – Sett en vare i køen. Hvis køen er full, vent til en ledig plass er tilgjengelig før du legger til varen.
• put_nowait(item) – Sett en vare i køen uten å blokkere. Hvis ingen gratis spilleautomat er tilgjengelig umiddelbart, hev QueueFull.
• qsize() – Returner antall 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 hjelp av en enkeltlenket liste:

Den koblede listen har to metoder addHead(item) og removeHead() som kjører konstant. Disse to metodene er egnet for å implementere en stabel.

• getSize() – Få antall elementer i stabelen.
• er tom() – Returner True hvis stabelen er tom, False ellers.
• kikke() – Returner det øverste elementet i stabelen. Hvis stabelen er tom, hev et unntak.
• push(verdi) – Skyv en verdi inn i toppen av stabelen.
• pop() – Fjern og returner en verdi i toppen av stabelen. Hvis stabelen er tom, hev et unntak.

Nedenfor er implementeringen av tilnærmingen ovenfor:

# 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] # Få gjeldende størrelse på stabelen def getSize(self): return self.size # Sjekk om stabelen er tom def isEmpty(self): return self.size = = 0 # Få det øverste elementet i stabelen def peek(self): # Sanitærsjekk for å se om vi # titter på en tom stabel. if self.isEmpty(): return Ingen returner self.head.next.value # Skyv en verdi inn i stabelen. def push(selv, verdi): node = Node(verdi) node.next = self.head.next # Få den nye noden til å peke på det gjeldende hodet self.head.next = node #!!! # Oppdater hodet til å være den nye noden self.size += 1 # Fjern en verdi fra stabelen og returner. def pop(selv): if self.isEmpty(): raise Unntak('Popping fra en tom stabel') remove = self.head.next self.head.next = remove.next #!!! endret self.size -= 1 returner remove.value # Driverkode hvis __navn__ == '__main__': stack = Stack() for i i området(1, 11): stack.push(i) print(f' Stabel: {stack}') for _ i området(1, 6): top_value = stack.pop() print(f'Pop: {top_value}') # variabelnavn endret print(f'Stack: { stack}')>

Produksjon

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

Fordeler med Stack:

• Stabler er enkle datastrukturer med et veldefinert sett med operasjoner, noe som gjør dem enkle å forstå og bruke.
• Stabler er effektive for å legge til og fjerne elementer, da disse operasjonene har en tidskompleksitet på O(1).
• For å reversere rekkefølgen på elementene bruker vi stabeldatastrukturen.
• Stabler kan brukes til å implementere angre/redo-funksjoner i applikasjoner.

Ulemper med Stack:

• Begrensning av størrelse i stabel er en ulempe, og hvis de er fulle, kan du ikke legge til flere elementer i stabelen.
• Stabler gir ikke rask tilgang til andre elementer enn toppelementet.
• Stabler støtter ikke effektivt søk, da du må poppe elementer ett etter ett til du finner elementet du leter etter.