LIFO ( eng. sist in, först ut , "sist in, först ut") är ett sätt att organisera och manipulera data gällande tid och prioriteringar. I en strukturerad, linjär, LIFO-organiserad lista kan objekt bara läggas till eller tas bort från ena änden, kallad "överst på listan". [1] Strukturen hos LIFO kan illustreras med exemplet med en stapel tallrikar: för att ta den andra från toppen måste du ta bort den översta, och för att ta bort den sista måste du ta bort alla de som ligger ovanför .
Termen hänvisar till de abstrakta principerna för listbehandling och tillfällig lagring av data, i synnerhet när du behöver kunna komma åt en begränsad uppsättning data i en viss ordning. LIFO-principen gäller när den sista data som läggs till i en struktur måste vara den första som tas bort eller bearbetas. En användbar analogi till en kontorsarbetare: en person kan bara arbeta på en sida i taget, så nästa dokument läggs till i mappen ovanpå högen med tidigare. På samma sätt har en dator också begränsningar, som databussens bredd och att systemet bara kan manipulera en minnesplats åt gången. [2] Den abstrakta LIFO-mekanismen som används i beräkningar är implementerad i verkliga datastrukturer i form av en stack , vars namn uppenbarligen refererar till "en bunt papper", " en bunt tallrikar" etc. bale, stack" ). Termen FILO används ibland som en synonym ( engelska först in, sist ut - "först in, sist ut"), vilket understryker att tidigare tillägg till listan bör vänta tills de stiger till toppen i strukturen, varefter de kommer att nås. I köteorin används ibland termen LCFS (sist till kvarn, först till kvarn). Skillnaden mellan en generisk lista, en array, en kö och en stack bestäms av reglerna som används i dataåtkomstmekanismen. [2] I alla fall är åtkomsten organiserad i LIFO-strukturen i omvänd ordning jämfört med kön . ”Det finns vissa, vanliga situationer inom datavetenskap där man vill begränsa infogning och radering till listor så att dessa ändringar bara kan ske i början eller slutet av listan, men inte i mitten av den. Två datastrukturer är användbara i sådana fall: stackar (butiker) och köer ." [3]
Som en synonym till LIFO används också termen "tidningsprincipen", som drar en analogi med ett vapenmagasin och patroner. [fyra]
Stackstrukturer i datorsystem är bland de grundläggande och därför extremt viktiga. Det kan sägas att utan möjligheten att organisera data konfigurerbart, inklusive med hänvisning till körbar kod , skulle datorer inte vara ett så flexibelt verktyg som de är idag, utan skulle helt enkelt vara en dyr kalkylator för speciella ändamål, som ENIAC of the Second Världskriget har begränsad kapacitet och en snäv omfattning. [5]
I ordnade datastrukturer används stacken som ett dynamiskt minneselement, där ett abstrakt koncept - en hårdvaruberoende anropsstack - används för att lagra en kopia av datan eller en del av den, vare sig det är minnesadresserna för dataelement (se: Parameter (programmering)#Att skicka en parameter genom referens ) eller en kopia av data (som skickar en parameter efter värde). Den vanligaste listbearbetningsuppgiften är sortering (i lexikografisk ordning , stigande värde, etc.), där maskinens åtgärder är begränsade till att bara jämföra två element, medan listan oftast innehåller miljontals medlemmar. Det finns olika strategier (datoralgoritmer ) som är optimala för att olika typer av data ska sorteras, men när de implementeras tar de alla till användning av program eller subrutiner , som vanligtvis kallar sig själva eller delar av sin kod rekursivt , och med varje anrop. de lägger till en delvis ordnad lista med element till samtalsstacken. Det är av denna anledning som stackar och rekursioner vanligtvis introduceras parallellt i datastrukturkurser, eftersom de är nära besläktade. [6]
Det är tack vare flexibiliteten för åtkomst till samtalsstacken med möjlighet till dataomgruppering (datablocket organiserat enligt den abstrakta LIFO-metoden tycks ha uppfunnits speciellt bara så att data enkelt kan ordnas om) subrutiner och standardfunktioner tar emot nödvändiga data, utför de uppgifter som de är optimerade för och skicka information tillbaka till det anropande segmentet i programmet. [7] Anropsstacken inkluderar i specifika fall adressen till nästa instruktion i det anropande programmet, som vanligtvis utför någon åtgärd på "svaren" som tas emot från subrutiner och standardfunktioner. I rekursiva anrop innebär dessa åtgärder vanligtvis att jämföra nästa element i listan med det returnerade "svaret" (till exempel att välja mellan två värden med det största värdet) tills listan är uttömd.
Därför, i den verkliga världen av implementeringar av den abstrakta LIFO-principen, ändras antalet samtalsstackar extremt ofta, storleken på var och en beror på antalet dataelement som krävs för att manipuleras. Därför är det lämpligt att jämföra LIFO med en hög med häften och broschyrer, och inte med en hög med tunna pappersark.