Hvad er stack-datastrukturer i Python?



Denne artikel vil give dig en detaljeret og omfattende viden om Stack-datastrukturer i Python med mange eksempler.

Datastrukturer er en samling af dataværdier, forholdet mellem dem og de funktioner eller operationer, der kan anvendes på dataene. Nu er der mange datastrukturer til rådighed. Men i dag vil vores fokus være på stack datastrukturer. Jeg diskuterer følgende emner:

Hvorfor datastrukturer?

For at besvare dette bliver du nødt til at tænke på et stort niveau. Tænk på, hvordan Google maps viser dig den bedste rute på bare en brøkdel af sekunder, hvordan det returnerer dit søgeresultat i mikrosekunder. Det handler ikke kun om 100 websteder, det beskæftiger sig med mere end en milliard websteder og viser dig stadig resultatet så hurtigt.





Selvom den anvendte algoritme spiller en afgørende rolle, er datastrukturen eller den anvendte beholder grundlaget for denne algoritme. I enhver applikation er organisering og lagring af data på en måde eller i en struktur, der er bedst egnet til dets anvendelse, nøglen til effektiv adgang og behandling af data.

Typer af datastrukturer

Der er nogle standard datastrukturer, der kan bruges til effektivt at arbejde med data. Vi kan endda tilpasse dem eller bygge helt nye, så de passer til vores applikation.



Datastrukturstyper

Hvad er stack datastruktur?

Overvej nogle eksempler fra det virkelige liv:

  • Forsendelse i fragt
  • Plader på en bakke
  • Stak med mønter
  • Stak med skuffer
  • Rangering af tog i en jernbanegård

plates-stacks-data-structure



Alle disse eksempler følger a Last-In-First-Out strategi. Overvej plader på en bakke. Når du vil vælge en plade, er du tvunget til at vælge en plade fra toppen, mens når pladerne blev holdt på bakken, skal de være i omvendt rækkefølge. Ovenstående eksempler, der følger Last-in-first-out (LIFO) princip er kendt som Stak .

Bortset fra de supplerende operationer kan jeg sige, at de vigtigste operationer, der er mulige på stakken, er:

  1. Skub eller indsæt et element øverst på stakken
  2. Pop eller fjern et element fra toppen af ​​stakken

Oprettelse af stakdatastruktur

klasse Stak: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ top = -1
  • max_størrelse er det maksimale antal elementer, der forventes i stakken.
  • Elementer af stakken er gemt i pythonlisten.
  • Top angiver det øverste indeks for stakken, som oprindeligt tages -1 for at markere tom stak.

Den indledende status for stakken kan ses i figuren hvor max_size = 5

Skub element i stak

Nu, hvis du vil indtaste eller skubbe element til stakken, skal du huske det

  • Toppen peger på det indeks, som elementet skal indsættes i.
  • Og at der ikke indsættes noget element, når stakken er fuld, dvs. når max_size = top.

Så hvad skal algoritmen være?

# returnerer den maksimale størrelse af stak def get_max_size (selv): returner selv .__ max_size # returnerer bool-værdi, uanset om stakken er fuld eller ej, Sand hvis fuld og Falsk ellers def er_full (selv): returnerer self.get_max_size () - 1 == self .__ top #pushes element øverst på stack def push (self, data): if (self.is_full ()): print ('stack is already full') ellers: self .__ top = self .__ top + int (1 ) selv .__-elementer [selv .__ top] = data #Du kan bruge nedenstående __str __ () til at udskrive elementerne i DS-objektet, mens debugging def __str __ (selv): msg = [] index = self .__ top while (index> = 0): msg.append ((str) (self .__ elements [index])) index- = 1 msg = ''. Join (msg) msg ​​= 'Stak data (top til bund):' + msg returner msg

Nu, når du udfører følgende:

stack1 = Stack (4)

# Skub alle de krævede element (er).

stack1.push (“A”)

stack1.push (“B”)

stack1.push (“C”)

stack1.push (“E”)

udskriv (stack1.is_full ())

udskriv (stak1)

Produktion:

python klasse __init__

stakken er allerede fuld
Sand
Stakdata (top til bund): D C B A

Popelementer fra stak

Når du nu har indsat elementerne i stakken, vil du poppe dem, så du skal passe på følgende:

  • Stakken er ikke tom, dvs. top! = -1
  • Når du sletter dataene, skal toppen pege på den forrige top af stakken.

Så hvad bliver algoritmen ??

