Last In Fast Out (LIFO) Algorithm

Memory မှာ Stack နဲ့ Heap ဆိုတဲ့ Memory ဆိုပြီးရှိပါတယ်။ Memory ကို Data တွေ သိုလှောင်ဖို့အသုံးပြုပါတယ်။ Data တွေကိုသိုလှောင်တဲ့အခါ အသွင်း၊အထုတ်ပြုလုပ်ရတဲ့လုပ်ငန်းစဉ်တွေလည်းရှိပါတယ်။ ဒီလိုလုပ်ငန်းစဉ်တွေကိုလည်း Memory ကလုပ်ဆောင်လို့ရတယ်။

Stack Memory

Stack ဆိုတာကလည်း Abstract Memory တစ်ခုပဲဖြစ်ပါတယ်။သူသည်လည်း Data တွေကို ထည့်သွင်းခြင်း၊ ထုတ်ယူခြင်း၊ သိုလှောင်ခြင်းစတဲ့လုပ်ငန်းစဉ်တွေကိုလုပ်ဆောင်လို့ရတယ်။

Stack ကို Variable များကိုသိုလှောင်ခြင်း ( သိုလှောင်မယ့် Variable ရဲ့ Size ကိုတစ်ခါတည်းသတ်မှတ်ပေးဖို့လိုပါတယ်။ Example in Rust :

let x : i32 = 123;

Rust မှာဆိုရင် Variable ရဲ့ Data Size ကိုသတ်မှတ်ပေးဖို့လိုအပ်ပါတယ်။ i32 ဆိုတာ Variable ရဲ့ Size လေးကိုသတ်မှတ်ပေးလိုက်တာပါ။ Memory ပေါ်မှာဘယ်နှနေရာစာယူမယ်ဆိုပြီးတော့သတ်မှတ်ပေးလိုက်တာပါ။ i32 ကတော့ 32bit (8bytes) စာနေရာယူမယ်လို့သတ်မှတ်လိုက်တာဖြစ်ပါတယ်။ သတ်မှတ်ထားတဲ့ Data Size ထက်ကျော်သွားရင် Stack Overflow Error ဖြစ်ပါလိမ့်မယ်။ )၊ Function များကိုသိုလှောင်ခြင်းစတဲ့လုပ်ငန်းစဉ်တွေအတွက်လုပ်ဆောင်ပါတယ်။ ခုလို Stack Thread ပေါ်မှာသိုလှောင်ခင်ူကို Stack Based Memorey Allocation လို့လည်းခေါ်ပါတယ်။

Stack ကိုသုံးတဲ့ Heap ထက် ပိုပြီးတော့မြန်ပါတယ်။ Performance ပိုကောင်းတယ်။

Stack က Last In Fast Out (LIFO) ပုံစံမျိုးလုပ်ဆောင်တယ်။ နောက်ဆုံးဝင်တဲ့ကောင်ကအရင်ပြန်ထွက်ရမယ်။ Stack ရဲ့လုပ်‌ဆောင်ပုံက ပန်းကန်ပြားလေးတွေကိုအထပ်လိုက်စီထားတာနဲ့တူပါတယ်။ ပန်းကန်တစ်ခုကိုသုံးချင်ရင် နောက်ဆုံးတင်ထားတဲ့ ပန်းကန်ကိုပဲယူလိုရမှာဖြစ်ပါတယ်။ပထမဆုံးတင်ထားတဲ့ပန်းကန်ကိုတော့ နောက်ဆုံးမှယူလို့ရမှာဖြစ်ပါတယ်။

Stack ဟာ Memory Size သေးပါတယ်။ ဒါ့ကြောင့် Size သိပြီးသား Variable တွေကိုသိုလှောင်တာဖြစ်ပါတယ်။ Size သိပြီးသားဆိုတော့ ဘယ်နှနေရာစာယူရမယ်ဆိုတာအတိအကျသိလို့ဖြစ်တယ်။ Size ကျော်သွားရင် Crash သွားတာဖြသ်လို့ Stack Overflow Error ကိုပြမှာဖြစ်ပါတယ်။

LIFI

Stack မှာ Push နဲ့ Pop ဆိုတဲ့လုပ်ငန်း‌စဉ်တွေကိုအဓိကလုပ်ဆောင်ပါတယ်။

Push

