Les 10 - 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 kan je een stack programmeren in python.

Omschrijf kort de werking van een queue (wachtrij)

Wat wordt er bedoeld met het FIFO principe?

Om het datatype queue te gebruiken in python moet er eerst een library (bibliotheek) geladen worden. Leg kort uit waarom.

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

from queue import Queue

kassa = Queue()

kassa.put("klant 1")

kassa.put("klant 2")

kassa.put("klant 3")

Bekijk de python code die hier rechts staat. Met welke code lees je in alle elementen uit de queue uit?

1. while kassa.empty(): print(kassa.get())
2. while not kassa.empty(): print(kassa.put())
3. while kassa.empty(): print(kassa.put())
4. while not kassa.empty(): print(kassa.get())

Stack

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

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.

Werking

Als een element wordt toegevoegd aan een stack wordt dit append genoemd. Wordt een element uit de stack gehaald dan noemen we dit pop.

Declaratie stack in python

internetGeschiedenis = [ 

  "www.google.nl",

  "www.vlietlandcollege.nl"]

Toevoegen elementen aan een stack in python

Om een element aan een stack toe te voegen maak je gebruik van de functie append().

internetGeschiedenis = [

  "www.google.nl",

  "www.vlietlandcollege.nl"]

internetGeschiedenis.append("www.wikipedia.nl")

Eelementen uit een stack ophalen in python

Om een element uit een stack op te halen maak je gebruik van de functie pop().

internetGeschiedenis = [

  "www.google.nl",

  "www.vlietlandcollege.nl"]

print(internetGeschiedenis.pop())

Tel aantal elementen in een stack in python

Om het aantal elementen in een stack te tellen kan gebruik worden gemaakt van de functie len(). In ondertaand voorbeeld staat de functie len() in de functie print(). De functie len() geeft een getal terug. De functie print kan echter alleen overweg met strings. Daarom staat voor de functie len() de functie str().

internetGeschiedenis = [

  "www.google.nl",

  "www.vlietlandcollege.nl"]

print(str(len(internetGeschiedenis)))

Alle elementen uit een stack ophalen in python

Om alle elementen uit een stack op te halen kan een iteratie gecombineerd worden met de functie len().

internetGeschiedenis = [

  "www.google.nl",

  "www.fundament-online.nl"]

while len(internetGeschiedenis) > 0: 

  print(internetGeschiedenis.pop())

Bekijk de python code. Wat is de uitvoer van de code?

mijnOrder = []

mijnOrder.append("Hamburger")

mijnOrder.append("Frietjes")

mijnOrder.append("Cola")

print(mijnOrder.pop())

print(len(mijnOrder))

1. Hamburger 2
2. Cola 3
3. Cola 2
4. Hamburger 3