#returns bool-værdi, uanset om stakken er tom eller ikke, sand hvis tom og falsk ellers def er_empty (selv): returner selv .__ top == - 1 #returns popped værdi def pop (selv): hvis (self.is_empty ()): print ('intet at poppe, allerede tomt') ellers: a = selv .__ elementer [selv .__ top] selv .__ top = selv .__ top-1 returnere et #display alle stakelementerne fra top til bund def display (selv): for jeg inden for rækkevidde (selv .__ top, -1, -1): print (selv .__-elementer [i], slut = '') print ()

Nu, i betragtning af tidligere oprettet stak, skal du prøve at pope elementer

udskriv (stack1.pop ())

udskriv (stack1.pop ())

udskriv (stak1)

udskriv (stack1.pop ())

udskriv (stack1.pop ())

udskriv (stack1.pop ())

Produktion:

D

C

Stakdata (top til bund): B A

B

TIL

intet at poppe, allerede tomt

Anvendelser af stakdatastruktur

  • Eksempel 1:

En stak bruges til at implementere parentesmatchingsalgoritme til aritmetisk ekspressionsevaluering og også til implementering af metodeopkald.

Svaret på hvilket er 5.

  • Eksempel 2:

Udklipsholder i Windows bruger to stakke til at implementere fortryd-gentag (ctrl + z, ctrl + y) operationer. Du ville have arbejdet på Windows-ordredigerere som MS-Word, Notepad osv. Her er en tekst skrevet i MS-Word. Overhold, hvordan teksten blev ændret ved klik på Ctrl-Z og Ctrl-Y.

Her er en kode, der simulerer fortryd-om-handling. Gå gennem koden og observer, hvordan stakken bruges i denne implementering.

#creating class stack class Stack: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ top = -1 def is_full (self): if (self .__ top == self .__ max_size-1): returner True return False def is_empty (self): if (self .__ top == - 1): return True Return False def push (self, data): if (self.is_full ()): print ('Stakken er fuld !!') andet: selv .__ top + = 1 selv .__ elementer [selv .__ top] = data def pop (selv): hvis (self.is_empty ()): print ('Stakken er tom! ! ') ellers: data = selv .__ elementer [selv .__ top] selv .__ top- = 1 returnere data def display (selv): hvis (self.is_empty ()): udskriv (' Stakken er tom ') ellers: indeks = self .__ top while (index> = 0): print (self .__ elements [index]) index- = 1 def get_max_size (self): return self .__ max_size # Du kan bruge nedenstående __str __ () til at udskrive elementerne i DS-objekt under fejlretning def __str __ (selv): msg = [] indeks = selv .__ top mens (indeks> = 0): msg.append ((str) (selv .__ elementer [indeks])) indeks- = 1 msg = ' '.join (msg) msg ​​=' Stak data (top til bund): '+ msg returnerer ms g #funktion til implementering af fjernelse eller backspace-handling def remove (): global udklipsholder, fortryde_stackdata = udklipsholder [len (udklipsholder) -1] udklipsholder. fjern (data) undo_stack.push (data) print ('Fjern:', udklipsholder #funktion til at implementere fortryd operation def fortryde (): global udklipsholder, fortryde_stack, gentage_stack hvis (undo_stack.is_empty ()): print ('Der er ingen data at fortryde') andet: data = undo_stack.pop () udklipsholder.append data) redo_stack.push (data) print ('Fortryd:', udklipsholder) #funktion til implementering af redo operation def redo (): global clipboard, undo_stack, redo_stack if (redo_stack.is_empty ()): print ('Der er ingen data at gentage ') ellers: data = redo_stack.pop () hvis (data ikke i udklipsholder): udskriv (' Der er ingen data at gentage ') redo_stack.push (data) ellers: clipboard.remove (data) undo_stack.push ( data) print ('Gentag:', udklipsholder) udklipsholder = ['A', 'B', 'C', 'D', 'E', 'F'] undo_stack = Stak (len (udklipsholder)) redo_stack = Stak (len (udklipsholder)) fjern () fortryd () gentag ()

Produktion:

Fjern: ['A', 'B', 'C', 'D', 'E']

Fortryd: ['A', 'B', 'C', 'D', 'E', 'F']

Gør om: ['A', 'B', 'C', 'D', 'E']

Med dette kommer vi til en ende på denne Stack-datastruktur i Python-artiklen. Hvis du med succes har forstået og kørt koderne, er du ikke længere nybegynder til Stacks Datastruktur.

Har du et spørgsmål til os? Nævn det i kommentarfeltet i denne artikel, og vi vender tilbage til dig hurtigst muligt.

For at få dybtgående viden om Python sammen med dens forskellige applikationer kan du tilmelde dig live med 24/7 support og livstidsadgang.