Wat zijn Stack-gegevensstructuren in Python?

Gegevensstructuren zijn een verzameling gegevenswaarden, de onderlinge relaties en de functies of bewerkingen die op de gegevens kunnen worden toegepast. Nu zijn er veel datastructuren beschikbaar. Maar vandaag zal onze focus liggen op Stack Data Structures. Ik bespreek de volgende onderwerpen:

• Waarom datastructuren?
• Typen gegevensstructuren
• Wat is Stack-gegevensstructuur?
• Stack-gegevensstructuur maken
• Duw elementen in stapel
• Pop-elementen uit stapel
• Toepassingen van Stack Data Structure

Waarom datastructuren?

Om dit te beantwoorden, moet je op een groot niveau denken. Bedenk hoe Google maps u de beste route in slechts een fractie van seconden laat zien, en hoe het uw zoekresultaat in microseconden retourneert. Het behandelt niet alleen 100 websites, het behandelt meer dan een miljard sites en laat nog steeds zo snel resultaat zien.

Hoewel het gebruikte algoritme een cruciale rol speelt, is de datastructuur of de gebruikte container de basis van dat algoritme. In elke toepassing is het organiseren en opslaan van gegevens op een manier of in een structuur die het meest geschikt is voor het gebruik ervan, de sleutel tot efficiënte toegang tot en verwerking van gegevens.

Typen gegevensstructuren

Er zijn enkele standaard datastructuren die kunnen worden gebruikt om efficiënt met data te werken. We kunnen ze zelfs aanpassen of volledig nieuwe bouwen om aan onze toepassing te voldoen.

Wat is Stack-gegevensstructuur?

Beschouw eens enkele praktijkvoorbeelden:

• Verzending in vracht
• Borden op een dienblad
• Stapel munten
• Stapel laden
• Rangeren van treinen op een emplacement

Al deze voorbeelden volgen een Laatste erin, eerste eruit strategie. Overweeg borden op een schaal. Als u een bord wilt kiezen, moet u een bord van bovenaf kiezen, terwijl wanneer de borden op de schaal werden bewaard, ze in omgekeerde volgorde moesten zijn. Bovenstaande voorbeelden die het Last-In-First-Out (LIFO) principe staan ​​bekend als Stapel .

Afgezien van de aanvullende bewerkingen, kan ik zeggen dat de belangrijkste bewerkingen die mogelijk zijn op de stapel zijn:

1. Duw of plaats een element naar de bovenkant van de stapel
2. Knal of verwijder een element van de bovenkant van de stapel

Stack-gegevensstructuur maken

class Stack: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ top = -1

• max_size is het maximale aantal elementen dat in de stapel wordt verwacht.
• Elementen van de stapel worden opgeslagen in de python-lijst.
• Top geeft de bovenste index van de stapel aan die in eerste instantie wordt ingenomen -1 om een ​​lege stapel te markeren.

De initiële status van de stapel is te zien in de afbeelding waar max_size = 5

Duw element in stapel

Als u nu een element naar de stapel wilt invoeren of naar de stapel wilt duwen, moet u dat onthouden

• De bovenkant geeft de index aan waarin het element wordt ingevoegd.
• En dat er geen element wordt ingevoegd als de stapel vol is, d.w.z. als max_size = top.

Dus wat zou het algoritme moeten zijn?

# geeft de maximale grootte van de stapel terug def get_max_size (zelf): retourneer zelf .__ max_size # geeft de bool-waarde terug, ongeacht of de stapel vol is of niet, waar als vol en anders onwaar def is_vol (zelf): retour zelf.get_max_size () - 1 == self .__ top #pushes element bovenaan stack def push (self, data): if (self.is_full ()): print ('stack is al vol') else: self .__ top = self .__ top + int (1 ) self .__ elements [self .__ top] = data #U kunt de onderstaande __str __ () gebruiken om de elementen van het DS-object af te drukken tijdens het debuggen def __str __ (self): msg = [] index = self .__ top while (index> = 0): msg.append ((str) (self .__ elements [index])) index- = 1 msg = '' .join (msg) msg ​​= 'Stack data (van boven naar beneden):' + msg return msg

Nu, wanneer u het volgende uitvoert:

stack1 = Stapel (4)

#Push alle vereiste element (en).

stack1.push ('A')

stack1.push ('B')

naar string methode in java

stack1.push ('C')

stack1.push ('E')

print (stack1.is_full ())

print (stapel1)

Uitgang:

stapel is al vol
Klopt
Gegevens stapelen (van boven naar beneden): D C B A

Pop-elementen uit stapel

Nu je de elementen in de stapel hebt ingevoegd, wil je ze poppen, dus je moet voor het volgende zorgen:

