Inleiding

Gegevensstructuren organiseren de opslag in computers, zodat we efficiënt gegevens kunnen openen en wijzigen. Stapels en wachtrijen behoren tot de vroegste gegevensstructuren die in de informatica zijn gedefinieerd.

Zelfs eenvoudig te leren en eenvoudig te implementeren, worden ze veel gebruikt en u zult ze waarschijnlijk in uw software tegenkomen voor verschillende taken.

Het is gebruikelijk dat stapels en wachtrijen worden geïmplementeerd met een matrix of een gekoppelde lijst. We zullen vertrouwen op de List datastructuur om zowel Stacks als Queues te accommoderen.

Hoe werken ze?

Stack

Stacks, zoals de naam al doet vermoeden, volgen het Last-in-First-Out (LIFO) principe. Alsof je munten op elkaar stapelt, is de munt die je als laatste op de stapel legt, de munt die later als eerste van de stapel wordt gehaald.

Om een stapel te implementeren, hebben we dus twee eenvoudige operaties nodig:

• push – voegt een element toe aan de top van de stapel:

• pop – verwijdert het element bovenaan de stapel:

Queue

Queues volgen, zoals de naam al doet vermoeden, het First-in-First-Out (FIFO) principe. Alsof je in de rij staat voor een bioscoopkaartje, is de eerste die in de rij gaat staan, de eerste die een kaartje koopt en van de film kan genieten.

Om een wachtrij te implementeren, hebben we daarom twee eenvoudige operaties nodig:

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

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

Stacks and Queues using Lists

Python’s ingebouwde List datastructuur wordt geleverd met methoden om zowel stack- als queue-operaties te simuleren.

Laten we eens kijken naar een stapel letters:

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 kunnen we pop gebruiken met de eerste index van de lijst, d.w.z. 0, om een wachtrij-achtig gedrag te krijgen.

Bedenk een “wachtrij” van vruchten:

Ook hier gebruiken we de append en pop bewerkingen van de lijst om de kernbewerkingen van een wachtrij te simuleren.

Stacks and Queues with the Deque Library

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

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

Als je meer wilt weten over de deque bibliotheek en andere soorten verzamelingen die Python biedt, kun je ons Introductie tot Python’s Verzamelingen Module artikel lezen.

Stricter implementaties in Python

Als uw code een stack nodig heeft en u biedt een List, dan is er niets dat een programmeur tegenhoudt om insert, remove of andere lijst functies aan te roepen die de volgorde van uw stack beïnvloeden! Dit ruïneert fundamenteel het punt van het definiëren van een stack, omdat het niet langer functioneert zoals het zou moeten.

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

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

Daartoe maken we een nieuw bestand met de naam stack_queue.py en definiëren we twee klassen:

De programmeurs die onze Stack en Queue gebruiken, worden nu aangemoedigd om in plaats daarvan de verstrekte methoden te gebruiken om de gegevens te manipuleren.

Voorbeelden

Stel u voor dat u een ontwikkelaar bent die aan een gloednieuwe tekstverwerker werkt. U bent belast met het maken van een undo-functie – waarmee gebruikers hun acties kunnen terugdraaien tot het begin van de sessie.

Een stack is een ideale pasvorm voor dit scenario. We kunnen elke actie van de gebruiker vastleggen door deze naar de stack te duwen. Wanneer de gebruiker een actie ongedaan wil maken, haalt hij die uit de stapel. We kunnen de functie snel als volgt simuleren:

Queues worden ook veel gebruikt in programmeren. Denk aan spellen als Street Fighter of Super Smash Brothers. Spelers in die spellen kunnen speciale bewegingen uitvoeren door een combinatie van knoppen in te drukken. Deze knoppencombinaties kunnen worden opgeslagen in een wachtrij.

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

Dat kun je oplossen met een wachtrij. We kunnen alle invoer gebeurtenissen enqueue-en als ze binnenkomen. Op deze manier maakt het niet uit of input events met weinig tijd ertussen komen, ze worden allemaal opgeslagen en zijn beschikbaar voor verwerking. Als we de zetten aan het verwerken zijn, kunnen we ze de-queue zetten. Een speciale zet kan als volgt worden uitgewerkt:

Conclusie

Stacks en queues zijn eenvoudige datastructuren die ons in staat stellen om gegevens sequentieel op te slaan en op te halen. In een stack is het laatste item dat we invoeren het eerste dat eruit komt. In een wachtrij is het eerste item dat we invoeren het eerste dat eruit komt.

We kunnen items aan een stack toevoegen met de bewerking push en items opvragen met de bewerking pop. Met wachtrijen voegen we items toe met de enqueue-bewerking en halen we items op met de dequeue-bewerking.

In Python kunnen we stapels en wachtrijen implementeren door gewoon de ingebouwde List-gegevensstructuur te gebruiken. Python heeft ook de deque bibliotheek die efficiënt stack en wachtrij operaties in één object kan leveren. Ten slotte hebben we onze stack en queue klassen voor strakkere controle van onze gegevens.

Er zijn veel real-world use cases voor stacks en wachtrijen, het begrijpen van hen stelt ons in staat om veel data-opslag problemen op te lossen op een eenvoudige en effectieve manier.