Stack ပေါ်ကို Data တွေထည့်တဲ့လုပ်ငန်းစဉ်ဖြစ်ပါတယ်။ Data ထည့်တဲ့အခါ Stack ရဲ့ ထိပ်ဆုံး(Top/Front) မှာသွားထည့်ပါတယ်။ ပန်းကန်ပြားလေးတွေထပ်သလိုပါပဲ။

Pop

Stack ရဲ့ထိပ်ဆုံးက Data ကို ထုတ်(Remove/Dequeue)တဲ့လုပ်ငန်းစဉ်ဖြစ်ပါတယ်။ ထပ်ထားတဲ့ပန်းကန်ပြားအထပ်‌က‌နေပန်းကန်ပြားတစ်ချပ်ကိုယူလိုက်သလိုပါပဲ။

Push နဲ့ Pop အပြင် Peek ဆိုတဲ့ လုပ်ငန်းစဉ်လည်းရှိပါတယ်။ Peek က Stack ထိပ်ဆုံးမှာရှိတဲ့ Data ကိုယူချင်တဲ့အခါသုံးပါတယ်။

Push Example

1

Push(1)

Data တစ်ခုကို Stack ပေါ်ကိုတင်လိုက်တာပါ။ နောက်တစ်ခုထပ်တင်ကြည့်ပါမယ်။

2
1

Push(2)

နောက်တင်လိုက်တဲ့ 2 ဆိုတဲ့ Data ဟာ 1 ရဲ့အပေါ်ကိုရောက်သွားပါတယ်။ ဒါဟာ Push ရဲ့လုပ်ငန်းစဉ်ပါပဲ။ပထမဆုံးတင်လိုက်တဲ့ကောင်ဟာအောက်ဆုံးကိုရောက်သွားတယ်ဆိုတာပဲဖြစ်ပါတယ်။

Pop Example

2
1

Stack ပေါ်ရောက်နေတဲ့ Data တွေကို Pop လုပ်ကြည့်ပါမယ်။

1

Pop()

Pop လုပ်လိုက်တဲ့အခါ ထိပ်ဆုံးမှာရှိတဲ့ 2 ကို Top Pointer ကလှမ်းထောက်ပြီးတော့ Remove လုပ်လိုက်တာပါ။ဒီဖြစ်စဉ်က Pop လုပ်တဲ့လုပ်ငန်းစဉ်ပါပဲ။

ခု အထက်ကလုပ်ငန်းစဉ်တွေကို JavaScript နဲ့ Implement လုပ်ကြည့်ပါမယ်။ Implement လုပ်တဲ့အခါ လိုအပ်တဲ့လုပ်ငန်းစဉ်တွေကိုအရင်သတ်မှတ်ပါမယ်။ အထက်မှာကလျှင်လျှင်မြန်မြန်သဘောပေါက်စေဖို့အတွက်လုပ်ငန်းစဉ်တစ်ချို့ကိုချန်ပြီးပြောသွားတာပါ။

Stack ပေါ်ကို Data တင်တဲ့အခါ -

1. Stack ပြည့်မပြည့်စစ်တယ်။
2. ပြည့်နေရင် Error Message ပြမယ်။
3. Stack ပေါ်မှာထည့်ဖို့နေရာရှိသေးရင် Top Pointer က တစ်နေရာစာယူပေးထားတယ်
4. နောက် Data ထည့်လိုက်တဲ့အခါ ယူထားတဲ့ နေရာလေးမှာထည့်ပေးလိုက်ယုံပဲပေါ့ဗျာ။
5. Push လုပ်တာအောင်မြင်ကြောင်း Message ပြန်ပြယုံပါပဲ။

Stack ပေါ်ကနေ Data ပြန်ထုတ်တဲ့အခါ -

