LIFO Cache: kakanyahan, algorithm ng stack at kung paano ito gumagana

Ano ang LIFO Cache?

LIFO Cache (Last In First Out Cache) — ay isang cache na may limitadong laki, na ipinatupad batay sa stack. Kapag nagdadagdag ng bagong elemento sa punong cache, ang pinakabago (pinakaitaas) na elemento ay tinatanggal at ang bago ang pumapalit. Ang pangalang «Last In First Out» ay nangangahulugan na ang elemento na huling pumasok sa cache ang unang tatanggalin.

Ang ganitong polisiya ay radikal na naiiba sa LRU at FIFO. Habang sinusubukan ng LRU na panatilihin ang pinaka-aktuwal na datos (batay sa oras ng huling pag-access), at pinapanatili ng FIFO ang «edad» ng datos, sinasadyang isakripisyo ng LIFO ang sariwang datos. Ito ay maaaring mukhang hindi lohikal para sa caching, ngunit para sa ilang scenario ang LIFO ay lumalabas na pinakamainam na solusyon.

Ang klasikong implementasyon ng LIFO Cache ay gumagamit ng stack na nakabatay sa array o linked list. Ang array ay nagbibigay ng kompaktong imbakan at lokalidad ng cache, ngunit nangangailangan ng paunang alokasyon ng memorya para sa maxSize. Ang linked list ay mas flexible, ngunit ang bawat elemento ay nangangailangan ng karagdagang memorya para sa mga pointer (8–16 byte bawat elemento).

Mga Pangunahing Operasyon ng LIFO Cache

Ang operasyong push(value) ay nagdaragdag ng elemento sa tuktok ng stack. Kung ang laki ay umabot na sa maxSize, bago ang pagpasok ang tuktok ay tinatanggal. Ang operasyong pop() ay tinatanggal at ibinabalik ang pinakaitaas na elemento — kapaki-pakinabang para sa mga scenario ng «pag-undo ng huling aksyon». Ang operasyong peek() ay ibinabalik ang pinakaitaas na elemento nang hindi tinatanggal — para sa pagtingin ng huling naka-save na estado nang hindi binabago ang stack.

Paano Gumagana ang LIFO Cache

Ang prinsipyo ng trabaho ng LIFO Cache ay napakasimple: lahat ng operasyon ay ginagawa sa isang dulo ng estruktura — ang tuktok ng stack. Kapag nagdaragdag ng bagong elemento, ito ay inilalagay sa tuktok. Kung ang stack ay puno, ang tuktok na elemento ay itinutulak palabas (tinatanggal) at ang bago ang pumapalit. Pagtataboy ay laging nakakaapekto lamang sa isang elemento — ang tuktok, kaya ang algorithm ay hindi nangangailangan ng pag-ikot o paghahanap.

Ang katangiang ito ang gumagawa sa LIFO Cache na pinakamabilis sa lahat ng polisiya ng pagtataboy: lahat ng operasyon ay ginagawa sa O(1) nang walang anumang karagdagang estruktura ng datos. Hindi kailangan ng hash table para sa paghahanap, hindi kailangan ng doubly linked list para sa reorganisasyon — sapat na ang simpleng pointer sa tuktok ng stack. Memorya ay ginagamit nang minimal: para lamang sa pag-imbak ng mga elemento mismo.

Gayunpaman, ang pagiging simple ay may downside: Hindi isinasaalang-alang ng LIFO Cache ang dalas o oras ng huling pag-access sa datos. Kung ang aplikasyon ay unang humihiling ng datos A, B, C, at pagkatapos ay muli A — sa pag-apaw, ang C (huling idinagdag) ay tatanggalin, kahit na ang A ay hindi na aktuwal. Para sa mga scenario ng pangkalahatang caching ito ay gumagawa sa LIFO na pinakamasamang pagpipilian, dahil ang sariwang datos ay madalas na pinakamahalaga.

Sukat ng Stack at Pamamahala ng Memorya

Para sa LIFO Cache na nakabatay sa array, ang laki ay itinakda sa paggawa at hindi nagbabago nang dinamiko. Kung ang stack ay puno at may push — ang tuktok na elemento ay na-o-overwrite. Para sa implementasyon sa linked list, ang memorya ay inilalaan para sa bawat elemento kung kinakailangan, ngunit pagkatapos maabot ang limitasyon, ang lumang node ay dinidiskonekta at maaaring kolektahin ng garbage collector. Sa mga mobile application inirerekomenda ang paggamit ng array para sa LIFO Cache, dahil hindi ito lumilikha ng karagdagang karga sa GC.

LIFO vs LRU at FIFO: Paghahambing ng mga Estratehiya

Ang pagpili ng estratehiya ng pagtataboy ay direktang nakakaapekto sa kahusayan ng caching. Ang LIFO, LRU at FIFO ay kumakatawan sa iba't ibang mga paglapit sa isang tanong: aling elemento ang tatanggalin kapag umapaw? Bawat paglapit ay optimal para sa sarili nitong klase ng mga gawain.

