Datalogi · Gymnasiet 2 · Datastrukturer · 2.º Período

Stackar och köer

Introduktion till LIFO- och FIFO-principerna genom stackar och köer. Praktiska tillämpningar som ångra-funktioner och utskriftsköer diskuteras.

Kort sammanfattning:Stackar och köer är abstrakta datatyper som styr ordningen i vilken data bearbetas. En stack följer LIFO-principen (Last-In, First-Out), precis som en hög med tallrikar, medan en kö följer FIFO (First-In, First-Out), som en vanlig matkö. Dessa strukturer är fundamentala för hur operativsystem och applikationer hanterar processer.

• Skolverket Kursplaner
• DAODAT0 - 1. Algoritmer och datastrukturer
• DAODAT0 - 4. Problemlösning

Om detta ämne

Stackar och köer är abstrakta datatyper som styr ordningen i vilken data bearbetas. En stack följer LIFO-principen (Last-In, First-Out), precis som en hög med tallrikar, medan en kö följer FIFO (First-In, First-Out), som en vanlig matkö. Dessa strukturer är fundamentala för hur operativsystem och applikationer hanterar processer.

I undervisningen kopplar vi dessa till praktiska exempel som eleverna känner igen: 'ångra'-funktionen i ett ordbehandlingsprogram (stack) eller hur meddelanden väntar på att skickas i en chattapp (kö). Genom att förstå dessa principer lär sig eleverna att strukturera logik för att hantera sekventiella händelser på ett förutsägbart sätt.

Koncepten blir levande när eleverna får simulera dessa flöden genom rollspel eller stationer där de hanterar fysiska objekt enligt strikta regler.

Nyckelfrågor

1. Hur fungerar LIFO och FIFO?
2. Vilka verkliga problem kan lösas med en stack?
3. Hur implementeras en kö effektivt?

Se upp för dessa missuppfattningar

Vanlig missuppfattning

Att man kan ta bort vilket element som helst från en stack.

Vad man ska lära ut istället

Förtydliga att en ren stack bara tillåter åtkomst till det översta elementet. Genom att använda en fysisk behållare där man bara ser det översta föremålet blir begränsningen tydlig.

Vanlig missuppfattning

Att köer och listor är samma sak.

Vad man ska lära ut istället

Förklara att en kö är en begränsad version av en lista med specifika regler för in- och utmatning. Diskussioner om 'gränssnitt' hjälper eleverna att förstå varför vi ibland vill begränsa vad man kan göra med data.

Idéer för aktivt lärande

Rollspel

Funktionsanrop och Stacken

Eleverna simulerar hur en dator hanterar funktionsanrop. När en funktion anropas lägger eleven en lapp på en fysisk stack, och när funktionen är klar tas lappen bort. Detta visar tydligt hur programmet 'hittar tillbaka' till rätt ställe.

20 min·Hela klassen

Simuleringsövning

Kundtjänst-kön

Eleverna får agera ärenden i en kö. De experimenterar med olika typer av köer, som prioritetsköer där vissa 'ärenden' får gå före, och diskuterar hur detta påverkar rättvisa och effektivitet i systemet.

25 min·Smågrupper

Utforskande cirkel

Implementera 'Ångra'

I små grupper skissar eleverna på en algoritm för en enkel rit-app. De ska förklara hur de skulle använda en stack för att spara användarens handlingar så att de kan ångras i rätt ordning.

30 min·Smågrupper

Vanliga frågor

Varför kallas det för 'abstrakta' datatyper?

Det kallas abstrakt eftersom vi definierar hur strukturen beter sig (vad man kan göra med den) snarare än hur den är implementerad i koden. En stack kan byggas med både en array och en länkad lista, men beteendet utåt är detsamma.

Vilka är de bästa hands-on-strategierna för att lära ut stackar och köer?

Att använda fysiska objekt som Pringles-rör för stackar och smala rör för köer är mycket effektivt. När eleverna fysiskt inte kan nå botten av röret utan att tömma toppen först, skapas en omedelbar förståelse för LIFO-principen som är svår att glömma.

Hur används stackar i verklig programmering?

Förutom ångra-funktioner används de för att hantera minne (call stack), utvärdera matematiska uttryck och i algoritmer för att navigera genom labyrinter eller trädstrukturer.

Är prioritetsköer en del av detta moment?

Ja, det är en naturlig förlängning. Det låter eleverna diskutera mer komplexa scenarier, som hur ett operativsystem väljer vilken process som ska få köra på processorn härnäst.