Datastrukturer är en samling datavärden, förhållandet mellan dem och de funktioner eller operationer som kan tillämpas på data. Nu finns det många datastrukturer tillgängliga. Men idag kommer vårt fokus att ligga på stackdatastrukturer. Jag kommer att diskutera följande ämnen:
- Varför datastrukturer?
- Typer av datastrukturer
- Vad är stackdatastruktur?
- Skapa stapeldatastruktur
- Skjut in elementen i stacken
- Popelement från Stack
- Tillämpningar av stapeldatastruktur
Varför datastrukturer?
För att svara på detta måste du tänka på en stor nivå. Tänk på hur Google maps visar dig den bästa rutten på bara en bråkdel av sekunder, hur den returnerar ditt sökresultat i mikrosekunder. Det handlar inte bara om 100 webbplatser, det handlar om mer än en miljard webbplatser och visar dig fortfarande resultatet så snabbt.
Även om algoritmen som används spelar en avgörande roll, är datastrukturen eller behållaren som används grunden för den algoritmen. I alla applikationer är organisering och lagring av data på ett sätt eller i en struktur som är bäst lämpad för dess användning nyckeln till effektiv åtkomst och bearbetning av data.
Typer av datastrukturer
Det finns några standarddatastrukturer som kan användas för att effektivt arbeta med data. Vi kan även anpassa dem eller bygga helt nya för att passa vår applikation.
Vad är stackdatastruktur?
Tänk på några verkliga exempel:
- Sändning i last
- Tallrikar på en bricka
- Stack av mynt
- Stack av lådor
- Växling av tåg i en järnvägsgård
Alla dessa exempel följer a Sist in först ut strategi. Tänk på tallrikar på en bricka. När du vill välja en tallrik tvingas du välja en tallrik uppifrån medan när plattorna förvarades på brickan måste de vara i omvänd ordning. Ovanstående exempel som följer Last-in-First-Out (LIFO) principen är känd som Stack .
Förutom de kompletterande operationerna kan jag säga att de viktigaste operationerna som är möjliga på stacken är:
- Skjut eller sätt in ett element på toppen av stacken
- Poppa eller ta bort ett element från toppen av stacken
Skapa stapeldatastruktur
klass Stack: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ top = -1
- max_storlek är det maximala antalet element som förväntas i stacken.
- Element i stacken lagras i pythonlistan.
- Överst visar det högsta indexet för stacken som ursprungligen tas -1 för att markera tom stack.
Stapelns initiala status kan ses i figuren där max_size = 5
Skjut elementet i stacken
Nu, om du vill ange eller skjuta element till stacken måste du komma ihåg det
- Överst pekar indexet som elementet ska infogas till.
- Och att inget element kommer att införas när stacken är full, dvs. när max_size = top.
Så vad ska algoritmen vara ??
# returnerar den maximala storleken på stacken def get_max_size (själv): returnera själv .__ max_size # returnerar bool-värdet oavsett om stacken är full eller inte, True if full och False annars def är_full (self): returnera self.get_max_size () - 1 == self .__ top #pushes element at the top of stack def push (self, data): if (self.is_full ()): print ('stack is already full') else: self .__ top = self .__ top + int (1 ) self .__-element [self .__ top] = data # Du kan använda nedanstående __str __ () för att skriva ut elementen i DS-objektet medan du felsöker def __str __ (self): msg = [] index = self .__ top while (index> = 0): msg.append ((str) (self .__ elements [index])) index- = 1 msg = ''. Gå med (msg) msg = 'Stack data (uppifrån och ned):' + msg return msgNu när du utför följande:
stack1 = Stack (4)
#Push alla nödvändiga element.
stack1.push (“A”)
stack1.push (“B”)
stack1.push (“C”)
stack1.push (“E”)
skriva ut (stack1.is_full ())
skriva ut (stack1)
Produktion:
stacken är redan full
Sann
Stapeldata (uppifrån och ned): D C B A
hur man ställer in klassstig i java
Popelement från Stack
Nu när du har satt in elementen i stacken vill du poppa dem, så du måste ta hand om följande:
- Stack är inte tom, dvs. topp! = -1
- När du tar bort data måste toppen peka på föregående topp i stacken.
Så, vad blir algoritmen ??
#returns bool-värde, oavsett om stacken är tom eller inte, sant om det är tomt och falskt annars är def__fel (själv): returnerar själv .__ topp == - 1 # returnerar poppat värde def pop (själv): om (self.is_empty ()): skriva ut ('ingenting att popa, redan tomt') annat: a = själv .__ element [själv .__ topp] själv .__ topp = själv .__ topp-1 returnera en #display alla stapelelement från topp till botten def display (själv): för jag inom intervallet (själv .__ topp, -1, -1): skriv ut (själv .__ element [i], slut = '') tryck ()Nu, med tanke på tidigare skapad stack, försök att popa element
skriva ut (stack1.pop ())
skriva ut (stack1.pop ())
skriva ut (stack1)
skriva ut (stack1.pop ())
skriva ut (stack1.pop ())
skriva ut (stack1.pop ())
Produktion:
D
C
Stapeldata (uppifrån och ned): B A
B
TILL
inget att popa, redan tomt
Tillämpningar av stapeldatastruktur
- Exempel 1:
En stack används för att implementera parentesmatchningsalgoritm för aritmetisk uttrycksutvärdering och även för implementering av metodanrop.
Svaret på vilket är 5.
- Exempel 2:
Urklipp i Windows använder två stackar för att implementera ångra-om (ctrl + z, ctrl + y) operationer. Du skulle ha arbetat med Windows-ordredigerare som MS-Word, Notepad etc. Här är en text skriven i MS-Word. Observera hur texten ändrades vid klick på Ctrl-Z och Ctrl-Y.
Här är en kod som simulerar ångra-om-operation. Gå igenom koden och observera hur stacken används i denna 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): return True return False def is_empty (self): if (self .__ top == - 1): return True Return False def push (self, data): if (self.is_full ()): print ('Stapeln är full !!') annat: själv .__ topp + = 1 själv .__ element [själv .__ topp] = data def pop (själv): om (self.is_empty ()): skriv ut ('Stapeln är tom! ! ') annat: data = själv .__-element [själv .__ topp] själv .__ topp- = 1 returnera data def-visning (själv): om (self.is_empty ()): skriv ut (' Stapeln är tom ') annat: index = self .__ top while (index> = 0): print (self .__ elements [index]) index- = 1 def get_max_size (self): return self .__ max_size # Du kan använda nedan __str __ () för att skriva ut elementen i DS-objekt vid felsökning def __str __ (själv): msg = [] index = själv .__ topp medan (index> = 0): msg.append ((str) (själv .__ element [index])) index- = 1 msg = ' '.join (msg) msg =' Stack data (uppifrån och ned): '+ msg returnerar ms g #funktion för att implementera borttagning eller backstegsoperation def remove (): global urklipp, ångra_stackdata = urklipp [len (urklipp) -1] urklipp. ta bort (data) ångra_stack.push (data) skriv ut ('Ta bort:', urklipp) #funktion för att implementera ångra operation def ångra (): global urklipp, ångra_stack, gör om_stack om (ångra_stack.is_empty ()): skriv ut ('Det finns ingen data att ångra') annat: data = ångra_stack.pop () urklipp.append ( data) redo_stack.push (data) print ('Undo:', clipboard) #function to implement redo operation def redo (): global clipboard, undo_stack, redo_stack if (redo_stack.is_empty ()): print ('There is no data att göra om ') annat: data = göra om_stack.pop () om (data inte i urklipp): skriv ut (' Det finns ingen data att göra om ') göra om_stack.push (data) annat: klippbord. ta bort (data) ångra_stack.push ( data) skriv ut ('Gör om:', Urklipp) Urklipp = ['A', 'B', 'C', 'D', 'E', 'F'] undo_stack = Stack (len (klippbord)) redo_stack = Stack (len (urklipp)) ta bort () ångra () göra om ()Produktion:
vad är skillnaden mellan en abstrakt klass och ett gränssnitt?
Ta bort: ['A', 'B', 'C', 'D', 'E']
Ångra: ['A', 'B', 'C', 'D', 'E', 'F']
Gör om: ['A', 'B', 'C', 'D', 'E']
Med detta kommer vi till ett slut på den här stackdatastrukturen i Python-artikeln. Om du själv förstod och sprang koderna är du inte längre nybörjare i Stacks Datastruktur.
Har du en fråga till oss? Vänligen nämna det i kommentarsektionen i den här artikeln så kommer vi tillbaka till dig så snart som möjligt.
För att få fördjupad kunskap om Python tillsammans med dess olika applikationer kan du registrera dig för live med 24/7 support och livstidsåtkomst.