LIFO Cache: essentie, stapelalgorithmen en hoe het werkt

Wat is LIFO Cache?

LIFO Cache (Last In First Out Cache) — is een cache van beperkte grootte, geïmplementeerd op basis van een stapel. Bij het toevoegen van een nieuw element aan een volle cache wordt het meest recente (bovenste) element verwijderd en neemt het nieuwe element zijn plaats in. De naam «Last In First Out» betekent dat het element dat als laatste in de cache is gekomen, als eerste wordt verwijderd.

Dit beleid verschilt radicaal van LRU en FIFO. Terwijl LRU probeert de meest actuele gegevens te bewaren (op basis van de laatste toegangstijd) en FIFO de «leeftijd» van gegevens behoudt, offert LIFO bewust verse gegevens op. Dit lijkt misschien onlogisch voor cachen, maar voor bepaalde scenario’s blijkt LIFO de optimale oplossing te zijn.

De klassieke implementatie van LIFO Cache gebruikt een stapel op basis van een array of gelinkte lijst. Een array biedt compacte opslag en cachelokaliteit, maar vereist voorafgaande geheugentoewijzing voor maxSize. Een gelinkte lijst is flexibeler, maar elk element vereist extra geheugen voor pointers (8–16 bytes per element).

Basisbewerkingen van LIFO Cache

De bewerking push(value) voegt een element toe aan de top van de stapel. Als de grootte maxSize heeft bereikt, wordt de top vóór het invoegen verwijderd. De bewerking pop() verwijdert en retourneert het bovenste element — nuttig voor scenario’s van «ongedaan maken van de laatste actie». De bewerking peek() retourneert het bovenste element zonder verwijdering — voor het bekijken van de laatst opgeslagen toestand zonder de stapel te wijzigen.

Hoe LIFO Cache werkt

Het werkingsprincipe van LIFO Cache is uiterst eenvoudig: alle bewerkingen worden uitgevoerd aan één uiteinde van de structuur — de top van de stapel. Bij het toevoegen van een nieuw element wordt het op de top geplaatst. Als de stapel vol is, wordt het bovenste element eruit geduwd (verwijderd) en neemt het nieuwe element zijn plaats in. Verdringing heeft altijd slechts één element — de top — als doel, dus het algoritme vereist geen doorlopen of zoeken.

Deze eigenschap maakt LIFO Cache de snelste van alle verdringingsbeleidsregels: alle bewerkingen worden uitgevoerd in O(1) zonder extra gegevensstructuren. Er is geen hashtabel nodig voor zoeken, geen dubbel gelinkte lijst voor herschikking — een simpele pointer naar de top van de stapel is voldoende. Geheugen wordt minimaal verbruikt: alleen voor de opslag van de elementen zelf.

Eenvoud heeft echter ook een keerzijde: LIFO Cache houdt geen rekening met de frequentie of tijd van laatste toegang tot gegevens. Als de applicatie eerst gegevens A, B, C opvraagt en vervolgens weer A — wordt bij overloop C (laatst toegevoegd) verwijderd, zelfs als A niet meer actueel is. Voor algemene cache-scenario’s maakt dit LIFO de slechtste keuze, omdat verse gegevens vaak het meest waardevol zijn.

Stapelgrootte en geheugenbeheer

Voor LIFO Cache op basis van een array wordt de grootte bij aanmaak ingesteld en verandert niet dynamisch. Als de stapel vol is en er vindt een push plaats — wordt het bovenste element overschreven. Voor implementatie op een gelinkte lijst wordt geheugen toegewezen voor elk element indien nodig, maar bij het bereiken van de limiet wordt de oude knoop losgekoppeld en kan deze worden verzameld door de garbage collector. In mobiele applicaties wordt het gebruik van een array voor LIFO Cache aanbevolen, omdat dit geen extra belasting voor de GC creëert.

LIFO vs LRU en FIFO: vergelijking van strategieën

De keuze van de verdringingsstrategie heeft directe invloed op de efficiëntie van het cachen. LIFO, LRU en FIFO vertegenwoordigen verschillende benaderingen van dezelfde vraag: welk element verwijderen bij overloop? Elke benadering is optimaal voor zijn eigen taakklasse.

LRU geeft meestal de beste hit-ratio, maar vereist meer geheugen en is complexer te implementeren. FIFO — compromis tussen prestaties en hit-ratio, nuttig voor streaminggegevens. LIFO — de eenvoudigste, maar met een lage hit-ratio: het moet alleen worden toegepast wanneer de semantiek «laatst binnen – eerst uit» overeenkomt met de bedrijfslogica (navigatie, ongedaan maken van bewerkingen).

