Post 4 — Stack#
Læringsmål#
De studerende kan efter aktiviteten…
- Forklare hvad en Stack er og hvordan den fungerer (LIFO)
- Bestemme kompleksiteten for push, pop og søgning i en Stack
- Forklare hvorfor Stack er effektiv til push og pop men langsom til søgning
Forudsætninger#
De studerende forventes at kende til:
- Begrebet kompleksitet og O-notation
Kort beskrivelse#
En stak tallerkener simulerer en Stack. Øvelsen er enkel og genkendelig — de fleste har prøvet at stable tallerkener. Push og pop er intuitivt O(1), mens søgning kræver at man tager tallerkener af én ad gangen og dermed er O(n).
Faglig kontekst#
- Semester/fag: 4. semester — Avanceret Programmering
- Holdstørrelse: 6–8 studerende pr. gruppe
- Organisering: Grupper — roterer mellem stationer
Kort beskrivelse#
En stak tallerkener sættes på bordet med en seddel med et tilfældigt ord på hver. De studerende skal tage en tallerken af stakken, lægge en på og finde en tallerken med et bestemt ord.
Materialer#
post4_instruktion.md— instruktionsark til gruppen (print ét pr. gruppe)post4_svar.md— svarark til den enkelte studerende (print ét pr. studerende)post4_svar_facit.md- svarark til underviseren- En stak tallerkener (mindst 8–10)
- Sedler med tilfældige ord og tape eller elastik til at fæstne dem på tallerkenerne
- Blyanter
Tidsforbrug#
Ca. 10 min. pr. gruppe inkl. udfyldning af svarark.
Modtagelse#
Udvidelser#
- Diskuter i plenum: hvornår er Stack den rigtige datastruktur? (undo-funktionalitet, call stack, browser-historik)
- Hvad ville en Queue se ud som fysisk repræsentation?
Noter til underviseren#
- LIFO-princippet (Last In, First Out) behøver ikke nævnes i øvelsen — lad dem opdage det selv
- Giv evt de studerende det udfyldte svarark til sidst til at tjekke deres egne svar med