LIFO Cache: الجوهر، خوارزمية المكدس وكيف يعمل

ما هو LIFO Cache؟

LIFO Cache (Last In First Out Cache) هو ذاكرة تخزين مؤقت ذات حجم ثابت مبنية على مكدس. عند إضافة عنصر جديد إلى ذاكرة تخزين مؤقت ممتلئة، تتم إزالة العنصر الأحدث (القمة) ويحل العنصر الجديد محله. يعني الاسم “Last In First Out” أن العنصر الذي دخل ذاكرة التخزين المؤقت أخيراً سيتم استبعاده أولاً.

تختلف هذه السياسة جذرياً عن LRU و FIFO. بينما تحاول LRU الاحتفاظ بالبيانات الأكثر صلة (حسب وقت آخر وصول) وتحافظ FIFO على “عمر” البيانات، تضحي LIFO عمداً بالبيانات الجديدة. قد يبدو هذا غير بديهي للتخزين المؤقت، ولكن لبعض السيناريوهات تكون LIFO الحل الأمثل.

يستخدم التنفيذ الكلاسيكي لـ LIFO Cache مكدساً يعتمد على مصفوفة أو قائمة مرتبطة. توفر المصفوفة تخزيناً مضغوطاً ومحلية ذاكرة تخزين مؤقت لكنها تتطلب تخصيص ذاكرة مسبقاً لـ maxSize. القائمة المرتبطة أكثر مرونة، لكن كل عنصر يتطلب ذاكرة إضافية للمؤشرات (8–16 بايت لكل عنصر).

العمليات الأساسية لـ 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 عادة ما توفر أعلى نسبة إصابات لكنها تتطلب ذاكرة أكثر وأكثر تعقيداً في التنفيذ. FIFO هي حل وسط بين الأداء ونسبة الإصابات، مفيدة للبيانات المتدفقة. LIFO هي الأبسط لكن مع نسبة إصابات منخفضة: يجب استخدامها فقط عندما تتوافق دلالات “آخر دخول أول خروج” مع منطق الأعمال (التنقل، عمليات التراجع).

أين يُستخدم LIFO Cache

على الرغم من ملاءمته المحدودة للتخزين المؤقت العام، يجد LIFO Cache استخداماً في سيناريوهات محددة حيث يكون ترتيب معالجة البيانات معكوساً لترتيب الوصول. دعنا ننظر في الحالات الرئيسية.

مكدسات التنقل

في التطبيقات المحمولة، يُستخدم مكدس التنقل: عند فتح شاشة جديدة، توضع على قمة المكدس؛ عند الضغط على زر “العودة”، تُزال. إذا كان عمق المكدس محدوداً (على سبيل المثال، حد أقصى 10 شاشات)، فسيقوم LIFO Cache تلقائياً باستبعاد أحدث شاشة عند تجاوز الحد. يتيح لك ذلك التحكم في استهلاك الذاكرة لمكدس التنقل دون فقدان الشاشات المفتوحة سابقاً.

مكدسات التراجع/الإعادة

آلية التراجع (Undo) هي مثال كلاسيكي على LIFO. يتم حفظ كل إجراء للمستخدم في مكدس. عند استدعاء Undo، يتم التراجع عن آخر إجراء ونقله إلى مكدس الإعادة. يضمن تحديد حجم المكدسات عبر 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--  // 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]
    }
}

يشير الفهرس 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، تُزال الأخيرة. إذا فتح المستخدم 11 شاشة بحد أقصى 10، فإن أحدثها (الحادية عشرة) ستستبعد السابقة (العاشرة) — تبقى الشاشة الأولى في المكدس، وهو ما يتوافق مع توقعات المستخدم عند العودة للخلف. هذه الاستراتيجية أكثر كفاءة من LRU للتنقل: إزالة الشاشات المفتوحة منذ فترة طويلة (“الصفحة الرئيسية”، “الملف الشخصي”) قد تؤدي إلى سلوك غير متوقع.