DATS 2300202008

Prev Up Next

Hei alle sammen!

 

I denne uken så fortsetter vi på i pensumet. Vi er nå over halvveis i kurset, og jeg anbefaler dere alle til å ta en titt på kursinformasjonen for å se hva som gjenstår.  I denne uken så skal vi går gjennom forskjellige typer køer. Det virker kanskje litt kjedelig og enkelt, men er mye mer komplekst enn man kanskje tror til å begynne med. Heldigvis er det relativt greit å forstå om man har en riktig mental modell for å tenke på disse datastrukturene. 

Vi går gjennom pensum som er beskrevet mer i kapittel 4. Husk ukeoppgavene som kommer til hver uke også. 

 

Forskjellige typer køer

I denne videoen går vi gjennom forskjellige typer køer som vi skal bruke: FIFO, LIFO, og deque. En FIFO-kø står for first in first out (vanlig kø), LIFO står for last in first out (stack, eller stabbel med tallerkner), og en deque (uttales deck) står for double ended queue. 

 

LIFO-kø / stack

I denne videoen går vi gjennom datastrukturen stack, og hvordan en stack kan brukes for å representere funksjonskall i Java. 

 

Lenket liste for å lagre en kø

I denne videoen går vi gjennom hvordan vi kan lagre en FIFO og LIFO-kø ved hjelp av en dobbelt lenket liste. 

 

Tabell-basert kø og sirkulære køer

I denne videoen går vi gjennom hvordan en tabell-basert kø kan implementeres. Vi går spesielt igjennom problemet med at hode og hale-pekerene beveger seg utenfor arrayet, og hvordan en sirkulær kø kan effektivt løse dette problemet. 

Forelesning tirsdag

I tirsdagsforelesningen gikk vi gjennom stack, og operasjoner vi kan gjør med en stack. Vi nevnte også hvordan den rekursive algoritmen for å løse Hanois tårn faktisk kan sees på som bruk av stack: via å bruke programstacken i Java.  Vi gikk også gjennom deque, og ikke minst ArrayDeque, som typisk er den mest effektive (array-baserte) datastrukturen i mange programmeringsspråk. Til slutt gikk vi også gjennom sirkulære buffere, og hvordan vi kan kode disse. I forelesning var det noen tekniske problemer, så laget en ekstra video til dere som går gjennom en gang til.