Spring til indhold

FIFO - LIFO

Fra Wikipedia, den frie encyklopædi

FIFO – LIFO er sammenhørende begreber som har at gøre med processer vedrørende en serie ordnede elementer. Matematisk vedrører det området kø-teori. Praktiske eksempler kendes dels fra dagligdagen, dels fra dataområdet. Betegnelse for det logisk første element er head, mens det logisk sidste element benævnes tail.

Folk, der venter i en fysisk FIFO-kø

FIFO står for First In First Out[1] og det står for en traditionel kø. Folk stiller sig f.eks. op i en kø ved en billetluge for at købe biografbilletter, og den der er er kommet først til, bliver betjent først og kan forlade køen, hvorefter den næstfølgende kommer til osv. osv.. Mange steder, f.eks. på stationen, i banker, på posthuset og på apoteket er det blevet almindeligt med kø-automater. Man trækker et nummer, og ved de enkelte kasser er der displays, så man kan følge med i, hvor højt oppe man er i køen. Hvis man kan skønne, at det vil tage en vis tid, før man selv kommer til, kan man gå en tur i mellemtiden og behøver altså ikke fysisk at stille op i en lang række.

Sådanne FIFO-køer er der et væld af i dagligdagen, f.eks. biler, der i kø venter på at komme over et lysreguleret vejkryds, og telefoniske ventekøer udstyret med beroligende musik iblandet stemmebeskeder, der siger: du er nu nummer .. 3 i køen. Vent venligst!, folk der venter på at komme til behandling i en skadestues venteværelse osv.

Et særtilfælde er de såkaldte kø-tilbud, hvor de, der kommer først i køen – eventuelt efter at have overnattet i en sovepose foran butikken – kan være heldige at få et fjernsyn eller lignende til langt under indkøbsprisen.

FIFO-køer opfattes normalt som retfærdige, og det er ikke god tone at klemme sig ind midt i en kø. Man taler også om kø-kultur eller kø-etik.

Udtrykt programmeringsteknisk svarer FIFO til, at nytilkommende elementer føjes til i den bageste ende (tail), mens der tages fra i den modsatte ende (head)

LIFO-stakke spiller en central rolle i mange kortspil og kortkabaler (Paul Cézanne: The Card Players, 1895

LIFO står for Last in First Out[2] og det svarer til det man kalder en stak. Et praktisk eksempel kan være en stak kort i et kortspil med billedsiden opad), hvor spillerne efter tur dels lægger kort på og dels tager kort fra. Måske når man i sådanne tilfælde aldrig helt ned til bunden, idet der kommer flere nye kort til end det antal kort, der bliver taget fra.

I programmeringsteknisk sammenhæng spiller datastakke en stor rolle, fordi de er betingelsen for, at algoritmiske funktioner successivt kan kalde hinanden, eventuelt rekursivt[3]. Denne teknik kan i nogle tilfælde være så hukommelseskrævende, at operationen mislykkes på grund af stack overflow, fordi stakken vokser ud over alle grænser. En måde at omgå problemet på kan være at udnytte harddiskens lagringskapacitet, der normalt er mange gange større end computerhukommelsens, men til gengæld også fungerer meget langsommere.

Udtrykt programmeringsteknisk svarer LIFO til, at nytilkommende elementer føjes til forrest i serien (head), hvilket også er den ende, der tages af fra.

Push, Pop og Peek

[redigér | rediger kildetekst]

At lægge til en stak kaldes i programmeringssammenhæng Push, mens det at tage fra i en stak kaldes Pop. Disse operationer styres begge ved ved hjælp af en såkaldt stakpeger. At aflæse værdien af det øverste element (head) i en stak kaldes Peek.

Buffersystemer

[redigér | rediger kildetekst]

En mellemting mellem FIFO og LIFO er buffersystemer, hvor det er ligegyldigt med rækkefølgen af det, der kommer til og det, der bliver taget fra. F.eks. kan det opdæmmede vandreservoir bag en vandkraftdæmning betragtes som en sådan buffer. I regnfulde perioder ophobes der mere mere vand, end der strømmer igennem turbinerne, hvorimod der i tørre perioder strømmer mere vand gennem turbinerne end det vand, der samtidigt ophobes i vandreservoiret. Hamstring af f.eks. olie til imødegåelse af forventet svingende leverancer og usikker prisudvikling er at andet eksempel fra hverdagen. I modsætning hertil står JIT.

Noter og henvisninger

[redigér | rediger kildetekst]
  1. ^ dansk: først ind – først ud
  2. ^ dansk: sidst ind – først ud
  3. ^ en funktion, der kalder sig selv