LIFO Cache: esensi, algoritma stack dan cara kerjanya

Apa itu LIFO Cache?

LIFO Cache (Last In First Out Cache) — adalah cache berukuran terbatas yang diimplementasikan berdasarkan stack. Saat menambahkan elemen baru ke cache yang penuh, elemen terbaru (paling atas) dihapus dan elemen baru mengambil tempatnya. Nama «Last In First Out» berarti elemen yang terakhir masuk ke cache akan menjadi yang pertama dihapus.

Kebijakan ini sangat berbeda dari LRU dan FIFO. Sementara LRU berusaha menyimpan data yang paling terkini (berdasarkan waktu akses terakhir), dan FIFO mempertahankan «usia» data, LIFO secara sadar mengorbankan data baru. Ini mungkin tampak tidak logis untuk caching, tetapi untuk skenario tertentu LIFO ternyata menjadi solusi optimal.

Implementasi klasik LIFO Cache menggunakan stack berbasis array atau linked list. Array menyediakan penyimpanan kompak dan lokalitas cache, tetapi memerlukan alokasi memori awal untuk maxSize. Linked list lebih fleksibel, tetapi setiap elemen memerlukan memori tambahan untuk pointer (8–16 byte per elemen).

Operasi Dasar LIFO Cache

Operasi push(value) menambahkan elemen ke bagian atas stack. Jika ukuran telah mencapai maxSize, sebelum penyisipan bagian atas dihapus. Operasi pop() menghapus dan mengembalikan elemen atas — berguna untuk skenario «membatalkan tindakan terakhir». Operasi peek() mengembalikan elemen atas tanpa menghapus — untuk melihat status terakhir yang disimpan tanpa mengubah stack.

Bagaimana LIFO Cache Bekerja

Prinsip kerja LIFO Cache sangat sederhana: semua operasi dilakukan dengan satu ujung struktur — bagian atas stack. Saat menambahkan elemen baru, elemen tersebut ditempatkan di atas. Jika stack penuh, elemen atas didorong keluar (dihapus) dan elemen baru mengambil tempatnya. Penggusuran selalu hanya mempengaruhi satu elemen — bagian atas, sehingga algoritma tidak memerlukan penelusuran atau pencarian.

Sifat ini menjadikan LIFO Cache yang tercepat di antara semua kebijakan penggusuran: semua operasi dilakukan dalam O(1) tanpa struktur data tambahan. Tidak perlu tabel hash untuk pencarian, tidak perlu doubly linked list untuk penataan ulang — pointer sederhana ke bagian atas stack sudah cukup. Memori digunakan secara minimal: hanya untuk menyimpan elemen itu sendiri.

Namun, kesederhanaan memiliki sisi negatif: LIFO Cache tidak mempertimbangkan frekuensi atau waktu akses terakhir ke data. Jika aplikasi pertama meminta data A, B, C, dan kemudian lagi A — saat overflow, C (yang terakhir ditambahkan) akan dihapus, bahkan jika A sudah tidak relevan. Untuk skenario caching umum ini membuat LIFO menjadi pilihan terburuk, karena data baru seringkali paling berharga.

Ukuran Stack dan Manajemen Memori

Untuk LIFO Cache berbasis array, ukuran ditentukan saat pembuatan dan tidak berubah secara dinamis. Jika stack penuh dan terjadi push — elemen atas akan ditimpa. Untuk implementasi pada linked list, memori dialokasikan untuk setiap elemen sesuai kebutuhan, tetapi setelah mencapai batas, node lama diputus dan dapat dikumpulkan oleh garbage collector. Dalam aplikasi mobile disarankan menggunakan array untuk LIFO Cache, karena tidak menimbulkan beban tambahan pada GC.

LIFO vs LRU dan FIFO: Perbandingan Strategi

Pemilihan strategi penggusuran secara langsung mempengaruhi efisiensi caching. LIFO, LRU dan FIFO mewakili pendekatan berbeda untuk satu pertanyaan: elemen mana yang harus dihapus saat overflow? Setiap pendekatan optimal untuk kelas tugasnya masing-masing.

