LIFO Cache: Wesen, Stack-Algorithmus und Funktionsweise

Was ist LIFO Cache?

LIFO Cache (Last In First Out Cache) ist ein Cache fester Größe, der auf einem Stack implementiert ist. Wenn einem vollen Cache ein neues Element hinzugefügt wird, wird das aktuellste (oberste) Element entfernt und das neue Element nimmt seinen Platz ein. Der Name „Last In First Out“ bedeutet, dass das Element, das zuletzt in den Cache gelangt ist, zuerst entfernt wird.

Diese Richtlinie unterscheidet sich grundlegend von LRU und FIFO. Während LRU versucht, die relevantesten Daten (nach letzter Zugriffszeit) zu behalten und FIFO das „Alter“ der Daten bewahrt, opfert LIFO bewusst neue Daten. Das mag für Caching unintuitiv erscheinen, aber für bestimmte Szenarien erweist sich LIFO als optimale Lösung.

Eine klassische LIFO-Cache-Implementierung verwendet einen Stack auf Basis eines Arrays oder einer verketteten Liste. Ein Array bietet kompakte Speicherung und Cache-Lokalität, erfordert jedoch eine vorherige Speicherzuweisung für maxSize. Eine verkettete Liste ist flexibler, benötigt aber pro Element zusätzlichen Speicher für Zeiger (8–16 Byte pro Element).

Grundlegende LIFO-Cache-Operationen

Die push(value)-Operation fügt ein Element an der Spitze des Stacks hinzu. Wenn die Größe maxSize erreicht, wird die Spitze vor dem Einfügen entfernt. Die pop()-Operation entfernt und gibt das oberste Element zurück — nützlich für Szenarien zum „Rückgängigmachen der letzten Aktion“. Die peek()-Operation gibt das oberste Element zurück, ohne es zu entfernen — zum Anzeigen des letzten gespeicherten Zustands ohne Änderung des Stacks.

Wie LIFO Cache funktioniert

Das Funktionsprinzip von LIFO Cache ist denkbar einfach: Alle Operationen werden an einem Ende der Struktur durchgeführt — der Spitze des Stacks. Wenn ein neues Element hinzugefügt wird, wird es oben platziert. Wenn der Stack voll ist, wird das oberste Element entfernt und das neue nimmt seinen Platz ein. Die Verdrängung betrifft immer nur ein Element — die Spitze — daher benötigt der Algorithmus keine Iteration oder Suche.

Diese Eigenschaft macht LIFO Cache zum schnellsten aller Verdrängungsrichtlinien: Alle Operationen laufen in O(1) ohne zusätzliche Datenstrukturen. Keine Hash-Tabelle für Nachschlagevorgänge, keine doppelt verkettete Liste für Umordnung — nur ein einfacher Zeiger auf die Spitze des Stacks. Der Speicherverbrauch ist minimal: nur die Speicherung der Elemente selbst.

Allerdings hat Einfachheit eine Kehrseite: LIFO Cache berücksichtigt weder die Häufigkeit noch die letzte Zugriffszeit auf Daten. Wenn eine Anwendung zunächst die Daten A, B, C und dann erneut A anfordert, wird C (das zuletzt hinzugefügte) verdrängt, wenn der Cache voll ist, selbst wenn A nicht mehr relevant ist. Für allgemeine Caching-Szenarien macht dies LIFO zur schlechtesten Wahl, da neue Daten oft am wertvollsten sind.

Stack-Größe und Speicherverwaltung

Für einen array-basierten LIFO Cache wird die Größe bei der Erstellung festgelegt und ändert sich nicht dynamisch. Wenn der Stack voll ist und ein Push erfolgt, wird das oberste Element überschrieben. Für eine Implementierung mit verketteter Liste wird Speicher pro Element nach Bedarf zugewiesen, aber wenn das Limit erreicht ist, wird der alte Knoten abgetrennt und kann vom Garbage Collector eingesammelt werden. In mobilen Anwendungen wird empfohlen, ein Array für LIFO Cache zu verwenden, da es keine zusätzliche Belastung für den GC erzeugt.

LIFO vs. LRU und FIFO: Strategievergleich

Die Wahl der Verdrängungsstrategie wirkt sich direkt auf die Caching-Effizienz aus. LIFO, LRU und FIFO repräsentieren unterschiedliche Ansätze für dieselbe Frage: Welches Element soll bei vollem Cache entfernt werden? Jeder Ansatz ist für seine eigene Aufgabenklasse optimal.

