LIFO Cache: ماهیت، الگوریتم پشته و طرز کار

ذخیره‌ساز LIFO چیست؟

LIFO Cache (Last In First Out Cache) — ذخیره‌سازی با اندازه محدود است که بر پایه پشته پیاده‌سازی شده است. هنگام اضافه کردن عنصر جدید به ذخیره‌ساز پر، جدیدترین (بالایی) عنصر حذف می‌شود و عنصر جدید جای آن را می‌گیرد. نام «Last In First Out» به این معنی است که عنصری که آخر وارد ذخیره‌ساز شده، اول حذف خواهد شد.

چنین سیاستی از LRU و FIFO تفاوت اساسی دارد. در حالی که LRU سعی می‌کند مناسب‌ترین داده‌ها را (بر اساس زمان آخرین دسترسی) نگه دارد و FIFO «سن» داده‌ها را حفظ می‌کند، LIFO آگاهانه داده‌های تازه را قربانی می‌کند. این ممکن است برای ذخیره‌سازی نامنطقی به نظر برسد، اما برای برخی سناریوهای خاص، LIFO راهحل بهینه است.

پیاده‌سازی کلاسیک LIFO Cache از پشته بر پایه ماتریس یا لیست پیوندی استفاده می‌کند. ماتریس ذخیره‌سازی فشرده و محلی بودن حافظه را فراهم می‌کند، اما برای maxSize تخصیص از پیش حافظه نیاز دارد. لیست پیوندی انعطاف‌پذیرتر است، اما هر عنصر به حافظه اضافی برای پوینترها (۸–۱۶ بایت برای هر عنصر) نیاز دارد.

عملیات اصلی LIFO Cache

عملیات push(value) عنصری را به بالای پشته اضافه می‌کند. اگر اندازه به maxSize رسیده باشد، قبل از درج، بالا حذف می‌شود. عملیات pop() عنصر بالایی را حذف و بازمی‌گرداند — برای سناریوهای «لغو آخرین عمل» مفید است. عملیات peek() عنصر بالایی را بدون حذف بازمی‌گرداند — برای مشاهده آخرین وضعیت ذخیره‌شده بدون تغییر پشته.

LIFO Cache چگونه کار می‌کند

اصل کار LIFO Cache بسیار ساده است: همه عملیات با یک انتهای ساختار — بالای پشته انجام می‌شوند. هنگام اضافه کردن عنصر جدید، آن روی بالا قرار می‌گیرد. اگر پشته پر باشد، عنصر بالایی خارج (حذف) می‌شود و عنصر جدید جای آن را می‌گیرد. خارج‌سازی همیشه تنها یک عنصر را تحت تأثیر قرار می‌دهد — بالا، بنابراین الگوریتم نیازی به پیمایش یا جستجو ندارد.

این ویژگی LIFO Cache را سریع‌ترین در میان همه سیاست‌های خارج‌سازی می‌کند: همه عملیات بدون هیچ ساختار داده اضافه‌ای در O(1) انجام می‌شوند. جدول درهم برای جستجو نیاز نیست، لیست دوطرفه برای جابجایی نیاز نیست — یک پوینتر ساده به بالای پشته کافی است. حافظه به حداقل مصرف می‌شود: تنها برای ذخیره خود عناصر.

اما سادگی یک جنبه منفی نیز دارد: LIFO Cache تکرار یا زمان آخرین دسترسی به داده‌ها را در نظر نمی‌گیرد. اگر برنامه ابتدا داده‌های A، B، C را درخواست کند و سپس دوباره A را — در صورت پر شدن، C (آخرین اضافه‌شده) حذف می‌شود، حتی اگر A دیگر مورد نیاز نباشد. برای سناریوهای ذخیره‌سازی عمومی این LIFO را بدترین انتخاب می‌کند، زیرا داده‌های تازه اغلب از همه باارزش‌تر هستند.

اندازه پشته و مدیریت حافظه

برای LIFO Cache بر پایه ماتریس، اندازه در زمان ایجاد تعیین می‌شود و به صورت پویا تغییر نمی‌کند. اگر پشته پر باشد و push رخ دهد — عنصر بالایی روی‌نویسی می‌شود. در پیاده‌سازی بر پایه لیست پیوندی، حافظه برای هر عنصر در صورت نیاز تخصیص می‌شود، اما پس از رسیدن به حد نصاب، گره قدیمی جدا می‌شود و می‌تواند توسط زباله‌گیر جمع‌آوری شود. در برنامه‌های موبایل توصیه می‌شود از ماتریس برای LIFO Cache استفاده کنید، زیرا بار اضافه‌ای بر GC ایجاد نمی‌کند.

LIFO در مقابل LRU و FIFO: مقایسه راهبردها