Waar wordt LIFO Cache toegepast

Ondanks de beperkte geschiktheid voor algemeen cachen, vindt LIFO Cache toepassing in specifieke scenario’s waar de verwerkingsvolgorde van gegevens omgekeerd is aan de volgorde van binnenkomst. Laten we de belangrijkste gevallen bekijken.

Navigatiestapels

In mobiele applicaties wordt een navigatiestapel gebruikt: bij het openen van een nieuw scherm wordt deze op de top van de stapel geplaatst, bij het indrukken van «Terug» — verwijderd. Als de diepte van de stapel wordt beperkt (bijvoorbeeld maximaal 10 schermen), zal LIFO Cache automatisch het meest recente scherm verwijderen bij overschrijding van de limiet. Dit maakt het mogelijk om het geheugenverbruik van de navigatiestapel te beheersen zonder eerder geopende schermen te verliezen.

Undo/Redo-stapels

Het mechanisme voor het ongedaan maken van acties (Undo) — een klassiek voorbeeld van LIFO. Elke gebruikersactie wordt opgeslagen in een stapel. Bij het aanroepen van Undo wordt de laatste actie ongedaan gemaakt en verplaatst naar de Redo-stapel. Het beperken van de stapelgroottes via LIFO Cache garandeert dat bij overschrijding van de limiet de oudste acties (op de bodem van de stapel) blijven en de nieuwste worden verwijderd — wat logisch is, omdat de gebruiker meestal recente acties ongedaan maakt en oude niet meer actueel zijn.

Bufferen van tijdelijke berekeningen

Bij recursieve berekeningen met terugkeer (backtracking) worden de resultaten van tussenstappen in LIFO-volgorde opgeslagen. Wanneer de buffer overloopt, wordt het laatste resultaat verwijderd — dit is aanvaardbaar omdat het algoritme het indien nodig opnieuw kan berekenen. Deze benadering wordt gebruikt in parsers, compilers en algoritmen voor graafdoorloping met dieptebeperking.

Voorbeelden van LIFO Cache-code

Laten we de implementatie van LIFO Cache in Kotlin bekijken met behulp van een array met vaste grootte. De array biedt de beste prestaties en minimaal geheugenverbruik voor mobiele apparaten.

class LifoCache<V>(
    private val maxSize: Int
) {
    private val array = arrayOfNulls<V>(maxSize)
    private var top = -1

    fun push(value: V) {
        if (top == maxSize - 1) {
            top--  // verwijder oudste wanneer vol
        }
        array[++top] = value
    }

    fun pop(): V? {
        if (top == -1) return null
        val result = array[top]
        array[top--] = null
        return result
    }

    fun peek(): V? {
        return array[top]
    }
}

De index top verwijst naar de top van de stapel. push verhoogt top en schrijft de waarde; als de array vol is (top == maxSize - 1), wordt top vóór het schrijven verlaagd — de top van de stapel wordt overschreven, wat de LIFO-verdringing implementeert. De methode pop retourneert het element en verlaagt top, terwijl peek eenvoudig het bovenste element leest zonder de stapel te wijzigen.

Voorbeeld: navigatiestapel met LIFO Cache

Laten we het gebruik van LIFO Cache bekijken voor het beperken van de navigatiediepte in Jetpack Compose. Bij het openen van een nieuw scherm wordt het aan de stapel toegevoegd en bij overschrijding van de limiet wordt het meest recente scherm verdrongen.

class NavigationStack(maxDepth: Int = 10) {
    private val cache = LifoCache<Screen>(maxDepth)

    fun navigateTo(screen: Screen) {
        cache.push(screen)
    }

    fun goBack(): Screen? {
        return cache.pop()
    }

    fun currentScreen(): Screen? {
        return cache.peek()
    }
}

In dit voorbeeld gebruikt NavigationStack LIFO Cache voor het opslaan van de schermgeschiedenis. Bij aanroep van navigateTo wordt het scherm aan de stapel toegevoegd, bij goBack — wordt de laatste verwijderd. Als de gebruiker 11 schermen heeft geopend met een limiet van 10, zal het meest recente (11e) het vorige (10e) verdringen — het eerste scherm blijft in de stapel, wat overeenkomt met de verwachtingen van de gebruiker bij terugkeer. Deze strategie is efficiënter dan LRU voor navigatie: het verwijderen van lang geleden geopende schermen («startpagina», «profiel») zou leiden tot onverwacht gedrag.