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 कॉल किया जाता है, तो अंतिम क्रिया पूर्ववत की जाती है और Redo स्टैक में ले जाई जाती है। LIFO Cache के माध्यम से स्टैक आकार को सीमित करना सुनिश्चित करता है कि जब सीमा पार हो जाती है, तो सबसे पुरानी क्रियाएँ (स्टैक के निचले भाग में) रहती हैं जबकि सबसे हालिया छोड़ दी जाती हैं — जो तार्किक है क्योंकि उपयोगकर्ता आमतौर पर हाल की क्रियाओं को पूर्ववत करता है जबकि पुरानी अब प्रासंगिक नहीं हैं।

अस्थायी गणना बफ़रिंग

बैकट्रैकिंग के साथ पुनरावर्ती गणनाओं में, मध्यवर्ती चरणों के परिणाम LIFO क्रम में सहेजे जाते हैं। जब बफ़र ओवरफ़्लो हो जाता है, तो अंतिम परिणाम छोड़ दिया जाता है — यह स्वीकार्य है क्योंकि एल्गोरिदम आवश्यकता पड़ने पर इसे पुनः गणना कर सकता है। इस दृष्टिकोण का उपयोग पार्सर, कंपाइलर और गहराई सीमा वाले ग्राफ़ ट्रैवर्सल एल्गोरिदम में किया जाता है।

LIFO Cache कोड उदाहरण

आइए एक निश्चित आकार की सरणी का उपयोग करते हुए Kotlin में LIFO Cache के कार्यान्वयन को देखें। सरणी मोबाइल उपकरणों के लिए सबसे अच्छा प्रदर्शन और न्यूनतम मेमोरी खपत प्रदान करती है।

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 के साथ नेविगेशन स्टैक

Jetpack Compose में नेविगेशन गहराई को सीमित करने के लिए LIFO Cache के उपयोग पर विचार करें। जब एक नई स्क्रीन खोली जाती है, तो उसे स्टैक में जोड़ा जाता है, और जब सीमा पार होती है, तो सबसे हालिया स्क्रीन हटा दी जाती है।

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 कॉल किया जाता है, तो अंतिम स्क्रीन हटा दी जाती है। यदि उपयोगकर्ता ने 10 की सीमा के साथ 11 स्क्रीन खोली हैं, तो सबसे हालिया (11वीं) पिछली (10वीं) को हटा देगी — पहली स्क्रीन स्टैक में रहती है, जो पीछे नेविगेट करते समय उपयोगकर्ता की अपेक्षाओं से मेल खाती है। यह रणनीति नेविगेशन के लिए LRU से अधिक कुशल है: लंबे समय से खुली स्क्रीन (“होम”, “प्रोफ़ाइल”) को हटाने से अप्रत्याशित व्यवहार होगा।