انتخاب راهبرد خارج‌سازی مستقیماً بر کارایی ذخیره‌سازی تأثیر می‌گذارد. LIFO، LRU و FIFO رویکردهای مختلفی به یک سوال هستند: کدام عنصر را در صورت پر شدن حذف کنیم؟ هر رویکرد برای طبقه خود از وظایف بهینه است.

LRU معمولاً بهترین hit-ratio را می‌دهد، اما به حافظه بیشتر و پیاده‌سازی پیچیده‌تری نیاز دارد. FIFO — توافقی بین عملکرد و hit-ratio، مفید برای داده‌های جریانی. LIFO — ساده‌ترین، اما با hit-ratio پایین: تنها زمانی باید استفاده شود که سمانتیک «آخرین وارد — اولین خارج» با منطق کسب و کار مطابقت داشته باشد (نمایش، لغو عملیات).

LIFO Cache کجا استفاده می‌شود

علیرغم مناسبت محدود برای ذخیره‌سازی عمومی، LIFO Cache در سناریوهای خاصی که ترتیب پردازش معکوس ترتیب ورود است، کاربرد دارد. موارد اصلی را بررسی می‌کنیم.

پشته‌های نمایش

در برنامه‌های موبایل از پشته نمایش استفاده می‌شود: هنگام باز شدن صفحه جدید، آن روی بالای پشته قرار می‌گیرد، با فشردن دکمه «بازگشت» حذف می‌شود. اگر عمق پشته محدود شود (مثلاً حداکثر ۱۰ صفحه)، LIFO Cache به طور خودکار آخرین صفحه را پس از تجاوز از حد حذف می‌کند. این امکان می‌دهد مصرف حافظه توسط پشته نمایش را بدون از دست دادن صفحات قبلی کنترل کرد.

پشته‌های Undo/Redo

مکانیزم لغو عملیات (Undo) — یک نمونه کلاسیک LIFO. هر عمل کاربر در پشته ذخیره می‌شود. هنگام فراخوانی Undo، آخرین عمل لغو می‌شود و به پشته Redo منتقل می‌گردد. محدود کردن اندازه پشته‌ها از طریق LIFO Cache تضمین می‌کند که پس از تجاوز از حد، کهنه‌ترین عملیات (در انتهای پشته) باقی بمانند و جدیدترین حذف شوند — که منطقی است، زیرا کاربر معمولاً عملیات اخیر را لغو می‌کند و عملیات قدیمی دیگر مورد نیاز نیستند.

بافری محاسبات موقت

در محاسبات بازگشتی با بازگشت (backtracking)، نتایج مراحل وسطی به ترتیب LIFO ذخیره می‌شوند. وقتی بافر پر می‌شود، آخرین نتیجه حذف می‌شود — این قابل قبول است، زیرا الگوریتم می‌تواند در صورت نیاز آن را مجدداً محاسبه کند. این رویکرد در پارسرها، کامپایلرها و الگوریتم‌های پیمایش گراف با محدودیت عمق استفاده می‌شود.

نمونه کد LIFO Cache

پیاده‌سازی LIFO Cache را در Kotlin با استفاده از ماتریس با اندازه ثابت بررسی می‌کنیم. ماتریس بهترین عملکرد و حداقل مصرف حافظه را برای دستگاه‌های موبایل فراهم می‌کند.

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--  // در صورت پر شدن، قدیمی‌ترین را دور بینداز
        }
        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]
    }
}

اندیس top به بالای پشته اشاره می‌کند. push top را افزایش می‌دهد و مقدار را می‌نویسد; اگر ماتریس پر باشد (top == maxSize - 1)، قبل از نوشتن top کاهش می‌یابد — بالای پشته روی‌نویسی می‌شود که همان خارج‌سازی LIFO است. روش pop عنصر را بازمی‌گرداند و top را کاهش می‌دهد، و peek صرفاً عنصر بالایی را بدون تغییر پشته می‌خواند.

نمونه: پشته نمایش با LIFO Cache

استفاده از LIFO Cache را برای محدود کردن عمق نمایش در Jetpack Compose بررسی می‌کنیم. هنگام باز شدن صفحه جدید، آن به پشته اضافه می‌شود، و پس از تجاوز از حد، آخرین صفحه حذف می‌شود.

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

در این مثال، NavigationStack از LIFO Cache برای ذخیره تاریخچه صفحات استفاده می‌کند. با فراخوانی navigateTo صفحه به پشته اضافه می‌شود، با goBack آخرین حذف می‌شود. اگر کاربر ۱۱ صفحه را با لیمیت ۱۰ باز کند، آخرینی (۱۱مین) جای قبلی (۱۰مین) را می‌گیرد — اولین صفحه در پشته باقی می‌ماند که با انتظارات کاربر برای بازگشت مطابقت دارد. این راهبرد برای نمایش از LRU مؤثرتر است: حذف صفحات قدیمی («صفحه اصلی»، «پروفایل») منجر به رفتار غیرمنتظره می‌شد.