LRU ay karaniwang nagbibigay ng pinakamahusay na hit-ratio, ngunit nangangailangan ng mas maraming memorya at mas komplikadong ipatupad. FIFO — kompromiso sa pagitan ng performans at hit-ratio, kapaki-pakinabang para sa streaming data. LIFO — pinakasimple, ngunit may mababang hit-ratio: dapat lamang itong gamitin kapag ang semantika na «huling pumasok – unang lumabas» ay tumutugma sa lohika ng negosyo (navigasyon, pag-undo ng operasyon).

Saan Ginagamit ang LIFO Cache

Sa kabila ng limitadong angkop para sa pangkalahatang caching, ang LIFO Cache ay ginagamit sa tiyak na mga scenario kung saan ang pagkakasunud-sunod ng pagproseso ng datos ay baliktad sa pagkakasunud-sunod ng pagdating. Tingnan natin ang mga pangunahing kaso.

Navigation Stack

Sa mga mobile application, ginagamit ang navigation stack: kapag nagbubukas ng bagong screen, ito ay inilalagay sa tuktok ng stack, kapag pinindot ang «Bumalik» — tinatanggal. Kung ang lalim ng stack ay limitado (halimbawa, maximum na 10 screen), awtomatikong tatanggalin ng LIFO Cache ang pinakabagong screen kapag lumampas sa limitasyon. Ito ay nagpapahintulot na kontrolin ang pagkonsumo ng memorya ng navigation stack nang hindi nawawala ang mga naunang binuksang screen.

Undo/Redo Stack

Ang mekanismo ng pag-undo ng aksyon (Undo) — klasikong halimbawa ng LIFO. Bawat aksyon ng gumagamit ay naka-save sa stack. Kapag tinawag ang Undo, ang huling aksyon ay binabawi at inilipat sa Redo stack. Ang paglilimita sa laki ng stack sa pamamagitan ng LIFO Cache ay ginagarantiya na kapag lumampas sa limitasyon, ang pinakamatatandang aksyon (sa ilalim ng stack) ay mananatili, at ang mga pinakabago ay itatapon — na lohikal, dahil ang gumagamit ay karaniwang bumabawi sa mga kamakailang aksyon, at ang mga luma ay hindi na aktuwal.

Buffering ng Pansamantalang Kalkulasyon

Sa rekursibong kalkulasyon na may pagbabalik (backtracking), ang mga resulta ng mga intermediate na hakbang ay naka-save sa LIFO na pagkakasunud-sunod. Kapag ang buffer ay umapaw, ang huling resulta ay itinatapon — ito ay katanggap-tanggap, dahil ang algorithm ay maaaring kalkulahin itong muli kung kinakailangan. Ang paglapit na ito ay ginagamit sa mga parser, compiler at algorithm ng paglalakbay ng graph na may limitasyon ng lalim.

Mga Halimbawa ng Kodigo ng LIFO Cache

Tingnan natin ang implementasyon ng LIFO Cache sa Kotlin gamit ang array na may nakapirming laki. Ang array ay nagbibigay ng pinakamahusay na performans at minimal na pagkonsumo ng memorya para sa mga mobile device.

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--  // itapon ang pinakaluma kapag puno
        }
        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]
    }
}

Ang indeks na top ay tumuturo sa tuktok ng stack. Ang push ay nagpapataas ng top at nagsusulat ng halaga; kung ang array ay puno (top == maxSize - 1), bago ang pagsusulat ang top ay binabawasan — ang tuktok ng stack ay na-o-overwrite, na nagpapatupad ng pagtataboy ng LIFO. Ang metodong pop ay nagbabalik ng elemento at nagbabawas ng top, habang ang peek ay simpleng nagbabasa ng tuktok na elemento nang hindi binabago ang stack.

Halimbawa: Navigation Stack na may LIFO Cache

Tingnan natin ang paggamit ng LIFO Cache para sa paglilimita ng lalim ng navigasyon sa Jetpack Compose. Kapag nagbubukas ng bagong screen, ito ay idinadagdag sa stack, at kapag lumampas sa limitasyon, ang pinakabagong screen ay itinataboy.

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

Sa halimbawang ito, ang NavigationStack ay gumagamit ng LIFO Cache para sa pag-imbak ng kasaysayan ng screen. Kapag tinawag ang navigateTo, ang screen ay idinadagdag sa stack, kapag goBack — ang huli ay tinatanggal. Kung ang gumagamit ay nagbukas ng 11 screen na may limitasyon na 10, ang pinakabago (ika-11) ay magtataboy sa nauna (ika-10) — ang unang screen ay mananatili sa stack, na tumutugma sa inaasahan ng gumagamit kapag bumalik. Ang estratehiyang ito ay mas epektibo kaysa LRU para sa navigasyon: ang pagtatanggal ng matagal nang binuksang screen («home», «profile») ay magdudulot ng hindi inaasahang pag-uugali.