LRU bietet typischerweise die beste Trefferquote, benötigt aber mehr Speicher und ist aufwändiger zu implementieren. FIFO ist ein Kompromiss zwischen Leistung und Trefferquote, nützlich für Streaming-Daten. LIFO ist am einfachsten, aber mit niedriger Trefferquote: Es sollte nur verwendet werden, wenn die Semantik „‚Zuletzt herein, zuerst hinaus‘“ mit der Geschäftslogik (Navigation, Rückgängig-Operationen) übereinstimmt.

Wo LIFO Cache eingesetzt wird

Trotz seiner begrenzten Eignung für allgemeines Caching findet LIFO Cache in bestimmten Szenarien Verwendung, in denen die Reihenfolge der Datenverarbeitung umgekehrt zur Reihenfolge des Eintreffens ist. Betrachten wir die wichtigsten Fälle.

Navigationsstapel

In mobilen Anwendungen wird ein Navigationsstapel verwendet: Wenn ein neuer Bildschirm geöffnet wird, wird er oben auf den Stapel gelegt; wenn die „Zurück“-Taste gedrückt wird, wird er entfernt. Wenn die Stapeltiefe begrenzt ist (z. B. maximal 10 Bildschirme), entfernt LIFO Cache automatisch den aktuellsten Bildschirm, wenn das Limit überschritten wird. Dadurch können Sie den Speicherverbrauch des Navigationsstapels kontrollieren, ohne zuvor geöffnete Bildschirme zu verlieren.

Rückgängig/Wiederholen-Stapel

Der Rückgängig-Mechanismus (Undo) ist ein klassisches Beispiel für LIFO. Jede Benutzeraktion wird in einem Stapel gespeichert. Wenn Undo aufgerufen wird, wird die letzte Aktion rückgängig gemacht und in den Wiederholen-Stapel verschoben. Die Begrenzung der Stapelgröße über LIFO Cache stellt sicher, dass bei Überschreitung des Limits die ältesten Aktionen (am Boden des Stapels) erhalten bleiben, während die aktuellsten verworfen werden — was logisch ist, da der Benutzer normalerweise aktuelle Aktionen rückgängig macht, während alte nicht mehr relevant sind.

Zwischenspeicherung temporärer Berechnungen

Bei rekursiven Berechnungen mit Rücksetzung (Backtracking) werden die Ergebnisse von Zwischenschritten in LIFO-Reihenfolge gespeichert. Wenn der Puffer überläuft, wird das letzte Ergebnis verworfen — dies ist akzeptabel, da der Algorithmus es bei Bedarf neu berechnen kann. Dieser Ansatz wird in Parsern, Compilern und Graphendurchlauffalgorithmen mit Tiefenbegrenzung verwendet.

LIFO Cache Codebeispiele

Betrachten wir eine LIFO-Cache-Implementierung in Kotlin mit einem Array fester Größe. Ein Array bietet die beste Leistung und den geringsten Speicherverbrauch für mobile Geräte.

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--  // discard oldest when full
        }
        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]
    }
}

Der Index top zeigt auf die Spitze des Stacks. push erhöht top und schreibt den Wert; wenn das Array voll ist (top == maxSize - 1), wird top vor dem Schreiben dekrementiert — die Stack-Spitze wird überschrieben, was die LIFO-Verdrängung implementiert. Die Methode pop gibt das Element zurück und dekrementiert top, während peek einfach das oberste Element liest, ohne den Stack zu verändern.

Beispiel: Navigationsstapel mit LIFO Cache

Betrachten Sie die Verwendung von LIFO Cache zur Begrenzung der Navigationstiefe in Jetpack Compose. Wenn ein neuer Bildschirm geöffnet wird, wird er zum Stapel hinzugefügt, und wenn das Limit überschritten wird, wird der aktuellste Bildschirm entfernt.

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 diesem Beispiel verwendet NavigationStack LIFO Cache, um den Bildschirmverlauf zu speichern. Wenn navigateTo aufgerufen wird, wird der Bildschirm zum Stapel hinzugefügt; wenn goBack aufgerufen wird, wird der letzte entfernt. Wenn der Benutzer bei einem Limit von 10 11 Bildschirme geöffnet hat, verdrängt der aktuellste (11.) den vorherigen (10.) — der erste Bildschirm bleibt im Stapel, was den Erwartungen des Benutzers beim Zurücknavigieren entspricht. Diese Strategie ist für die Navigation effizienter als LRU: Das Entfernen von lange geöffneten Bildschirmen („Startseite“, „Profil“) würde zu unerwartetem Verhalten führen.