1. Stack က Empty ဖြစ်နေသလားစစ်ပါတယ်။
2. Empty ဖြစ်နေရင် Empty ဖြစ်တဲ့အကြောင်း Error Message ပြန်ပြပါမယ်။
3. Top Pointer လေးကို‌အောက်တစ်ဆင့်ပြန်းတယ်။
4. ပြီးတဲ့နောက်မှာ ထိပ်ဆုံးက Data ကို Remove လုပ်ပစ်လိုက်မယ်။ ( မူလက 5 ဆိုတဲ့နေရာကို Top Pointer လေးရောက်နေတယ်ဆိုပါစို့။ 4 နေရာမှာကြတော့တကယ့် Data ရှိနေမှာ။ 5 က တစ်နေရာစာကြိုယူထားတဲ့နေရာလေးပေါ့။ Pointer ကိုအောက်တစ်ထစ်ဆင်းလိုက်တဲ့အတွက် 4 ဖြစ်သွားပါတယ်။ အဲ့နောက်မှာမှ 4 ကို Remove လုပ်လိုက်ရပါတယ်။)
5. Push လုပ်တာအောင်မြင်ကြောင်း Message ပြန်ပေးရပါမယ်။

Stack ထိပ်ဆုံးက Data ကို Access လုပ်တဲ့အခါ -

Top Pointer ကနေ 1 နှုတ်ပေးလိုက်ယုံပါပဲ။

အခု လက်တွေ့လေ့လာကြည့်ရအောင်။

အရင်ဆုံး Stack Memory တစ်ခုကြေညာပါမယ်။ Stack Memory က Array နဲ့ဆင်တာဖြစ်တဲ့အတွက် Array အဖြစ်ကြေညာလိုက်ပါမယ်။ ပြီးတဲ့နောက်မှာ Top Pointer ကိုလည်းကြေညာပေးဖို့လိုပါမယ်။ သူက Stack ပေါ် Data သွင်းတဲ့အခါထုတ်တဲ့အခါမျိုးမှာ Data အတွက်နေရာကိုယူပေးဖို့အတွက်ဖြစ်ပါတယ်။ ကျွန်တော်တို့သုံးနေတာက JS ဖြစ်နေတဲ့အတွက် Stack ရဲ့ Size ကို သတ်မှတ်ပေးဖို့လိုပါတယ်။

// stack memory
let stack = [];
// top pointer
let top = 0;
// maximum length of stack
let max_length = 5;

အခု ပထမဆုံးစလုပ်ရမှာက Push Process ဖြစ်ပါတယ်။ Data တွေကို လက်ခံမှာဖြစ်တဲ့အတွက် Function တစ်ခုအနေနဲ့ Apply လုပ်လိုက်ပါမယ်။ ပြီးတဲ့နောက်မှာ Stack ရဲ့ Maximum Size ပြည့်မပြည့်စစ်ပါမယ်။ ပြည့်နေတဲ့အခါ Error Message ပြန်ပြမှာဖြစ်ပါတယ်။ မပြည့်သေးဖူးဆိုရင်တော့ Stack ရဲ့ Top Pointer ‌ရောက်နေတဲ့နေရာကို Data ထည့်ပေးလိုက်ပါတယ်။ ပြီးနောက်မှာ တစ်နေရာစာတိုးပေးလိုက်ပါတယ်။ တစ်နေရာစာတိုးပေးလိုက်တာက နောက်ဝင်လာမယ့် Data အတွက်နေရာကြိုဦးထားလိုက်ခြင်းဖြစ်ပါတယ်။ Push လုပ်တဲ့ လုပ်ငန်းစဉ်အောင်မြင်တဲ့အတွင်အောင်မြင်ကြောင်း Message ပြန်ပြီးထုတ်ပေးလိုက်ပါတယ်။

// insert data to the stack
const push = (element) => {
    // check the stack is full or no5
    if (stack.length >= max_length) {
        throw new Error('Stack Overflow Error Occured');
    }
    // insert data to the empty of stack
    stack[top] = element;
    // take new empty space for next data
    top = top + 1;
    console.log('Data Inserted');
};

ခု Data တွေ ပြန်ထုတ်တဲ့ Pop Process ကိုလေ့လာကြည့်ပါမယ်။ Pop လုပ်ငန်းစဉ်မှာ Stack က Empty ဖြစ်နေသလားစစ်ဖို့လိုပါတယ်။ ဒီ့အတွက် Empty ဖြစ်၊ မဖြစ်စစ်တဲ့လုပ်ငန်းစဉ်ကို Pop Process မတိုင်ခင် Implement လုပ်ထားဖို့လိုပါတယ်။ Stack ရဲ့ Length ကိုစစ်လိုက်ယုံပါပဲ။ 0 ဖြစ်နေတဲ့အခြေအနေဆိုရင် Stack Empty ဖြစ်နေတယ်လို့အလွယ်သိနိုင်မှာဖြစ်ပါတယ်။

