Les 11 - Stack

• Informatica
• Middelbare school
• havo, vwo
• Leerjaar 4-6

Datastructuren

Stack

Leerdoel

Aan het eind van de les ken je de kenmerken van een stack, ken je het principe Last-in, First-out (LIFO) en heb je met een stack geoefend in Flowgorithm.

Last-in, First-out (LIFO)

In en tekstverwerker heb je een knop met wijzigingen ongedaan maken. Iedere wijziging wordt bijgehouden in een stack. Wil je een wijziging ongedaan maken dan hoef je alleen maar op wijziging ongedaan maken te klikken en je laatste wijziging wordt ongedaan gemaakt. 

Dit principe wordt Last-in, First-out (LIFO) genoemd.

Stack

Een stack is te vergelijken met een queue (rij/array), maar werkt precies andersom. Het element dat als laatste is toegevoegd zal ook al eerste weer uit de stack worden gehaald.

Kaarten sorteren op waarde

• Pak de eerste kaart en leg die zichtbaar op tafel. Dit wordt de eerste stapel.
• Pak de volgende kaart. Kijk of de kaart een grotere waarde heeft dan de kaart op de eerste stapel.
        - Zo ja, dan leg je de kaart rechts naast de eerste stapel. Dit wordt een nieuwe stapel.
        - Zo nee, dan leg je de kaart bovenop de eerste stapel.
• Doe voor alle volgende kaarten het volgende:
        - Zoek alle stapels waarvan de topkaart even groot is of groter dan de kaart
           die je vasthoudt.
        - Zijn die stapels er? Leg je kaart dan op de stapel met de kleinste topkaart.
        - Is je kaart groter dan alle topkaarten? Begin dan een nieuwe stapel aan
          de rechterkant.

Dit heet de Verdeelfase. Volgende dia: De verzamelfase

Verzamelfase:

De kaart met de kleinste waarde ligt nu bovenop de meest linker stapel. Pak die.

Pak nu steeds de topkaart met de kleinste waarde van de andere stapels.

Schematiseren

Een stack is een datastructuur.

We hebben al kennis gemaakt met de boomstructuur en de rij: Manieren om data te ordenen.

In een boomstructuur kan snel gezocht worden, zoals bv. in de mappen van Windows verkenner.

Een rij wordt gebruikt als data volgens het FIFO-principe benaderd moeten worden: First In, First Out

Een stack werkt volgens het LIFO-principe: Last In, First Out

Hieronder staat een declaratie van een queue in python. Schrijf de code om een klant (element) toe te voegen aan de wachtrij.

from queue import Queue

kassa = Queue()

kassa.put("klant 1")

Wat wordt er bedoeld met het FIFO principe?

Opdracht

1. Soorteer de kaarten op kleur. Beschrijf hoe jullie dit doen
   
   
2. Vergelijk jullie methode met die van jullie buren, welke is beter?
   
   
3. Je gaat de stapel nu sorteren op getallen. Dus eerst allen nullen, dan alle enen, enz. Beschrijf weer hoe jullie dit doen.
   
   
4. Vergelijk jullie methode met die van jullie buren, welke is beter?

Stack: Filmpje wat leuk begint, maar dan toch snel te ingewikkeld wordt

Deze video: Simpel en wat heb je eraan? wel duidelijk

Deze video: De stack wordt vrij duidelijk uitgelegd en omgezet naar pseudocode, waarin je recursie ziet

Begin leuk, dan ingewikkeld: https://youtu.be/QLhlCwhENzc

Duidelijke animatie, erg simpel: https://youtu.be/1SWr7q121gc

Stack, pseudocode met recursie: https://youtu.be/niBsGw4h5yI