Stack — LIFO ဒေတာဖွဲ့စည်းပုံ

ဒီခန်းပြီးရင် ဘာတတ်သွားမလဲ

Stack — LIFO ဒေတာဖွဲ့စည်းပုံ concept ကို နားလည်ရှင်းပြနိုင်ရန်
နမူနာ Python code ကို ကိုယ်တိုင် run ပြီး output စစ်နိုင်ရန်
Tutorial Platform project နှင့် production scenario တွင် မှန်ကန်စွာအသုံးချနိုင်ရန်

နားလည်ထားရမယ့် အချက်

Stack ဟာ data structure တွေထဲမှာ အရိုးရှင်းဆုံးထဲက တစ်ခုဖြစ်ပေမယ့် အင်အားအထူးကြီးတယ် — element တွေကို ထည့်တဲ့ (push) အစီအစဉ်ရဲ့ ဆန့်ကျင်ဘက်နဲ့ ပြန်ထုတ်ရ (pop) တယ်၊ ဆိုလိုတာက Last In, First Out (LIFO)။ ဒါကို ခန့်ညစားစား ခေါင်းထဲမှာ 'ပန်းကန်ပုံစုပုံစီ' လို့ မြင်နိုင်တယ် — အပေါ်ဆုံးက ပန်းကန်ကိုပဲ ဦးဆုံးထုတ်လို့ရမယ်၊ အောက်ကတစ်ချပ်ကို ရှေးမနေရဘူး။ ဒီ constraint ကနေ push/pop နှစ်ခုစလုံး O(1) ဖြစ်လာတယ် — array ရဲ့ အဆုံးမှာပဲ အမြဲ လုပ်ဆောင်လို့ shift လုပ်စရာမလိုဘူး။ Stack ရဲ့ အရေးကြီးဆုံး use case တွေက 'ပြောင်းပြန်' အစီအစဉ်လိုအပ်တဲ့ ပြဿနာတွေမှာ ပေါ်လာတယ် — undo history (နောက်ဆုံးလုပ်ခဲ့တဲ့ action ကိုပဲ ပြန်ပယ်ရမယ်)၊ function call stack (function တစ်ခုက ခေါ်တဲ့ function ပြီးမှ မိမိဆက်လုပ်ရမယ်)၊ ပြီးတော့ bracket/parenthesis matching (ပိတ်ကွင်းတစ်ခုက အနီးဆုံး မပိတ်သေးတဲ့ ဖွင့်ကွင်းနဲ့ တွဲရမယ်) — အဲဒါကနေ ဒီ lesson ရဲ့ code example ကို တိုက်ရိုက် ရရှိလာတယ်။

လက်တွေ့ scenario နဲ့ ချိတ်ကြည့်မယ်

Tutorial Platform ရဲ့ content editor မှာ lesson author တစ်ယောက် code snippet ရေးတဲ့အခါ bracket/parenthesis တွေ correctly ပိတ်ထား/မထား စစ်ဖို့ stack သုံးနိုင်တယ်၊ publish မလုပ်ခင် syntax error ကို auto-detect လုပ်ပေးတာဖြစ်တယ်။ Undo/redo feature ကိုလည်း action history ကို stack အနေနဲ့ သိမ်းထားပြီး implement လုပ်နိုင်တယ်။

Stack က LIFO — နောက်ဆုံးထည့်တဲ့ element ကိုပဲ အရင်ဆုံးထုတ်ရတယ်
Push/pop နှစ်ခုစလုံး O(1) — အဆုံးတစ်ဖက်ကိုပဲ တိုက်ရိုက် ထိတွေ့ရလို့ shift မလိုဘူး
Undo history, function call stack, bracket matching က stack ရဲ့ classic use case တွေ

အတူတူ စမ်းရေးကြည့်မယ်

python

def is_balanced(expression):
    stack = []
    pairs = {")": "(", "]": "[", "}": "{"}
    for char in expression:
        if char in "([{":
            stack.append(char)  # push - O(1)
        elif char in ")]}":
            if not stack or stack.pop() != pairs[char]:  # pop - O(1)
                return False
    return not stack  # everything must have been matched and closed

tests = ["(a[b]{c})", "(a[b)c]", "((("]
for t in tests:
    print(t, "->", is_balanced(t))

You should see

Test string သုံးခုစီအတွက် `True, False, False` ဆိုပြီး balanced/unbalanced status ကို print ထုတ်ပေးတယ်။

၅ မိနစ် စမ်းကြည့်

`is_balanced` function ကို ပြင်ပြီး bracket type မမှားတဲ့အပြင် ဘယ် position မှာ ပထမဆုံး error ဖြစ်တာလဲဆိုတာကိုပါ ပြန်ပေးအောင် ရေးပါ။

သတိလေးတစ်ချက်

Loop ပြီးတဲ့နောက် `stack` empty ဖြစ်မဖြစ် စစ်တာမေ့တတ်တယ် — `(a` လို unclosed bracket ကို false positive အနေနဲ့ balanced လို့ ထင်သွားနိုင်တယ်

Pop မလုပ်ခင် stack empty ဖြစ်မဖြစ် မစစ်ဘဲ `stack.pop()` ခေါ်ရင် `)a)` လို string အတွက် IndexError ပစ်တတ်တယ်

Wikipedia — Stack (abstract data type) — Data Structures & Algorithms

ဒီနေရာမှာ လူအများမှားတတ်တယ်

Loop ပြီးတဲ့နောက် `stack` empty ဖြစ်မဖြစ် စစ်တာမေ့တတ်တယ် — `(a` လို unclosed bracket ကို false positive အနေနဲ့ balanced လို့ ထင်သွားနိုင်တယ်
Pop မလုပ်ခင် stack empty ဖြစ်မဖြစ် မစစ်ဘဲ `stack.pop()` ခေါ်ရင် `)a)` လို string အတွက် IndexError ပစ်တတ်တယ်
နမူနာ code ကို production system ပေါ် တိုက်ရိုက်မစမ်းဘဲ local/test environment တွင် အရင်အတည်ပြုပါ။

လေ့ကျင့်ခန်း

You'll know it worked when: Test string သုံးခုစီအတွက် `True, False, False` ဆိုပြီး balanced/unbalanced status ကို print ထုတ်ပေးတယ်။