Datalogi · Gymnasiet 1 · Datastrukturer och abstraktion · 4.º Período

Stackar och köer

Introduktion till LIFO (Last In, First Out) och FIFO (First In, First Out) principerna. Vi implementerar stackar och köer och undersöker deras användningsområden.

Kort sammanfattning:Stackar och köer är fundamentala abstrakta datatyper som styr hur data bearbetas i en viss ordning. I Datalogi 1 lär sig eleverna principerna LIFO (Last In, First Out) för stackar och FIFO (First In, First Out) för köer. Dessa strukturer är avgörande för att förstå allt från hur webbläsarens bakåtknapp fungerar till hur operativsystem hanterar utskriftsjobb.

• Skolverket Kursplaner
• Skolverket DAODAT01: Abstrakta datatyper.
• Skolverket DAODAT01: Tillämpning av stackar och köer.

Om detta ämne

Stackar och köer är fundamentala abstrakta datatyper som styr hur data bearbetas i en viss ordning. I Datalogi 1 lär sig eleverna principerna LIFO (Last In, First Out) för stackar och FIFO (First In, First Out) för köer. Dessa strukturer är avgörande för att förstå allt från hur webbläsarens bakåtknapp fungerar till hur operativsystem hanterar utskriftsjobb.

Genom att studera dessa strukturer tränar eleverna sin förmåga att välja rätt verktyg för rätt problem. Kursplanen betonar förståelse för abstrakta datatyper och deras tillämpningar. Eleverna greppar bäst skillnaden mellan stackar och köer genom att simulera dem med fysiska objekt, vilket tydliggör hur element läggs till och tas bort i de olika modellerna.

Nyckelfrågor

1. Vad kännetecknar en stack jämfört med en kö?
2. I vilka verkliga tillämpningar används LIFO och FIFO?
3. Hur implementeras dessa strukturer i kod?

Se upp för dessa missuppfattningar

Vanlig missuppfattning

Att man kan ta bort ett element i mitten av en stack.

Vad man ska lära ut istället

Elever tror ofta att stackar fungerar som vanliga listor. Genom att använda en fysisk behållare där man bara når det översta objektet blir det tydligt att man måste 'poppa' sig ner till det element man vill ha.

Vanlig missuppfattning

Att FIFO och LIFO bara är teoretiska begrepp.

Vad man ska lära ut istället

Många ser inte kopplingen till vardagen. Genom att analysera hur en skrivarkö fungerar (först in, först ut) blir konceptet FIFO omedelbart logiskt och användbart.

Idéer för aktivt lärande

Simuleringsövning

Tallriksstacken vs. Bankkön

Eleverna använder fysiska objekt (t.ex. böcker för stacken och en kö till dörren för kön). De utför operationer som 'push/pop' och 'enqueue/dequeue' för att se vilken ordning objekten kommer ut i.

25 min·Hela klassen

Utforskande cirkel

Bakåtknappens logik

I smågrupper ska eleverna designa en algoritm för en webbläsares historik med hjälp av en stack. De ska rita upp vad som händer när man besöker nya sidor och när man trycker på 'bakåt'.

40 min·Smågrupper

EPA (Enskilt-Par-Alla)

Verkliga tillämpningar

Eleverna får en lista på system (t.ex. ångra-funktion i Word, kundtjänst-telefonkö, diskmaskin). De diskuterar i par om varje system bäst representeras av en stack eller en kö och motiverar varför.

20 min·Par

Vanliga frågor

Vad betyder LIFO och FIFO?

LIFO står för Last In, First Out (Sist in, först ut) och används för stackar. FIFO står för First In, First Out (Först in, först ut) och används för köer. Det beskriver ordningen i vilken elementen lämnar datastrukturen.

Var används en stack i verklig programmering?

Stackar används för att hantera funktionsanrop (call stack), för 'ångra'-funktioner i program, och för att utvärdera matematiska uttryck. Det är en struktur som är perfekt när man behöver gå tillbaka i sina steg.

Hur kan aktivt lärande hjälpa vid undervisning om abstrakta datatyper?

Genom att låta eleverna fysiskt bygga och manipulera stackar och köer med konkreta föremål, flyttas fokus från kodsyntax till den logiska strukturen. Det gör det lättare för dem att senare implementera dessa strukturer i kod eftersom de har en tydlig mental bild av hur de fungerar.

Vad är 'stack overflow'?

Det är ett fel som uppstår när en stack (ofta call stacken) får slut på minne för att för många element har lagts till utan att tas bort. Det händer ofta vid felaktig rekursion där en funktion anropar sig själv i all oändlighet.