LIFO ( eng. sidst ind, først ud , "sidst ind, først ud") er en måde at organisere og manipulere data vedrørende tid og prioriteter på. I en struktureret, lineær, LIFO-organiseret liste kan elementer kun tilføjes til eller fjernes fra den ene ende, kaldet "toppen af listen." [1] Strukturen af LIFO kan illustreres ved eksemplet med en stak plader: for at tage den anden fra toppen, skal du fjerne den øverste, og for at fjerne den sidste, skal du fjerne alle dem, der ligger ovenover .
Udtrykket refererer til de abstrakte principper for listebehandling og midlertidig lagring af data, især når du skal have adgang til et begrænset sæt data i en bestemt rækkefølge. LIFO-princippet gælder, når de sidste data, der tilføjes til en struktur, skal være de første, der skal fjernes eller behandles. En nyttig analogi til en kontormedarbejder: en person kan kun arbejde på én side ad gangen, så det næste dokument føjes til mappen oven på stakken af tidligere. På samme måde har en computer også begrænsninger, såsom bredden af databussen og det faktum, at systemet kun kan manipulere én hukommelsesplacering ad gangen. [2] Den abstrakte LIFO-mekanisme, der bruges i beregninger, er implementeret i rigtige datastrukturer i form af en stak , hvis navn åbenbart refererer til "en stak papir", " en stak plader" osv. balle, stak" ). Begrebet FILO bruges nogle gange som et synonym ( engelsk først ind, sidst ud - "først ind, sidst ud"), hvilket understreger, at tidligere tilføjelser til listen bør vente, indtil de kommer helt til tops i strukturen, hvorefter de vil blive tilgået. I køteori bruges udtrykket LCFS (sidst til mølle) nogle gange. Forskellen mellem en generisk liste, et array, en kø og en stak bestemmes af reglerne, der bruges i dataadgangsmekanismen. [2] Under alle omstændigheder er adgangen organiseret i LIFO-strukturen i omvendt rækkefølge sammenlignet med køen . "Der er visse, almindelige situationer inden for datalogi, hvor man ønsker at begrænse indsættelser og sletninger til lister, så disse ændringer kun kan forekomme i begyndelsen eller slutningen af listen, men ikke midt i den. To datastrukturer er nyttige i sådanne tilfælde: stakke (butikker) og køer ." [3]
Som synonym for LIFO bruges også begrebet "magasinprincip", som drager en analogi med et våbenmagasin og patroner. [fire]
Stakstrukturer i computersystemer er blandt de grundlæggende og derfor ekstremt vigtige. Det kan siges, at uden muligheden for at organisere data konfigurerbart, herunder med reference til eksekverbar kode , ville computere ikke være et så fleksibelt værktøj, som de er i dag, men ville simpelthen være en dyr regnemaskine til specielle formål, som ENIAC of the Second Verdenskrig med begrænsede kapaciteter og et snævert omfang. [5]
I ordnede datastrukturer bruges stakken som et dynamisk hukommelseselement, hvor et abstrakt koncept - en hardwareafhængig opkaldsstak - bruges til at lagre en kopi af dataene eller en del af dem, det være sig dataelementernes hukommelsesadresser (se: Parameter (programmering)#Videregivelse af en parameter ved reference ) eller en kopi af dataene (overførsel af en parameter efter værdi). Den mest almindelige listebehandlingsopgave er sortering (i leksikografisk rækkefølge , stigende værdi osv.), hvor maskinens handlinger er begrænset til kun at sammenligne to elementer, mens listen oftest indeholder millioner af medlemmer. Der er forskellige strategier (computeralgoritmer ) , der er optimale til at sortere forskellige typer data, men når de implementeres, tyer de alle til brugen af programmer eller subrutiner , som normalt kalder sig selv eller en del af deres kode rekursivt , og med hvert opkald de tilføjer en delvist ordnet liste over elementer til opkaldsstakken. Det er af denne grund, at stakke og rekursioner normalt introduceres parallelt i datastrukturkurser, fordi de er tæt beslægtede. [6]
Det er takket være fleksibiliteten i adgangen til opkaldsstakken med mulighed for dataomgruppering (datablokken organiseret efter den abstrakte LIFO-metode ser ud til kun at være specielt opfundet, så data nemt kan omarrangeres) subrutiner og standardfunktioner modtager de nødvendige data, udføre de opgaver, som de er optimeret til, og videregive information tilbage til det kaldende segment af programmet. [7] Opkaldsstakken i specifikke tilfælde inkluderer adressen på den næste instruktion i det kaldende program, som normalt udfører en handling på "svarene" modtaget fra underrutiner og standardfunktioner. I rekursive opkald involverer disse handlinger typisk at sammenligne det næste element på listen med det returnerede "svar" (for eksempel at vælge mellem to værdier af den største værdi), indtil listen er udtømt.
Derfor, i den virkelige verden af implementeringer af det abstrakte LIFO-princip, ændres antallet af opkaldsstakke ekstremt hyppigt, størrelsen af hver afhænger af antallet af dataelementer, der skal manipuleres. Derfor er det passende at sammenligne LIFO med en bunke hæfter og pjecer, og ikke med en stak tynde ark papir.