Les 11 - Stack

Datastructuren
Stack
1 / 22
volgende
Slide 1: Tekstslide
InformaticaMiddelbare schoolhavo, vwoLeerjaar 4-6

In deze les zitten 22 slides, met interactieve quizzen, tekstslides en 1 video.

time-iconLesduur is: 50 min

Onderdelen in deze les

Datastructuren
Stack

Slide 1 - Tekstslide

Deze slide heeft geen instructies

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.

Slide 2 - Tekstslide

Deze slide heeft geen instructies

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.

Slide 3 - Tekstslide

Deze slide heeft geen instructies

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.

Slide 4 - Tekstslide

Deze slide heeft geen instructies

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.

Slide 5 - Tekstslide

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.

Slide 6 - Tekstslide

Deze slide heeft geen instructies

Schematiseren

Slide 7 - Tekstslide

Deze slide heeft geen instructies

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

Slide 8 - Tekstslide

Deze slide heeft geen instructies

Deze afbeelding komt uit deze video van 28 min

Slide 9 - Tekstslide

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.

Slide 10 - Tekstslide

Overeenkomstig kun je functie-aanroepen weergeven.
Dit programma  (in de video in Python) staat in Flowgorithm: StackRecursie.fprg (Zie Domein D: grondslagen)

Slide 11 - Tekstslide

Deze slide heeft geen instructies

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.

Slide 12 - Tekstslide

Dit klassikaal doorlopen is ook prima en tegelijk op het bord tekenen
De stack bij dit programma ziet er als volgt uit:


Slide 13 - Tekstslide

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

Slide 14 - Tekstslide

Deze slide heeft geen instructies

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.

Slide 15 - Tekstslide

Deze slide heeft geen instructies

Open StackRecursie.fprg. Verander het programma zodanig dat dit de uitvoer wordt:
Sla het programma op en lever het in

Slide 16 - Tekstslide

Deze slide heeft geen instructies

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.

Slide 17 - Tekstslide

Deze slide heeft geen instructies

Slide 18 - Video

Deze slide heeft geen instructies

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()

Slide 19 - Open vraag

kassa.put("klant 1")

Wat wordt er bedoeld met het FIFO principe?

Slide 20 - Open vraag

Deze slide heeft geen instructies

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?

Slide 21 - Tekstslide

Deze slide heeft geen instructies

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

Slide 22 - Tekstslide

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

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

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