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

Deze afbeelding komt uit deze video van 28 min

Hele goede video met uitleg over recursie: https://www.youtube.com/watch?v=AfBqVVKg4GE&t=704s

Uitleg plaatje: Je praat over Alice, halverwege praat je verder over Bob, dan ga je verder met iets over Carol. Als dat klaar is maak je je verhaal over Bob af en kom je weer terug op je verhaal over Alice.

Overeenkomstig kun je functie-aanroepen weergeven.

Dit programma  (in de video in Python) staat in Flowgorithm: StackRecursie.fprg (Zie Domein D: grondslagen)

Opdracht 1:

Open StackRecursie.fprg en ga er stapsgewijs doorheen.

Je krijgt dezelfde Output.

Merk op hoe het programma door de verschillende functies, a, b en c, heengaat.

Eerst wordt de Output gegeven, dan wordt functie b aangeroepen. De rest van functie a wordt op de stack gezet.

Dit klassikaal doorlopen is ook prima en tegelijk op het bord tekenen

De stack bij dit programma ziet er als volgt uit:

Dit is nog geen recursie: Dan moet een functie zichzelf aanroepen

Opdracht 2:

Open het programma: Optellen2Getallen.fprg en run het stapsgewijs.

Teken een stack en teken hierin hoe de stack in dit programma gevuld en geleegd wordt

Opdracht 3:

Open het programma StackRecursie2.fprg en run het stapsgewijs.

1. Wat gaat hier niet goed en waarom?
2. Verander het programma zodanig, dat het op een gegeven moment eindigt. Schrijf in commentaar erbij wat je veranderd hebt en lever jouw versie in.

Open StackRecursie.fprg. Verander het programma zodanig dat dit de uitvoer wordt:

Sla het programma op en lever het in

Opdracht 4:

Open StackRecursie4.fprg en run het stapsgewijs.

Bepaal de uitvoer en teken de stack.

Let op: Als een commando op de stack gezet wordt, worden ook alle waarden van variabelen erop gezet oftewel opgeslagen, die op dat moment in gebruik zijn. Als het programma terugkeert naar dat commando, krijgen de variabelen weer de 'oude' waarde.

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