Gegevensstructuren: Stacks and Queues – Designveloper

Waarom Stacks and Queues?

In tegenstelling tot een array is er bij stacks en queues geen sprake van willekeurige toegang (we kunnen een element niet direct benaderen met een ‘index’). We hebben meestal minder methoden/acties die we kunnen uitvoeren, zoals push(), pop(), peek(), enqueue(), dequeue(), die allemaal uitsluitend betrekking hebben op het element aan het begin of het einde van de Datastructuur.

Maar…

Vraag: Dit klinkt zo beperkend omdat we alleen toegang hebben tot het eerste of het laatste element in de datastructuur. Waarom zouden we ooit zoiets willen gebruiken? Waarom gebruiken we niet gewoon arrays voor meer flexibiliteit?

Antwoord: Stacks en Queues zijn meestal ‘gegevensstructuren van een hoger niveau’ die bovenop gegevensstructuren van een lager niveau (array of gekoppelde lijst) zijn gebouwd om de bewerkingen die we erop kunnen doen te beperken. Dat is een voordeel als we beperkte toegang willen.

Het hebben van deze beperkte mogelijkheid op een datastructuur is een voordeel omdat we kunnen controleren wie deze datastructuur gebruikt die alleen juiste bewerkingen uitvoert die efficiënt zijn. We hoeven ons bijvoorbeeld niet af te vragen of iemand willekeurig een element in het midden van onze lijst heeft ingevoegd, waardoor sommige invarianten in de war zijn geschopt. Dat heeft ons een hoop problemen bespaard. Laten we ze eens van dichterbij bekijken.

Wat is een stack?

Een stack is een lineaire gegevensstructuur met één uiteinde die een echte stack modelleert door twee primaire operaties te hebben, namelijk push en pop.

In de onderstaande afbeelding kunnen we zien dat een gegevenslid van de top van de stack wordt gepopt en een ander eraan wordt toegevoegd. Er is een top pointer die wijst naar het blok aan de top van de stack. Dit komt omdat elementen in een stack altijd worden verwijderd en toegevoegd aan de top van de stapel. Dit gedrag is algemeen bekend als LIFO (Last In First Out).

Stack operaties

Het volgende zijn de 2 basis operaties die kunnen worden uitgevoerd op een stack.

• Push functie: Voegt een element toe aan de top van de stack
• Pop functie: Verwijder het bovenste element (en geef het eventueel terug)

Visualisatie van de basisbewerkingen van de stack

Verder zijn de volgende extra functies voor een stack voorzien om de status ervan te controleren.

• Peek-functie: Geeft het bovenste element van de stapel terug zonder het te verwijderen of te wissen
• isEmpty functie: Controleer of de stapel leeg is of niet
• isFull functie: Controleer of de stapel vol is of niet

Alles werkt aan de bovenkant van de stapel. We hebben geen toegang tot iets anders dan de top. Dit is van cruciaal belang om te begrijpen hoe het werkt.

Complexiteitsanalyse

De volgende complexiteitstabel gaat ervan uit dat u een stack hebt geïmplementeerd met behulp van een gekoppelde lijst

Stacks toepassingen

Wanneer en waar wordt een Stack gebruikt? We gebruiken Stacks veel in het programmeren zonder het zelf op te merken, hier zijn enkele voorbeelden:

• Kan gebruikt worden voor expressie evaluatie (b.v.: een shunting-yard algoritme voor het parsen en evalueren van wiskundige expressies).
• Kan gebruikt worden om functie-aanroepen te implementeren in recursie programmeren.

• Gebruikt door ongedaanmakingsmechanismen in teksteditors om tekst die we hebben geschreven, ongedaan te maken (Cmd + Z op Mac OS en Ctrl + Z op Windows)
• Gebruikt in Browser om achteruit en voorwaarts
• Kan worden gebruikt om een “Depth First Search” (DFS) op een grafiek te doen
• Gebruikt achter de schermen om recursie te ondersteunen door het bijhouden van vorige functie-aanroepen

Wat is een wachtrij?

Een wachtrij is ook een lineaire gegevensstructuur die echte wachtrijen modelleert door twee primaire operaties te hebben, namelijk enqueue (we kunnen dat zien als “in de wachtrij komen”) en dequeue (we kunnen dat ook zien als “uit de wachtrij verwijderen”). Deze structuur wordt “wachtrij” genoemd vanwege het feit dat hij lijkt op een echte wachtrij – (waar mensen in een rij staan te wachten).

Elke wachtrij heeft een voorkant en een achterkant (soms ook “achterkant” genoemd). We voegen elementen in via de achterkant en verwijderen ze via de voorkant.

Een wachtrij is een FIFO-structuur (First In First Out – het element dat als eerste is geplaatst, kan als eerste worden benaderd) die in veel programmeertalen kan worden gevonden.

Queue operaties

De volgende zijn de 3 basis operaties die kunnen worden uitgevoerd op een queue.

• Enqueue functie: Voeg een element toe aan het einde van de wachtrij
• Dequeue functie: Verwijder het element van het begin van de wachtrij
• Gluren functie: Kijken naar de waarde vooraan in de wachtrij zonder deze te verwijderen

Complexiteitsanalyse

Zoals we in de afbeelding kunnen zien, nemen enqueuing- en dequeuing-operaties een constante tijd O(1) in beslag. Controleren of een element in de wachtrij zit, kost echter lineaire tijd O(n), omdat we mogelijk alle elementen zouden moeten scannen.

Er is ook een element verwijdering (niet dequeuing) intern. Dit kost lineaire tijd omdat we in het ergste geval alle elementen moeten scannen.

Toepassingen voor wachtrijen

• Gebruikt om threads te beheren in multithreading.
• Kan worden gebruikt om efficiënt de x meest recent toegevoegde elementen bij te houden
• Web server request management waar we willen dat wie het eerst komt, het eerst maalt. Bijvoorbeeld: Onze webserver kan op elk moment maar maximaal 50 mensen tegelijk bedienen.

Als er in korte tijd 70 verzoeken binnenkomen, dan kunnen we die niet allemaal verwerken. Dus haalt de webserver slechts 50 verzoeken uit de wachtrij en zet hij de overige 20 in de wachtstand. Als de webserver klaar is met het verwerken van een verzoek, dequeuet hij het volgende verzoek en dat blijft hij doen totdat de wachtrij leeg is.

• Breadth-first search (BFS) graph traversal
• Gebruikt om wachtrijsystemen te implementeren (b.v.: prioriteitswachtrijen)
• Gebruikt in netwerkprinter: De printer kan slechts één verzoek tegelijk verwerken. Dus als er andere verzoeken komen terwijl de printer bezig is, zal het programma dat de printer beheert deze verzoeken niet afwijzen, maar ze in een wachtrij plaatsen, wachtend op uitvoering. Het eerste verzoek wordt het eerst bediend (FIFO).

We hopen dat dit artikel u een beeld heeft gegeven van stapels en wachtrijen in het achterhoofd. Vergeet niet om je te abonneren op onze blog en volg Designveloper’s Facebook, Twitter en LinkedIn.

En dit zijn andere artikelen die je misschien leuk vindt:

• Wat is Web Applicatie Architectuur?
• Data Structures and Their Applications
• Wat is Big O Notatie?