Stapels en wachtrijen in Python

Inleiding

datastructuren organiseren opslag in computers zodat we efficiënt toegang kunnen krijgen tot gegevens en deze kunnen wijzigen. Stapels en wachtrijen zijn enkele van de vroegste datastructuren gedefinieerd in de informatica.

eenvoudig te leren en eenvoudig te implementeren, hun toepassingen zijn gebruikelijk en u zult waarschijnlijk merken dat u ze in uw software opneemt voor verschillende taken.

Het is gebruikelijk dat stapels en wachtrijen worden geïmplementeerd met een Array of gekoppelde lijst. We vertrouwen op deList datastructuur om zowel stapels als wachtrijen aan te passen.

Hoe werken ze?

Stack

Stacks, zoals de naam al doet vermoeden, volgen het Last-in-First-Out (LIFO) Principe. Alsof het stapelen van munten op elkaar, de laatste munt die we op de top is degene die de eerste wordt verwijderd uit de stapel later.

om een stack te implementeren, hebben we daarom twee eenvoudige bewerkingen nodig:

push – voegt een element toe aan de bovenkant van de stack:

pop – verwijdert het element aan de bovenkant van de stapel:

wachtrij

wachtrij volg, zoals de naam al doet vermoeden, het first-in-first-out (fifo) principe. Alsof je in de rij staat voor de filmkaartjes, is de eerste die in de rij staat de eerste die een kaartje koopt en geniet van de film.

om een wachtrij te implementeren, hebben we daarom twee eenvoudige bewerkingen nodig:

enqueue – voegt een element toe aan het einde van de wachtrij:

dequeue – verwijdert het element aan het begin van de wachtrij:

stapels en wachtrijen met behulp van lijsten

Python ‘ s ingebouwde List datastructuur wordt gebundeld met methoden om zowel stack-als wachtrijbewerkingen te simuleren.

laten we een stapel letters bekijken:

We kunnen dezelfde functies gebruiken om een wachtrij te implementeren. De functie pop neemt optioneel de index van het item dat we willen ophalen als argument.

dus we kunnen pop gebruiken met de eerste index van de lijst, d.w.z. 0, om wachtrijachtig gedrag te krijgen.

beschouw een” wachtrij”van vruchten:

opnieuw gebruiken we de append en pop operaties van de lijst om de kern operaties van een wachtrij te simuleren.

Stacks en wachtrijen met de deque Library

Python heeft een deque (uitgesproken als ‘deck’) bibliotheek die een reeks biedt met efficiënte methoden om te werken als een stack of een wachtrij.

deque is een afkorting van Double Ended Queue – een gegeneraliseerde wachtrij die het eerste of laatste element kan krijgen dat is opgeslagen:

Als u meer wilt weten over de deque bibliotheek en andere soorten collecties die Python biedt, kunt u ons artikel over de inleiding tot Python ‘ s Collections Module lezen.

striktere implementaties in Python

als uw code een stack nodig had en u een List opgeeft, is er niets dat een programmeur weerhoudt om insertremove of andere lijstfuncties aan te roepen die de volgorde van uw stack zullen beïnvloeden! Dit ruïneert fundamenteel het punt van het definiëren van een stack, omdat het niet meer functioneert zoals het zou moeten.

Er zijn momenten waarop we ervoor willen zorgen dat alleen geldige bewerkingen kunnen worden uitgevoerd op onze gegevens.

We kunnen klassen maken die alleen de noodzakelijke methoden voor elke gegevensstructuur blootleggen.

om dit te doen, maken we een nieuw bestand genaamd stack_queue.py en definiëren we twee klassen:

de programmeurs die gebruik maken van onze Stack en Queue worden nu aangemoedigd om de methoden te gebruiken om de gegevens te manipuleren.

voorbeelden

stel je voor dat je een ontwikkelaar bent die werkt aan een gloednieuwe tekstverwerker. Je bent belast met het maken van een undo – functie-zodat gebruikers hun acties terug te volgen tot het begin van de sessie.

een stack is een ideale oplossing voor dit scenario. We kunnen elke actie van de gebruiker opnemen door het naar de stack te duwen. Wanneer de gebruiker een actie ongedaan wil maken, zal hij deze uit de stack halen. We kunnen de functie snel simuleren als volgt:

wachtrijen zijn ook wijdverbreid in het programmeren. Denk aan games zoals Street Fighter of Super Smash Brothers. Spelers in die spellen kunnen speciale bewegingen uitvoeren door op een combinatie van knoppen te drukken. Deze knoppencombinaties kunnen in een wachtrij worden opgeslagen.

stel je nu voor dat je een ontwikkelaar bent die werkt aan een nieuw vechtspel. In je spel, elke keer als een knop wordt ingedrukt, wordt een input event afgevuurd. Een tester merkte op dat als knoppen te snel worden ingedrukt het spel alleen de eerste verwerkt en speciale moves zal niet werken!

u kunt dit oplossen met een wachtrij. We kunnen alle invoergebeurtenissen opvragen als ze binnenkomen. Op deze manier maakt het niet uit of invoer gebeurtenissen komen met weinig tijd tussen hen, ze zullen allemaal worden opgeslagen en beschikbaar voor verwerking. Als we de bewegingen verwerken, kunnen we ze dequeue. Een speciale zet kan als volgt worden uitgewerkt:

conclusie

stapels en wachtrijen zijn eenvoudige datastructuren die ons in staat stellen om sequentieel gegevens op te slaan en op te halen. In een stapel, het laatste item dat we invoeren is het eerste dat eruit komt. In een rij, het eerste item dat we invoeren is de eerste come out.

We kunnen items toevoegen aan een stack met behulp van de push operatie en items ophalen met behulp van de pop operatie. Met wachtrijen voegen we items toe met behulp van de enqueue operatie en halen items op met behulp van de dequeue operatie.

in Python kunnen we stapels en wachtrijen implementeren door de ingebouwde List gegevensstructuur te gebruiken. Python heeft ook dedeque bibliotheek die efficiënt stack en wachtrij operaties in één object kan bieden. Tot slot hebben we onze stack-en wachtrijklassen gemaakt voor een betere controle over onze gegevens.

Er zijn veel real-world use cases voor stapels en wachtrijen, door ze te begrijpen kunnen we veel problemen met gegevensopslag op een eenvoudige en effectieve manier oplossen.