LRU biasanya memberikan hit-ratio terbaik, tetapi membutuhkan lebih banyak memori dan lebih kompleks dalam implementasi. FIFO — kompromi antara performa dan hit-ratio, berguna untuk data streaming. LIFO — yang paling sederhana, tetapi dengan hit-ratio rendah: hanya boleh diterapkan ketika semantik «yang terakhir masuk – pertama keluar» sesuai dengan logika bisnis (navigasi, pembatalan operasi).

Di mana LIFO Cache Diterapkan

Meskipun kesesuaiannya terbatas untuk caching umum, LIFO Cache dapat diterapkan dalam skenario spesifik di mana urutan pemrosesan data terbalik dari urutan kedatangan. Mari kita lihat kasus utama.

Stack Navigasi

Dalam aplikasi mobile, stack navigasi digunakan: saat membuka layar baru, layar tersebut ditempatkan di bagian atas stack, saat menekan «Kembali» — dihapus. Jika kedalaman stack dibatasi (misalnya maksimal 10 layar), LIFO Cache akan secara otomatis menghapus layar terbaru saat melebihi batas. Ini memungkinkan mengontrol konsumsi memori stack navigasi tanpa kehilangan layar yang dibuka sebelumnya.

Stack Undo/Redo

Mekanisme pembatalan tindakan (Undo) — contoh klasik LIFO. Setiap tindakan pengguna disimpan dalam stack. Saat Undo dipanggil, tindakan terakhir dibatalkan dan dipindahkan ke stack Redo. Membatasi ukuran stack melalui LIFO Cache memastikan bahwa saat melebihi batas, tindakan tertua (di dasar stack) tetap ada dan yang terbaru dibuang — yang logis, karena pengguna biasanya membatalkan tindakan baru-baru ini, dan yang lama sudah tidak relevan.

Buffering Perhitungan Sementara

Dalam perhitungan rekursif dengan pengembalian (backtracking), hasil langkah-langkah perantara disimpan dalam urutan LIFO. Ketika buffer meluap, hasil terakhir dibuang — ini dapat diterima, karena algoritma dapat menghitung ulang jika diperlukan. Pendekatan ini digunakan dalam parser, compiler, dan algoritma penelusuran graf dengan batasan kedalaman.

Contoh Kode LIFO Cache

Mari kita lihat implementasi LIFO Cache di Kotlin menggunakan array berukuran tetap. Array memberikan performa terbaik dan konsumsi memori minimal untuk perangkat mobile.

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--  // buang yang tertua saat penuh
        }
        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]
    }
}

Indeks top menunjuk ke bagian atas stack. push meningkatkan top dan menulis nilai; jika array penuh (top == maxSize - 1), sebelum penulisan top dikurangi — bagian atas stack ditimpa, yang mengimplementasikan penggusuran LIFO. Metode pop mengembalikan elemen dan mengurangi top, sedangkan peek hanya membaca elemen atas tanpa mengubah stack.

Contoh: Stack Navigasi dengan LIFO Cache

Mari kita lihat penggunaan LIFO Cache untuk membatasi kedalaman navigasi di Jetpack Compose. Saat membuka layar baru, layar tersebut ditambahkan ke stack, dan saat melebihi batas, layar terbaru akan digusur.

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()
    }
}

Dalam contoh ini, NavigationStack menggunakan LIFO Cache untuk menyimpan riwayat layar. Saat navigateTo dipanggil, layar ditambahkan ke stack, saat goBack — yang terakhir dihapus. Jika pengguna membuka 11 layar dengan batas 10, yang terbaru (ke-11) akan menggeser yang sebelumnya (ke-10) — layar pertama tetap di stack, sesuai dengan harapan pengguna saat kembali. Strategi ini lebih efisien daripada LRU untuk navigasi: menghapus layar yang sudah lama dibuka («halaman utama», «profil») akan menyebabkan perilaku yang tidak terduga.