• Stapel is niet leeg, d.w.z. top! = -1
• Wanneer u de gegevens verwijdert, moet de bovenkant naar de vorige bovenkant van de stapel wijzen.

Dus, wat wordt het algoritme?

#returns bool-waarde of stapel leeg is of niet, Waar als leeg en anders False def is_empty (self): return self .__ top == - 1 #returns popped value def pop (self): if (self.is_empty ()): print ('niets te poppen, al leeg') else: a = self .__ elements [self .__ top] self .__ top = self .__ top-1 retourneer a #display alle stapelelementen van boven naar beneden def display (self): voor i binnen bereik (self .__ top, -1, -1): print (self .__ elements [i], end = '') print ()

Probeer nu, gezien de eerder gemaakte stapel, elementen te poppen

print (stack1.pop ())

print (stack1.pop ())

print (stapel1)

print (stack1.pop ())

print (stack1.pop ())

print (stack1.pop ())

Uitgang:

D

C

Gegevens stapelen (van boven naar beneden): B A

B.

NAAR

niets te ploppen, al leeg

Toepassingen van Stack Data Structure

• Voorbeeld 1:

Een stapel wordt gebruikt om het algoritme voor het matchen van haakjes te implementeren voor de evaluatie van rekenkundige uitdrukkingen en ook voor de implementatie van methodeaanroepen.

Antwoord waarop is 5.

• Voorbeeld 2:

Klembord in Windows gebruikt twee stapels om undo-redo-bewerkingen (ctrl + z, ctrl + y) te implementeren. U zou hebben gewerkt aan Windows-woordeditors zoals MS-Word, Kladblok, enz. Hier is een tekst is geschreven in MS-Word. Kijk hoe de tekst veranderde door op Ctrl-Z en Ctrl-Y te klikken.

Hier is een code die ongedaan maken-opnieuw uitvoeren simuleert. Doorloop de code en kijk hoe de stack in deze implementatie wordt gebruikt.

#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 ('De stapel is vol !!') else: self .__ top + = 1 self .__ elements [self .__ top] = data def pop (self): if (self.is_empty ()): print ('De stapel is leeg! ! ') else: data = self .__ elementen [self .__ top] self .__ top- = 1 retour data def weergave (self): if (self.is_empty ()): print (' De stapel is leeg ') else: index = self .__ top while (index> = 0): print (self .__ elements [index]) index- = 1 def get_max_size (self): return self .__ max_size #U kunt de onderstaande __str __ () gebruiken om de elementen van de DS-object tijdens het debuggen def __str __ (self): msg = [] index = self .__ top while (index> = 0): msg.append ((str) (self .__ elements [index])) index- = 1 msg = ' '.join (msg) msg ​​=' Stack data (van boven naar beneden): '+ msg retour ms g #functie om remove of backspace-bewerking te implementeren def remove (): globaal klembord, undo_stack data = clipboard [len (clipboard) -1] clipboard.remove (data) undo_stack.push (data) print ('Verwijderen:', klembord) #functie om de bewerking ongedaan maken te implementeren def undo (): globaal klembord, undo_stack, redo_stack if (undo_stack.is_empty ()): print ('Er zijn geen gegevens om ongedaan te maken') anders: data = undo_stack.pop () clipboard.append ( data) redo_stack.push (data) print ('Undo:', clipboard) #function om redo-operatie te implementeren def redo (): globaal klembord, undo_stack, redo_stack if (redo_stack.is_empty ()): print ('Er zijn geen gegevens opnieuw uitvoeren ') else: data = redo_stack.pop () if (data niet in klembord): print (' Er zijn geen data om opnieuw uit te voeren ') redo_stack.push (data) else: clipboard.remove (data) undo_stack.push ( data) print ('Redo:', clipboard) clipboard = ['A', 'B', 'C', 'D', 'E', 'F'] undo_stack = Stack (len (clipboard)) redo_stack = Stack (len (clipboard)) remove () undo () redo ()

Uitgang:

Verwijderen: [‘A’, ‘B’, ‘C’, ‘D’, ‘E’]

Ongedaan maken: [‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’]

Opnieuw: [‘A’, ‘B’, ‘C’, ‘D’, ‘E’]

Hiermee komen we aan het einde van dit Stack Data Structure in Python-artikel. Als je de codes met succes hebt begrepen en zelf hebt uitgevoerd, ben je niet langer een nieuweling van Stacks Data Structure.

Heeft u een vraag voor ons? Vermeld het in het opmerkingengedeelte van dit artikel en we nemen zo snel mogelijk contact met u op.

Om diepgaande kennis op te doen over Python en de verschillende applicaties, kunt u zich live inschrijven met 24/7 ondersteuning en levenslange toegang.