// check the length of stack
const empty = () =>  !stack.length;

ခု Pop ကိုဆက်ပြီးတော့ Implement လုပ်ပါမယ်။ Pop မှာ Empty ဖြစ်၊ မဖြစ်ကို အရင်စစ်ရမှာဖြစ်ပါတယ်။ Empty ဖြစ်ရင် Empty ဖြစ်ကြောင်း Message ပြယုံပါပဲ။

// remove the data
const pop = () => {
    // check stack is empty or not
    if (empty()) {
        throw new Error('Empty Stack');
    }
 }

Data ကို Stack ပေါ်ကနေထုတ်ပြီးတဲ့အခါ Top Pointer ကိုအောက်တစ်ဆင့်ပြန်ဆင်းရပါမယ်။ အောက်တစ်ဆင့်ပြန်ဆင်းမှသာ Stack အပေါ်ဆုံးက Data ကို Access တဲ့အခါ အလွယ်တကူ Access လုပ်လို့ရမှာဖြစ်ပါတယ်။ ပြီးတဲ့နောက်မှာ Stack ပေါ်က Data ကို Remove လိုက်ပါတယ်။ Stack ပေါ်က Data ကို Remove လုပ်တာအောင်မြင်ကြောင်း Message ပြန်ပေးလိုက်တဲ့အခါ Pop Process ပြီးဆုံးသွားပြီဖြစ်ပါတယ်။

// remove the data
const pop = () => {
    // check stack is empty or not
    if (empty()) {
        throw new Error('Empty Stack');
    }
    top = top - 1;
    stack.pop();
    console.log('Data Removed');
};

Stack ရဲ့ထိပ်ဆုံးက Element ကို လိုချင်တဲ့အခါ Peek Process လေးကိုထည့်ပေးယုံပါပဲ။ Stack ရဲ့ထိပ်ဆုံးက Data က Top Pointer ရဲ့အောက်တစ်ဆင့်မှာဖြစ်တဲ့အတွက် Top Pointer ယူထား‌တဲ့နေရာကနေ တစ်နေရာစာ‌နှုတ်ပေးလိုက်ရုံပါပဲ။

// access the element that is on the top of stack
const peek = () => stack[top - 1];

Stack ထဲက Data တွေအကုန်လုံးကို Print ထုတ်ချင်တဲ့အခါ ‌While Loop သုံးပြီး ထုတ်ပေးရုံပါပဲ။ While Loop ကိုပြောင်းပြန်ပတ်ပေးရပါမယ်။ Stack ရဲ့အပေါ်ဆုံးက Data ကနေ အောက်ဆုံးက Data ကိုအစဉ်လိုက်ပြချင်လို့ဖြစ်ပါတယ်။

// print all data of stack
const print = () => {
    while (top > 0) {
        console.log(peek());
        top--;
    }
};

အလုပ်လုပ်မလုပ်စမ်းကြည့်ဖို့အတွက်အောက်ပါအတိုင်းစမ်းကြည့်ပါမယ်။ ကျွန်တော်တို့က Error တွေ Throw ထားတဲ့အတွက် Try Catch ရဲ့ Error ကို Handle ပေးဖို့တော့လိုပါမယ်။

try {
    // set data
    push(1);
    push(2);
    push(3);
    push(4);
    push(5);
    // print all data to console
    print();
}catch(e) {
    // catch the error
    console.error(`
        ${e.message}
        `);
}

Code အပြည်အစုံကတော့အောက်ပါအတိုင်းဖြစ်ပါတယ်။

Conclusion

Stack ရဲ့အလုပ်လုပ်ပုံကိုသိသွားတဲ့အခါ Low Level Programming Language မှာပါတဲ့ Memory Management ပိုင်းကြရင် အထောက်အကူပြပါလိမ့်မယ်၊ ထို့ပြင် Stack Memory အတွက်အသုံးပြုတဲ့ Push, Pop Process တွေကို အသုံးချတတ်သွားပါလိမ့်မယ်။ Stack Overflow Error ဆိုတာဘာကြောင့်ပေါ်လာတယ်ဆိုတာကိုလည်းသဘောပေါက်မယ်ထင်ပါတယ်။