Stacks (အပေါ်ကနေပဲ ထည့်၊ ထုတ်တဲ့ အထပ်များ)
B2.2.3: Explain the concept of a stack as a “last in, first out” (LIFO) data structure: push, pop, peek and isEmpty, and how stack operations affect performance and memory usage.
မြန်မာလို: Stack (အပေါ်ကနေပဲ ထည့်၊ ထုတ်တဲ့ အထပ်) ကို “last in, first out” (LIFO: နောက်ဆုံးဝင်တာ အရင်ထွက်) data structure (ဒေတာ သိမ်းဆည်းပုံ) တစ်ခုအဖြစ် သူ့သဘောတရားကို ရှင်းပြနိုင်ရပါမယ်။ Push (stack ရဲ့ အပေါ်ဆုံးမှာ ထည့်ခြင်း)၊ pop (stack ရဲ့ အပေါ်ဆုံးကနေ ဖယ်ထုတ်ခြင်း)၊ peek (အပေါ်ဆုံး item ကို မဖယ်ဘဲ ကြည့်ခြင်း) နဲ့ isEmpty (အလွတ် ဖြစ်မဖြစ် စစ်ခြင်း) တို့နဲ့ stack operation (stack ပေါ်မှာ လုပ်တဲ့ လုပ်ဆောင်ချက်) တွေက performance (စွမ်းဆောင်ရည်) နဲ့ memory (မှတ်ဉာဏ်) သုံးစွဲမှုကို ဘယ်လို သက်ရောက်လဲ ဆိုတာ ပါဝင်ပါတယ်။
အဓိက အယူအဆများ
Stack ဆိုတာ ဘာလဲ
Stack ဆိုတာ Last In, First Out (LIFO) စည်းမျဉ်းကို လိုက်နာတဲ့ abstract data structure (operation တွေနဲ့ သတ်မှတ်တဲ့ data structure) တစ်ခုပါ: နောက်ဆုံး ထည့်ခဲ့တဲ့ item (အချက်) ကို အရင်ဆုံး ဖယ်ထုတ်ပါတယ်။ Top (အပေါ်ဆုံး) element (အစုထဲက အချက်) ကိုပဲ ယူသုံးလို့ ရပါတယ်။
စားသောက်ဆောင်မှာ ထပ်ထားတဲ့ ပန်းကန်ပြား အထပ်ကို စဉ်းစားကြည့်ပါ: ပန်းကန်ပြားကို အပေါ်ဆုံးမှာ ထပ်တင်ပြီး အပေါ်ဆုံးကနေပဲ ယူပါတယ်။ အလယ်ကနေ ဆွဲထုတ်လို့ မရပါဘူး။
Stack Operation များ (stack ပေါ်မှာ လုပ်တဲ့ လုပ်ဆောင်ချက်များ)
| Operation | ဘာလုပ်လဲ | Java method |
|---|---|---|
| Push | အပေါ်ဆုံးမှာ item တစ်ခု ထည့်ပါတယ် | stack.push(value) |
| Pop | အပေါ်ဆုံး item ကို ဖယ်ထုတ်ပြီး ပြန်ပေးပါတယ် | stack.pop() |
| Peek | အပေါ်ဆုံး item ကို မဖယ်ဘဲ ကြည့်ပါတယ် | stack.peek() |
| isEmpty | Stack ထဲမှာ element တစ်ခုမှ မရှိဘူးလား စစ်ပါတယ် | stack.isEmpty() |
| Size | Element အရေအတွက်ကို ယူပါတယ် | stack.size() |
Stack အလွတ်ပေါ်မှာ pop နဲ့ peek လုပ်ရင် EmptyStackException (stack အလွတ်ကနေ ယူဖို့ ကြိုးစားလို့ program run နေစဉ် ဖြစ်တဲ့ အမှား) ကို throw (exception ဖြစ်ကြောင်း အချက်ပြ) လုပ်ပါတယ်။ pop() ဒါမှမဟုတ် peek() ကို မခေါ်ခင် isEmpty() နဲ့ အမြဲ အရင် စစ်ပါ။ (Python မှာ list ကို stack အဖြစ် သုံးရင် list အလွတ်ကို pop လုပ်တဲ့အခါ IndexError ကို raise လုပ်ပါတယ်၊ သဘောတရား အတူတူပါပဲ: အရင် စစ်ပါ။)
Java မှာ Stack ကို သုံးခြင်း
import java.util.Stack;
Stack<Integer> stack = new Stack<>();
// Push elements onto the stack
stack.push(10); // stack: [10] top = 10
stack.push(20); // stack: [10, 20] top = 20
stack.push(30); // stack: [10, 20, 30] top = 30
// Peek at the top (does not remove)
System.out.println(stack.peek()); // 30
// Pop the top element (removes and returns)
System.out.println(stack.pop()); // 30 stack: [10, 20]
System.out.println(stack.pop()); // 20 stack: [10]
// Check state
System.out.println(stack.isEmpty()); // false (10 is still there)
System.out.println(stack.size()); // 1
# Python has no built-in Stack class - a plain list is the usual
# implementation choice: append() pushes, pop() removes the top.
stack = []
# Push elements onto the stack
stack.append(10) # stack: [10] top = 10
stack.append(20) # stack: [10, 20] top = 20
stack.append(30) # stack: [10, 20, 30] top = 30
# Peek at the top (does not remove)
print(stack[len(stack) - 1]) # 30 - the last element is the top
# Pop the top element (removes and returns)
print(stack.pop()) # 30 stack: [10, 20]
print(stack.pop()) # 20 stack: [10]
# Check state
print(len(stack) == 0) # False (10 is still there) - Python capitalises booleans
print(len(stack)) # 1
မမေ့ပါနဲ့: Stack<int> မဟုတ်ဘဲ Stack<Integer> လို့ ရေးပါ။ ArrayList လိုပဲ stack တွေကလည်း primitive type (Java ရဲ့ အခြေခံ ဒေတာ အမျိုးအစား) တွေကို မသိမ်းဘဲ object (class တစ်ခုကနေ ဖန်တီးထားတဲ့ instance) တွေကို သိမ်းပါတယ်။
Stack Operation တွေကို ပုံနဲ့ ကြည့်ခြင်း
Push တစ်ခါစီက item အသစ် (အစိမ်းရောင်) တစ်ခုကို stack ရဲ့ အပေါ်ဆုံးမှာ ချထည့်ပါတယ်။ Pop တစ်ခါစီက အပေါ်ဆုံး item ကို ဖယ်ထုတ်ပြီး ပြန်ပေးပါတယ်၊ မျဉ်းပြတ် အကွက်က အဲဒီ item ရှိခဲ့တဲ့ နေရာကို ပြပါတယ်။ top လို့ ရေးထားတဲ့ မြှားက နောက်တစ်ကြိမ် pop ဒါမှမဟုတ် peek လုပ်ရင် ရောက်မယ့် item ကို ညွှန်ပါတယ်။ ပုံထဲက returns ဆိုတာ ပြန်ပေးတယ်လို့ ဆိုလိုပါတယ်။
လက်တွေ့ အသုံးချပုံများ
Undo/Redo (လုပ်ခဲ့တာကို ပြန်ဖျက်ခြင်း / ပြန်လုပ်ခြင်း)
ပြင်ဆင်မှု တစ်ခု လုပ်တိုင်း အဲဒီ လုပ်ဆောင်ချက်ကို undo stack ပေါ်ကို push လုပ်ပါတယ်။ Ctrl+Z ကို နှိပ်ရင် နောက်ဆုံး လုပ်ခဲ့တဲ့ လုပ်ဆောင်ချက်ကို pop လုပ်ပြီး ပြန်ဖျက်ပါတယ်။ ပြန်ဖျက်လိုက်တဲ့ လုပ်ဆောင်ချက်ကို redo stack ပေါ်ကို push လုပ်ပါတယ်။
Browser ရဲ့ Back ခလုတ်
သွားကြည့်တဲ့ စာမျက်နှာ တစ်ခုစီကို history stack (သွားခဲ့တဲ့ စာမျက်နှာတွေကို မှတ်ထားတဲ့ stack) ပေါ်ကို push လုပ်ပါတယ်။ “Back” ကို နှိပ်ရင် လက်ရှိ စာမျက်နှာကို pop လုပ်ပြီး အရင် စာမျက်နှာကို ပြပါတယ်။
Method Call Stack (လက်ရှိ method ခေါ်မှုတွေကို သိမ်းတဲ့ stack)
Method (သီးခြား အလုပ်တစ်ခု လုပ်ပေးတဲ့ code အပိုင်း) တစ်ခုက တခြား method တစ်ခုကို ခေါ်တဲ့အခါ ခေါ်တဲ့ method ရဲ့ အခြေအနေ (state) ကို call stack ပေါ်ကို push လုပ်ပါတယ်။ ခေါ်ခံရတဲ့ method က return (ရလဒ်အဖြစ် ပြန်ပေး) လုပ်တဲ့အခါ သူ့ရဲ့ frame (method ခေါ်မှု တစ်ခုစီရဲ့ ဒေတာကို သိမ်းထားတဲ့ အကွက်) ကို pop လုပ်ပြီး ခေါ်တဲ့ method က ရပ်ထားတဲ့ နေရာကနေ ဆက်လုပ်ပါတယ်။
public static int multiply(int a, int b) {
return a * b;
}
public static int addThenDouble(int a, int b) {
return multiply(a + b, 2);
}
public static void main(String[] args) {
System.out.println(addThenDouble(3, 4));
}
// Call stack when multiply runs: [main, addThenDouble, multiply]
// multiply returns 14, popped: [main, addThenDouble]
// addThenDouble returns 14, popped: [main]
def multiply(a, b):
return a * b
def add_then_double(a, b):
return multiply(a + b, 2)
print(add_then_double(3, 4))
# Call stack when multiply runs: [main program, add_then_double, multiply]
# multiply returns 14, popped: [main program, add_then_double]
# add_then_double returns 14, popped: [main program]
Code အောက်ဆုံးက comment (ရှင်းလင်းချက် စာ) တွေက multiply run နေချိန်မှာ call stack ပေါ်မှာ ခေါ်မှု သုံးခု (main၊ addThenDouble၊ multiply) ရှိနေပြီး method တစ်ခု return လုပ်တိုင်း သူ့ frame ကို pop လုပ်သွားတာကို ပြပါတယ်။
Expression တွေကို တွက်ခြင်း
ဂဏန်းတွက်စက်တွေက ကွင်းပါတဲ့ expression (တန်ဖိုး တစ်ခု တွက်ထုတ်ရတဲ့ သင်္ချာ ပုံသေနည်း) တွေကို တွက်ဖို့ stack တွေကို သုံးပါတယ်။ ကွင်းဖွင့်တွေကို push လုပ်ပြီး ကွင်းပိတ် တစ်ခုကို တွေ့တဲ့အခါ operation တွေကို pop လုပ်ပြီး တွက်ပါတယ်။
စာမေးပွဲ မေးခွန်းမှာ LIFO ကို တွေ့ရင် stack ကို သတိရပါ။
အဆင့်ဆင့် ရှင်းပြထားတဲ့ ဥပမာများ
ဥပမာ 1: String (စာသား) တစ်ခုကို ပြောင်းပြန်လှန်ခြင်း
Stack က အစဉ်ကို သဘာဝအတိုင်း ပြောင်းပြန် ဖြစ်စေပါတယ်: character (စာလုံး ဒါမှမဟုတ် သင်္ကေတ) အားလုံးကို push လုပ်ပြီးမှ pop လုပ်ပါ။
public static String reverse(String text) {
Stack<Character> stack = new Stack<>();
// Push each character
for (int i = 0; i < text.length(); i++) {
stack.push(text.charAt(i));
}
// Pop to build reversed string
String reversed = "";
while (!stack.isEmpty()) {
reversed += stack.pop();
}
return reversed;
}
def reverse(text):
stack = [] # a plain list used as a stack (implementation choice)
# Push each character (Python has no char type - just 1-character strings)
for i in range(len(text)):
stack.append(text[i])
# Pop to build reversed string
# reversed is a built-in name in Python, so we call it reversed_text
reversed_text = ""
while len(stack) > 0:
reversed_text = reversed_text + stack.pop()
return reversed_text
System.out.println(reverse("hello")); // olleh
print(reverse("hello")) # olleh
ဥပမာ 2: ကွင်းတွေ အတွဲညီမညီ စစ်ခြင်း
Expression တစ်ခုထဲက ကွင်းတွေ balanced (အဖွင့်၊ အပိတ် အတွဲညီ) ဖြစ်မဖြစ် စစ်ပါ: ( တိုင်းမှာ သူနဲ့ တွဲမယ့် ) ရှိရပါမယ်။
public static boolean isBalanced(String expression) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < expression.length(); i++) {
char c = expression.charAt(i);
if (c == '(') {
stack.push(c);
} else if (c == ')') {
if (stack.isEmpty()) {
return false; // closing bracket with no opening
}
stack.pop();
}
}
return stack.isEmpty(); // true if all brackets matched
}
def is_balanced(expression):
stack = [] # a plain list used as a stack (implementation choice)
for i in range(len(expression)):
c = expression[i]
if c == "(":
stack.append(c)
elif c == ")":
if len(stack) == 0:
return False # closing bracket with no opening
stack.pop()
return len(stack) == 0 # True if all brackets matched
System.out.println(isBalanced("(a + b) * (c - d)")); // true
System.out.println(isBalanced("((a + b)")); // false
System.out.println(isBalanced("a + b)")); // false
print(is_balanced("(a + b) * (c - d)")) # True
print(is_balanced("((a + b)")) # False
print(is_balanced("a + b)")) # False
Quick Check (အမြန် စစ်ဆေးမေးခွန်း)
Q1. LIFO ဆိုတာ ဘာရဲ့ အတိုကောက်လဲ၊ ဘာကို ဆိုလိုသလဲ။
Q2. A, B, C ကို (ဒီအစဉ်အတိုင်း) push လုပ်ပါတယ်။ ပြီးရင် pop()၊ ပြီးရင် peek() လုပ်ပါတယ်။ peek() က ဘာကို ပြန်ပေးမလဲ။
Q3. Stack အလွတ်ပေါ်မှာ pop() ကို ခေါ်ရင် ဘာဖြစ်မလဲ။
Q4. ဘယ် လက်တွေ့ အသုံးချမှုက stack ကို သုံးသလဲ။
Q5. peek() နဲ့ pop() ဘာကွာသလဲ။
Trace Exercise (code ကို တစ်ဆင့်ချင်း လိုက်ကြည့်ခြင်း)
Operation တစ်ခုစီ ပြီးတိုင်း stack ထဲက တန်ဖိုးတွေကို trace လုပ်ပါ။
Trace: Operation တစ်ခုစီ ပြီးတိုင်း stack ထဲက တန်ဖိုးတွေနဲ့ operation တစ်ခုစီက ပြန်ပေးတဲ့ တန်ဖိုးကို မှတ်ပါ။ တန်ဖိုးတွေကို ဇယားထဲက ပုံစံအတိုင်း English လို ရိုက်ထည့်ပါ။ -- ဆိုတာ ပြန်ပေးတဲ့ တန်ဖိုး မရှိဘူးလို့ ဆိုလိုပါတယ်။
Stack<String> stack = new Stack<>();
stack.push("Red"); // Op 1
stack.push("Blue"); // Op 2
stack.push("Green"); // Op 3
stack.pop(); // Op 4
stack.push("Yellow"); // Op 5
stack.peek(); // Op 6
stack.pop(); // Op 7| Op ပြီးနောက် | Stack (အောက်ကနေ အပေါ်) | ပြန်ပေးတဲ့ တန်ဖိုး |
|---|---|---|
| 1 | [Red] | -- |
| 2 | [Red, Blue] | -- |
| 3 | [Red, Blue, Green] | -- |
| 4 | ||
| 5 | -- | |
| 6 | ||
| 7 |
Code Completion (code ကွက်လပ် ဖြည့်ခြင်း)
String တစ်ခုက palindrome (ရှေ့က ဖတ်ဖတ်၊ နောက်က ဖတ်ဖတ် အတူတူ ဖြစ်တဲ့ စကားလုံး) ဖြစ်မဖြစ် stack သုံးပြီး စစ်တဲ့ method ကို ဖြည့်ပါ။
ကွက်လပ် ဖြည့်ပါ: Character အားလုံးကို push လုပ်ပါ၊ ပြီးရင် pop လုပ်ပြီး နှိုင်းယှဉ်ပါ။
public static boolean isPalindrome(String text) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < text.length(); i++) {
stack.(text.charAt(i));
}
for (int i = 0; i < text.length(); i++) {
if (text.charAt(i) != stack.) {
return ;
}
}
return true;
}Spot the Error (အမှား ရှာခြင်း)
ဒီ code က ဂဏန်း အားလုံးကို ပြောင်းပြန် အစဉ်နဲ့ print ထုတ်ရမှာ ဖြစ်ပေမယ့် နောက်ဆုံး တစ်ခု ကျန်ခဲ့ပါတယ်။
Bug ရှာပါ: ဒီ code က ဂဏန်း အားလုံးကို ပြောင်းပြန် print ထုတ်ရမှာ ဖြစ်ပေမယ့် နောက်ဆုံး တစ်ခု ကျန်ခဲ့ပါတယ်။ (Line 3 က 3 2 1 လို့ print ထုတ်ရမယ်လို့ ပြောတဲ့ comment ပါ။)
Line 4 အတွက် မှန်ကန်တဲ့ ပြင်နည်းကို ရွေးပါ:
Predict the Output (output ကို ကြိုခန့်မှန်းခြင်း)
ကြိုခန့်မှန်းပါ: ဒီ code က ဘာကို print ထုတ်မလဲ။
Stack<Integer> s = new Stack<>();
s.push(5);
s.push(10);
s.push(15);
System.out.println(s.pop());
s.push(20);
System.out.println(s.pop());
System.out.println(s.peek());Practice Exercises (လေ့ကျင့်ခန်းများ)
Core (အခြေခံ အဆင့်)
-
Stack ကို အဆင့်ဆင့် လိုက်ကြည့်ခြင်း။ Stack အလွတ် တစ်ခုကနေ စပြီး ဒီ operation တွေကို လုပ်ပါ၊ operation တစ်ခုစီ ပြီးတိုင်း stack ထဲက တန်ဖိုးတွေကို ရေးပါ: push(5), push(10), push(15), pop(), push(20), pop(), pop(), peek()။
-
Array ကို ပြောင်းပြန်လှန်ခြင်း။
int[]array တစ်ခုကို လက်ခံပြီးStack<Integer>ကို သုံးကာ element တွေကို ပြောင်းပြန် အစဉ်နဲ့ စီထားတဲ့ array အသစ် တစ်ခုကို return လုပ်တဲ့ method ကို ရေးပါ။ -
Stack ကို ဘယ်မှာ သုံးသင့်လဲ။ အောက်က အခြေအနေ တစ်ခုစီအတွက် stack က သင့်တော်ရဲ့လား၊ ဘာကြောင့်လဲဆိုတာ ရှင်းပြပါ:
- (a) Browser history (back ခလုတ်) ကို စီမံခြင်း
- (b) ကုန်တိုက် ငွေရှင်းကောင်တာမှာ တန်းစီခြင်း
- (c) သင်္ချာ expression တစ်ခုထဲက nested (တစ်ခုထဲမှာ တစ်ခု) ကွင်းတွေကို တွက်ခြင်း
Extension (တိုးချဲ့ အဆင့်)
-
Undo စနစ်။ ရိုးရှင်းတဲ့ text editor (စာရိုက်ပြီး ပြင်တဲ့ program) model တစ်ခုကို ဖန်တီးပါ: line တွေ သိမ်းဖို့
ArrayList<String>တစ်ခုနဲ့ undo အတွက်Stack<String>တစ်ခု သုံးပါ။addLine(String line)(list ထဲ ထည့်ပြီး undo stack ပေါ်ကို push လုပ်ပါတယ်) နဲ့undo()(နောက်ဆုံး ထည့်ခဲ့တဲ့ line ကို ဖယ်ထုတ်ပါတယ်) ကို ရေးပါ။ -
Stack နှစ်ခုနဲ့ sort လုပ်ခြင်း။ ကျပန်း အစဉ်နဲ့ ရှိနေတဲ့ integer (ကိန်းပြည့်) stack တစ်ခုကို ပေးထားပါတယ်။ Stack နောက်ထပ် တစ်ခုကို သုံးပြီး အငယ်ဆုံး တန်ဖိုး အပေါ်ဆုံးမှာ ရောက်အောင် element တွေကို sort (အစဉ်တကျ စီ) လုပ်ပါ။ Push၊ pop၊ peek နဲ့ isEmpty ကိုပဲ သုံးခွင့် ရှိပါတယ်။
Challenge (စိန်ခေါ်မှု အဆင့်)
- Postfix expression တွက်စက်။ Postfix (Reverse Polish Notation:
+၊*လို သင်္ကေတကို ကိန်းတွေရဲ့ နောက်မှာ ရေးတဲ့ ပုံစံ) expression တွေကို တွက်ပေးတဲ့ ဂဏန်းတွက်စက် program တစ်ခုကို ရေးပါ။ ဥပမာ"3 4 + 2 *"ဆိုတာ(3 + 4) * 2 = 14ကို ဆိုလိုပါတယ်။ Stack ကို သုံးပါ: ကိန်းတွေကို push လုပ်ပါ၊ operator (တန်ဖိုးတွေကို တွက်ချက်တဲ့ သင်္ကေတ) တစ်ခုကို တွေ့တဲ့အခါ ကိန်း နှစ်ခုကို pop လုပ်ပြီး အဲဒီ operator နဲ့ တွက်ကာ ရလဒ်ကို push လုပ်ပါ။
ဆက်စပ် ခေါင်းစဉ်များ
- အရင် လေ့လာထားရမယ့် ခေါင်းစဉ်: 1D Arrays (တန်းတစ်တန်းတည်းမှာ စီထားတဲ့ ဒေတာအစုများ): index (နေရာအမှတ်) နဲ့ ယူသုံးတဲ့ collection (ဒေတာအစု) တွေကို နားလည်ခြင်း
- အရင် လေ့လာထားရမယ့် ခေါင်းစဉ်: ArrayList (ကြီးလာ၊ သေးသွားနိုင်တဲ့ list): Java generics (သိမ်းမယ့် ဒေတာ type ကို ထောင့်ကွင်း
< >ထဲမှာ သတ်မှတ်ပေးတဲ့ ပုံစံ) ကို သုံးတဲ့ dynamic collection တွေ - ဆက်စပ် ခေါင်းစဉ်: Queues (အရင်ထည့်တာ အရင်ထွက်တဲ့ တန်းများ): stack နဲ့ ဆန့်ကျင်ဘက်ဖြစ်တဲ့ FIFO (အရင်ဝင်တာ အရင်ထွက်) structure
- နောက်ထပ် လေ့လာမယ့် ခေါင်းစဉ်: Recursion (method က သူ့ကိုယ်သူ ပြန်ခေါ်ခြင်း)၊ HL (Higher Level: IB သင်တန်းမှာ ပိုနက်နက်ရှိုင်းရှိုင်း လေ့လာရတဲ့ အဆင့်) အတွက်ပါ: call stack ကိုယ်တိုင်က stack တစ်ခုပါ
- နောက်ထပ် လေ့လာမယ့် ခေါင်းစဉ်: ADTs: Stacks from Scratch (stack ကို အစကနေ ကိုယ်တိုင် တည်ဆောက်ခြင်း)၊ HL အတွက်ပါ: ကိုယ်ပိုင် stack ကို တည်ဆောက်ခြင်း