အခန်း ၇ - Stack and Queue

Stack ဆိုတာ Data တွေကို အထပ်လိုက် စီထားတဲ့ ပုံစံမျိုး (ဥပမာ - စာအုပ်ပုံ) အလုပ်လုပ်တဲ့ Data Structure တစ်ခု ဖြစ်ပါတယ်။ သူ့မှာ အဓိက စည်းကမ်းတစ်ခု ရှိပါတယ်။ အဲ့ဒါကတော့ LIFO (Last-In, First-Out) ဖြစ်ပါတယ်။

LIFO (Last-In, First-Out)

LIFO ဆိုတာ "နောက်ဆုံးမှ ဝင်လာတဲ့ကောင်က ပထမဆုံး ပြန်ထွက်ရမယ်" လို့ ဆိုလိုတာပါ။

ဥပမာ

စားသောက်ဆိုင် (Buffet) တစ်ခုမှာ ပန်းကန်ပြားတွေကို ပုံးထဲမှာ တစ်ချပ်ပေါ် တစ်ချပ် ထပ်ပြီး စီထားတာကို မြင်ဖူးမှာပါ။ စားပွဲထိုးက ဆေးပြီးသား ပန်းကန်အသစ်တွေကို ထည့်တဲ့အခါ အပေါ်ဆုံးကနေပဲ ထပ်တင်ရပါတယ်။ (Push)

စားမယ့်သူတွေ လာယူတဲ့အခါကျရင်လည်း အပေါ်ဆုံးက ပန်းကန် (နောက်ဆုံးမှ ဆေးပြီး တင်လိုက်တဲ့ ပန်းကန်) ကိုပဲ အရင်ဆုံး ယူသုံးကြပါတယ်။ (Pop)

အောက်ဆုံးမှာရှိတဲ့ ပန်းကန်ကို လိုချင်ရင် အပေါ်က ပန်းကန်တွေ အကုန်လုံးကို အရင် ဖယ်ထုတ်ပစ်မှသာ ရပါလိမ့်မယ်။ ဒါဟာ LIFO ရဲ့ အကောင်းဆုံး ဥပမာပါပဲ။

အဓိက လုပ်ဆောင်ချက်များ (Operations)

Stack တစ်ခုမှာ အဓိက လုပ်ဆောင်ချက် ၃ ခု ရှိပါတယ် —

1. Push: Data တစ်ခုကို Stack ရဲ့ အပေါ်ဆုံး (Top) မှာ ထည့်တာ။
2. Pop: Stack ရဲ့ အပေါ်ဆုံးက Data ကို ဖယ်ရှားပြီး ပြန်ထုတ်ပေးတာ။
3. Peek / Top: အပေါ်ဆုံးမှာ ဘာရှိလဲဆိုတာကို Data မထုတ်ဘဲ ကြည့်တာ။

ဒီအလုပ် ၃ ခုလုံးဟာ Stack ရဲ့ အပေါ်ဆုံး (Top) မှာပဲ တိုက်ရိုက် လုပ်တာ ဖြစ်တဲ့အတွက် Time Complexity ဟာ $O(1)$ ဖြစ်ပါတယ်။

graph TD
    subgraph "Stack Structure"
    D[Item 4 - Top]
    C[Item 3]
    B[Item 2]
    A[Item 1 - Bottom]
    end

    PushIn((Push)) --> D
    D --> PopOut((Pop))

    style D fill:#f9f,stroke:#333

Java ဖြင့် Stack အသုံးပြုခြင်း

Java မှာဆိုရင် java.util.Stack ကို သုံးပြီး အလွယ်တကူ ရေးနိုင်ပါတယ်။

နောက်ပိုင်း ခေတ်သစ် Java မှာ Stack အစား Deque (ဥပမာ ArrayDeque) ကို Stack အနေနဲ့ သုံးဖို့ ပိုမို အကြံပြုကြပါတယ်။ ဒါပေမယ့် Concept ကို နားလည်ဖို့အတွက် ရိုးရှင်းတဲ့ Stack ကို အရင် ကြည့်ရအောင်။

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        // Stack တစ်ခု တည်ဆောက်ခြင်း
        Stack<String> history = new Stack<>();

        // Data ထည့်ခြင်း (Push) - O(1)
        history.push("google.com");
        history.push("facebook.com");
        history.push("youtube.com");

        // အပေါ်ဆုံးက ဘာလဲ ကြည့်ခြင်း (Peek) - O(1)
        System.out.println("Top Website: " + history.peek()); // youtube.com

        // Data ထုတ်ခြင်း (Pop) - O(1)
        String lastVisited = history.pop();
        System.out.println("Back from: " + lastVisited);

        // လက်ရှိ အပေါ်ဆုံးက ဘာလဲ
        System.out.println("Now Top is: " + history.peek()); // facebook.com
    }
}

Time Complexity

မှတ်ချက်: Stack မှာ Data ရှာဖွေတာ (Search) က $O(n)$ ကြာပါတယ်။ ဘာကြောင့်လဲဆိုတော့ အောက်ဆုံးက Data ကို လိုချင်ရင် အပေါ်က Data တွေကို တစ်ခုချင်းစီ ဖယ်ပြီးမှ ရှာလို့ ရလို့ပါ။ Data ကို လျင်မြန်စွာ ရှာဖွေချင်တယ် ဆိုရင် Hash Table လိုမျိုး အခြား Data Structure တွေကို သုံးရပါမယ်။

လက်တွေ့အသုံးချမှုများ

နေ့စဉ်သုံးနေတဲ့ Software တွေမှာ Stack ကို နေရာများစွာမှာ အသုံးပြုကြပါတယ် —

• Undo / Redo Function: စာရိုက်တဲ့အခါ မှားလို့ နောက်ပြန်ဆုတ် (Ctrl+Z) ချင်ရင် နောက်ဆုံးရိုက်ခဲ့တဲ့ အခြေအနေတွေကို Stack ထဲကနေ တစ်ခုချင်း ပြန်ထုတ်ပေးတာပါ။
• Browser History (Back / Forward Button): Back Button နှိပ်ရင် နောက်ဆုံးကြည့်ခဲ့တဲ့ Website (Top of Stack) ကို ပြန်ပြတာပါ။
• Call Stack: Programming Language အများစုမှာ Function (Method) တစ်ခုထဲကနေ နောက်တစ်ခုကို ထပ်ဆင့်ခေါ်တဲ့အခါ ဘယ်နေရာကနေ ပြန်စရမလဲဆိုတာ မှတ်သားဖို့ Stack Memory ကို သုံးပါတယ်။

Design Pattern စာအုပ်တွင် Command Pattern တွင် Stack သုံးထားတာကို တွေ့နိုင်မှာပါ။

Questions

Stack ကို နားလည်သွားပြီ ဆိုရင် Stack ကို လက်တွေ့ အသုံးချရမယ့် LeetCode ပုစ္ဆာ တချို့ကို ကြည့်ရအောင်။

Valid Parentheses

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

ဒီပုစ္ဆာက Stack ကို လေ့လာတဲ့ သူတွေအတွက် အခြေခံ အကျဆုံးနဲ့ အရေးအကြီးဆုံး ပုစ္ဆာ ဖြစ်ပါတယ်။ ကျွန်တော်တို့ string ထဲမှာ အဖွင့် ကွင်း (, {, [ တွေ့တိုင်း သူနဲ့တွဲတဲ့ အပိတ်ကွင်း ကို Stack ထဲ push ထည့်ပါမယ်။ အပိတ် ကွင်း တွေ့တဲ့ အခါမှာတော့ Stack ရဲ့ အပေါ်ဆုံးက ကွင်းကို pop လုပ်ပြီး လက်ရှိ အပိတ်ကွင်းနဲ့ ကိုက်ညီမှု ရှိမရှိ စစ်ဆေးပါမယ်။

$O(n)$ time complexity, $O(n)$ space complexity ဖြစ်ရပါမယ်။

import java.util.Stack;

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();

        for (char c : s.toCharArray()) {
            // အဖွင့်ကွင်းများ ဖြစ်လျှင် သက်ဆိုင်ရာ အပိတ်ကွင်းကို Stack ထဲ ထည့်သည်
            if (c == '(') {
                stack.push(')');
            } else if (c == '{') {
                stack.push('}');
            } else if (c == '[') {
                stack.push(']');
            } else {
                // အပိတ်ကွင်း ဖြစ်ပါက Stack အလွတ်ဖြစ်နေသလား သို့မဟုတ်
                // Stack အပေါ်ဆုံးက ကွင်းနှင့် မတူဘူးလား စစ်ဆေးသည်
                if (stack.isEmpty() || stack.pop() != c) {
                    return false;
                }
            }
        }

        // Stack လွတ်သွားမှသာ ကွင်းတွေ အစုံအလင် ပိတ်ပြီးသွားတာဖြစ်သည်
        return stack.isEmpty();
    }
}

Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

• MinStack() initializes the stack object.
• void push(int val) pushes the element val onto the stack.
• void pop() removes the element on the top of the stack.
• int top() gets the top element of the stack.
• int getMin() retrieves the minimum element in the stack.

You must implement a solution with $O(1)$ time complexity for each function.

Example 1:

Input:
["MinStack", "push", "push", "push", "getMin", "pop", "top", "getMin"]
[[], [1], [2], [0], [], [], [], []]

Output: [null,null,null,null,0,null,2,1]

Explanation:
MinStack minStack = new MinStack();
minStack.push(1);
minStack.push(2);
minStack.push(0);
minStack.getMin(); // return 0
minStack.pop();
minStack.top();    // return 2
minStack.getMin(); // return 1

ပုံမှန် Stack မှာ အသေးဆုံး တန်ဖိုး (Minimum element) ကို လိုချင်ရင် အပေါ်ဆုံးကနေ အောက်ခြေ အထိ လိုက်ရှာရတဲ့အတွက် $O(n)$ အချိန် ကြာပါတယ်။ အခုက Pushing နဲ့ Popping လုပ်နေချိန်မှာပါ $O(1)$ Time Complexity နဲ့ အသေးဆုံး တန်ဖိုးကို ချက်ချင်း သိချင်တာပါ။

ဒီ ပြဿနာကို ဖြေရှင်းဖို့အတွက် Stack နှစ်ခု (သို့မဟုတ် Stack တစ်ခုတည်းမှာ Minimum Value ကိုပါ တွဲသိမ်းတာ) သုံးလို့ ရပါတယ်။ minStack ဆိုတဲ့ နောက်ထပ် Stack တစ်ခု ထားပြီး၊ အသစ်ဝင်လာတဲ့ val က လက်ရှိ အသေးဆုံး တန်ဖိုးထက် ငယ်နေရင် (သို့မဟုတ် ညီနေရင်) minStack ထဲကိုပါ ထည့်သိမ်းပေးလိုက်ယုံပါပဲ။ ဒီနည်းနဲ့ operation တိုင်း $O(1)$ ဖြစ်ပြီး၊ နောက်ထပ် Stack တစ်ခု ပိုသုံးရတဲ့အတွက် space ကတော့ $O(n)$ ဖြစ်ပါတယ်။

import java.util.Stack;

class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int val) {
        stack.push(val);
        // minStack လွတ်နေလျှင် (သို့) ထည့်မည့်တန်ဖိုးသည် လက်ရှိ အနည်းဆုံးထက် ငယ်/ညီ နေလျှင်
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }

    public void pop() {
        // ထုတ်လိုက်သော တန်ဖိုးသည် အနည်းဆုံး တန်ဖိုးဖြစ်နေပါက minStack မှပါ ထုတ်သည်
        if (stack.pop().equals(minStack.peek())) {
            minStack.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

Evaluate Reverse Polish Notation

You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.

Evaluate the expression. Return an integer that represents the value of the expression.

Note that:

• The valid operators are '+', '-', '*', and '/'.
• Each operand may be an integer or another expression.
• The division between two integers always truncates toward zero.
• There will not be any division by zero.
• The input represents a valid arithmetic expression in a reverse polish notation.

Example 1:

Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Example 2:

Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Reverse Polish Notation (RPN) ဟာ ဂဏန်း (Operands) တွေကို အရင်ရေးပြီးမှ ပေါင်းနှုတ်မြှောက်စား သင်္ကေတ (Operators) တွေကို နောက်ကနေ ကပ်ရေးတဲ့ နည်းစနစ်ပါ။ ဥပမာ 2 + 1 ကို RPN နဲ့ ရေးရင် 2 1 + ဖြစ်ပါတယ်။ RPN ဟာ Stack နှင့် တွဲဖက် အသုံးပြုဖို့ အကောင်းဆုံး အရာ ဖြစ်ပါတယ်။ ကွန်ပျူတာတွေဟာ သင်္ချာညီမျှခြင်းတွေကို တွက်ချက်တဲ့အခါ Stack ကို သုံးပြီး အခုလိုပဲ တွက်ချက်ပါတယ်။

အလွယ်ဆုံး စဥ်းစားနည်းကတော့ —

• ဂဏန်း တွေ့ရင် Stack ထဲ ထည့် (Push)။
• သင်္ကေတ (+, -, *, /) တွေ့ရင် Stack ထဲကနေ ဂဏန်း ၂ ခု ထုတ် (Pop) ပြီး တွက်ချက်ကာ ရလာတဲ့ အဖြေကို Stack ထဲ ပြန်ထည့် (Push) ပြုလုပ်သွားယုံပါပဲ။
• နောက်ဆုံး Stack ထဲမှာ ကျန်နေတဲ့ ဂဏန်း ဟာ အဖြေ ဖြစ်ပါတယ်။

import java.util.Stack;

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();

        for (String token : tokens) {
            // Operator တွေ့ပါက တွက်ချက်ခြင်းပြုလုပ်သည်
            if (token.equals("+")) {
                stack.push(stack.pop() + stack.pop());
            } else if (token.equals("*")) {
                stack.push(stack.pop() * stack.pop());
            } else if (token.equals("-")) {
                // အရင်ထွက်လာသည့်ဂဏန်းသည် အနောက်က ဂဏန်းဖြစ်သည်
                int a = stack.pop();
                int b = stack.pop();
                stack.push(b - a);
            } else if (token.equals("/")) {
                int a = stack.pop();
                int b = stack.pop();
                stack.push(b / a);
            } else {
                // ဂဏန်းတွေ့ပါက Stack ထဲသို့ Integer ပြောင်း၍ ထည့်သည်
                stack.push(Integer.parseInt(token));
            }
        }

        return stack.pop();
    }
}

Daily Temperatures

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the $i^{th}$ day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Example 1:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Example 2:

Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

ဒီပုစ္ဆာမှာ နေ့စဉ် အပူချိန်တွေ ပေးထားပြီး နောက်ရက်တွေမှာ ကိုယ့်ထက် ပိုပူတဲ့နေ့ ရောက်ဖို့ ဘယ်နှရက် စောင့်ရမလဲ ဆိုတာကို ရှာရမှာပါ။

ရိုးရိုး Nested Loop နဲ့ ရှာရင် $O(n^2)$ ကြာပါမယ်။ Stack (Monotonic Decreasing Stack) ကို သုံးပြီး $O(n)$ နဲ့ ဖြေရှင်းလို့ ရပါတယ်။
Stack ထဲမှာ အပူချိန်ရဲ့ Index တွေကို သိမ်းပါမယ်။ လက်ရှိ ဝင်လာတဲ့ အပူချိန်က Stack ရဲ့ အပေါ်ဆုံးမှာ ရှိတဲ့ အပူချိန်ထက် ကြီးနေရင်၊ အဲ့ဒီ Stack ထဲက Index အတွက် ပိုပူတဲ့နေ့ကို တွေ့သွားပါပြီ။ ဒါကြောင့် Stack ကနေ Pop လုပ်ပြီး ရက်ကွာခြားချက် (Current Index - Popped Index) ကို အဖြေအဖြစ် မှတ်ယူပါမယ်။

import java.util.Stack;

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] result = new int[temperatures.length];
        // Index များကို သိမ်းမည့် Stack
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < temperatures.length; i++) {
            // လက်ရှိ အပူချိန်သည် Stack အပေါ်ဆုံးမှ အပူချိန်ထက် ကြီးနေသရွေ့
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int prevIndex = stack.pop();
                // စောင့်ရမည့် ရက်အရေအတွက်ကို မှတ်သည်
                result[prevIndex] = i - prevIndex;
            }
            stack.push(i);
        }

        return result;
    }
}

Car Fleet

There are n cars at given miles away from the starting mile 0, traveling to reach the mile target. You are given two integer arrays position and speed, both of length n, where position[i] is the starting mile of the $i^{th}$ car and speed[i] is the speed of the $i^{th}$ car in miles per hour.

A car cannot pass another car ahead of it. It can only catch up to another car and then drive at the same speed. A car fleet is some non-empty set of cars driving at the same position and same speed. Note that a single car is also a car fleet.

Return the number of car fleets that will arrive at the destination.

Example 1:

Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Output: 3
Explanation:
- The cars starting at 10 (speed 2) and 8 (speed 4) become a fleet, meeting each other at 12.
- The car starting at 0 does not catch up to any other car, so it is a fleet by itself.
- The cars starting at 5 (speed 1) and 3 (speed 3) become a fleet, meeting each other at 6.
  The fleet moves at speed 1 until it reaches target.

ဒီပုစ္ဆာမှာ ကားတွေက ပန်းတိုင် (target) ကို သွားကြမှာပါ။ အနောက်ကကားက အမြန်မောင်းလို့ အရှေ့ကကားကို မီသွားရင်တောင် ကျော်တက်လို့ မရဘဲ အရှေ့ကားနဲ့ တစ်တန်းတည်း (Fleet) အဖြစ် ပတ်သက်သွားရမှာပါ။ နောက်ဆုံး ပန်းတိုင်ရောက်ရင် Fleet ဘယ်နှစု ဖြစ်မလဲဆိုတာ မေးတာပါ။

ဒီပုစ္ဆာကို ဖြေရှင်းဖို့ ကားတွေကို သူတို့ရဲ့ စတင်တဲ့ နေရာ (Position) အလိုက် အစဉ်လိုက် (အကြီးမှ အငယ်၊ ပန်းတိုင်နဲ့ အနီးဆုံးကနေ အဝေးဆုံး) စီ (Sort) စဉ်းစားပါမယ်။
ပြီးရင် ကားတစ်စီးစီ ပန်းတိုင်ရောက်ဖို့ ကြာမယ့် အချိန် (Distance / Speed) ကို တွက်ပါမယ်။
အနောက်ကလာတဲ့ ကားရဲ့ အချိန်ဟာ အရှေ့ကကားရဲ့ အချိန်ထက် ငယ်နေရင် (သို့) ညီနေရင် (ဆိုလိုတာက ပိုမြန်နေရင် သို့မဟုတ် တချိန်တည်းရောက်ရင်) အရှေ့ကားကို မီသွားပြီး Fleet တစ်ခုတည်း ဖြစ်သွားပါမယ်။ အချိန် ပိုကြီးနေရင်တော့ (ဆိုလိုတာက ပိုနှေးနေရင်) မမီတဲ့အတွက် Fleet အသစ် တစ်ခု ဖြစ်ပါမယ်။

import java.util.Arrays;
import java.util.Stack;

class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        int n = position.length;
        // ကားများ၏ Position နှင့် ကြာမည့်အချိန်ကို တွဲသိမ်းရန် Array
        double[][] cars = new double[n][2];
        for (int i = 0; i < n; i++) {
            cars[i][0] = position[i];
            cars[i][1] = (double)(target - position[i]) / speed[i];
        }

        // Position အလိုက် အငယ်မှ အကြီးစီသည်
        Arrays.sort(cars, (a, b) -> Double.compare(a[0], b[0]));

        Stack<Double> stack = new Stack<>();

        // ပန်းတိုင်နှင့် အနီးဆုံး ကား (Array ရဲ့ အနောက်ဆုံး) မှစ၍ ပြောင်းပြန် စစ်ဆေးသည်
        for (int i = n - 1; i >= 0; i--) {
            double time = cars[i][1];
            // Stack လွတ်နေလျှင် သို့မဟုတ် လက်ရှိကားသည် Stack ထဲရှိ အရှေ့ကားထက် အချိန်ပိုကြာလျှင် (နှေးပြီး မမီလျှင်)
            if (stack.isEmpty() || time > stack.peek()) {
                stack.push(time);
            }
            // အချိန်ပိုနည်းလျှင် (ပိုမြန်လျှင်) အရှေ့ကားကို မီသွား၍ Fleet တူသွားသဖြင့် Stack ထဲ ထပ်မထည့်ပါ
        }

        // Stack ၏ အရွယ်အစားသည် Fleet အရေအတွက် ဖြစ်သည်
        return stack.size();
    }
}

Largest Rectangle In Histogram

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Example 1:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The largest rectangle is shown in the shaded area, which has an area = 10 units.

ဒီပုစ္ဆာကတော့ Histogram (တိုင်လေးတွေ) ထဲမှာ အကျယ်ဆုံး စတုဂံ ဧရိယာ ကို ရှာရမယ့် မေးခွန်းပါ။ Stack ကို သုံးပြီး $O(n)$ အချိန်နဲ့ တွက်ထုတ်နိုင်တဲ့ အကောင်းဆုံး အသုံးချမှုတစ်ခု ဖြစ်ပါတယ်။

Monotonic Increasing Stack ကို သုံးပါမယ်။ Stack ထဲမှာ တိုင်တွေရဲ့ index တွေကို အစဉ်လိုက် မြင့်လာသရွေ့ သိမ်းသွားပါမယ်။
လက်ရှိ တိုင်ရဲ့ အမြင့်က Stack ရဲ့ အပေါ်ဆုံးက တိုင်အမြင့်ထက် ငယ်သွားပြီ ဆိုရင်၊ Stack ထဲက အရှည်ဆုံး တိုင်တွေအတွက် နောက်ထပ် ဆန့်လို့ရမယ့် ဘက် (ညာဘက် နယ်နိမိတ်) ကို တွေ့သွားပါပြီ။
ဒါကြောင့် Stack ကနေ Pop လုပ်ပြီး၊ အမြင့် (height = heights[popped index]) နဲ့ အကျယ် (width = current_index - new_top_index - 1) ကို မြှောက်ကာ ဧရိယာ အကြီးဆုံးကို တွက်ချက် မှတ်သားသွားပါမယ်။

import java.util.Stack;

class Solution {
    public int largestRectangleArea(int[] heights) {
        int maxArea = 0;
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i <= heights.length; i++) {
            // Array ပြီးဆုံးသွားလျှင် ကျန်နေသည့် Stack ကို ရှင်းရန် အမြင့် 0 ထည့်စဉ်းစားသည်
            int h = (i == heights.length) ? 0 : heights[i];

            // လက်ရှိအမြင့်သည် Stack အပေါ်ဆုံးမှ အမြင့်ထက် ငယ်နေသရွေ့ Pop လုပ်၍ ဧရိယာတွက်သည်
            while (!stack.isEmpty() && h < heights[stack.peek()]) {
                int height = heights[stack.pop()];
                // Stack လွတ်သွားလျှင် အစကနေ လက်ရှိအထိ ကျယ်သည်ဟု ယူဆသည်
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i);
        }

        return maxArea;
    }
}

Queue

Queue ဆိုတာ Data တွေကို တန်းစီစောင့် တဲ့ ပုံစံ (ဥပမာ - ဆိုင်ရှေ့မှာ လူတန်းစီတာ) အလုပ်လုပ်တဲ့ Data Structure ပါ။ Stack နဲ့ ပြောင်းပြန်ဖြစ်ပြီး အဓိက စည်းကမ်းက FIFO (First-In, First-Out) ဖြစ်ပါတယ်။

FIFO (First-In, First-Out)

FIFO ဆိုတာ "ပထမဆုံး ဝင်လာတဲ့ကောင်က ပထမဆုံး ပြန်ထွက်ရမယ်" လို့ ဆိုလိုတာပါ။

လွယ်ကူသော ဥပမာ (Ticket Counter Analogy):
ရုပ်ရှင်ရုံ လက်မှတ်ရောင်းကောင်တာရှေ့မှာ လူတွေ တန်းစီနေတာကို မြင်ဖူးမှာပါ။ အစောဆုံး လာတန်းစီတဲ့သူက အရှေ့ဆုံး (Front) မှာ ရှိပြီး၊ ပထမဆုံး လက်မှတ်ရတယ်။ နောက်မှ လာသူတွေက အနောက်ဆုံး (Rear / Back) ကနေ တန်းဆက်စီရတယ်။ ဘယ်သူမှ ဖြတ်ဝင်လို့ မရဘူး။ ဒါဟာ FIFO ရဲ့ အကောင်းဆုံး ဥပမာပါ။

အဓိက လုပ်ဆောင်ချက်များ (Operations)

Queue တစ်ခုမှာ အဓိက လုပ်ဆောင်ချက် ၃ ခု ရှိပါတယ် —

1. Enqueue: Data တစ်ခုကို Queue ရဲ့ အနောက်ဆုံး (Rear) မှာ ထည့်တာ။
2. Dequeue: Queue ရဲ့ အရှေ့ဆုံး (Front) က Data ကို ဖယ်ရှားပြီး ပြန်ထုတ်ပေးတာ။
3. Peek / Front: အရှေ့ဆုံးမှာ ဘာရှိလဲဆိုတာကို Data မထုတ်ဘဲ ကြည့်တာ။

ဒီအလုပ် ၃ ခုလုံးဟာ Queue ရဲ့ အစွန်း (Front/Rear) မှာပဲ လုပ်တာ ဖြစ်တဲ့အတွက် Time Complexity ဟာ $O(1)$ ဖြစ်ပါတယ်။

graph LR
    In((Enqueue)) --> R
    subgraph "Queue Structure"
    direction LR
    F[Item 1 - Front] --> B[Item 2] --> C[Item 3] --> R[Item 4 - Rear]
    end
    F --> Out((Dequeue))

    style F fill:#9f9,stroke:#333
    style R fill:#ff9,stroke:#333

Java ဖြင့် Queue အသုံးပြုခြင်း

Java မှာ Queue က interface တစ်ခု ဖြစ်ပြီး၊ LinkedList ဒါမှမဟုတ် ArrayDeque နဲ့ တည်ဆောက်လေ့ ရှိပါတယ်။ (ArrayDeque က ပိုမြန်လို့ အကြံပြုပါတယ်။)

import java.util.ArrayDeque;
import java.util.Queue;

public class QueueExample {
    public static void main(String[] args) {
        Queue<String> queue = new ArrayDeque<>();

        // Data ထည့်ခြင်း (Enqueue) - O(1)
        queue.offer("Customer 1");
        queue.offer("Customer 2");
        queue.offer("Customer 3");

        // အရှေ့ဆုံးက ဘာလဲ ကြည့်ခြင်း (Peek) - O(1)
        System.out.println("Front: " + queue.peek()); // Customer 1

        // Data ထုတ်ခြင်း (Dequeue) - O(1)
        String served = queue.poll();
        System.out.println("Serving: " + served); // Customer 1

        // လက်ရှိ အရှေ့ဆုံးက ဘာလဲ
        System.out.println("Now Front: " + queue.peek()); // Customer 2
    }
}

မှတ်ချက်: offer/poll/peek က Queue လွတ်/ပြည့် အခြေအနေမှာ exception မပစ်ဘဲ false/null ပြန်ပေးလို့ ပိုလုံခြုံပါတယ်။ (add/remove/element ကတော့ exception ပစ်ပါတယ်။)

Deque (Double-Ended Queue)

Deque ("deck" လို့ အသံထွက်) ဆိုတာ အစွန်းနှစ်ဖက်စလုံး (Front ရော Rear ရော) ကနေ ထည့်/ထုတ် လုပ်လို့ရတဲ့ Queue ပါ။ ဒါကြောင့် Deque တစ်ခုတည်းနဲ့ Stack (LIFO) အဖြစ်ရော Queue (FIFO) အဖြစ်ရော သုံးနိုင်ပါတယ်။ အရင်အခန်း (Sliding Window Maximum) မှာ သုံးခဲ့တဲ့ Monotonic Deque က ဒီ structure ပါပဲ။

လက်တွေ့အသုံးချမှုများ

Queue ကို "ရောက်လာတဲ့ အစဉ်အတိုင်း တစ်ခုပြီးတစ်ခု လုပ်ဆောင်" ရမယ့် နေရာတိုင်းမှာ သုံးပါတယ် —

• Background Job / Task Queue: Server မှာ email ပို့ခြင်း၊ image ပြောင်းခြင်း စတဲ့ အလုပ်တွေကို ရောက်လာတဲ့ အစဉ်အတိုင်း တန်းစီ လုပ်ဆောင်တယ်။
• Print Queue: Printer ဆီ စာ ၃ စောင် တစ်ပြိုင်နက် ပို့ရင် ပထမ ပို့တဲ့ဟာ အရင် ထွက်တယ်။
• Request / Message Queue: Web server တွေ၊ Kafka/RabbitMQ လို message broker တွေက request တွေကို Queue နဲ့ စီမံတယ်။
• BFS (Breadth-First Search): Graph / Tree ကို အလွှာလိုက် ရှာဖွေတဲ့အခါ Queue သုံးတယ်။ (Chapter 18 မှာ အသေးစိတ် တွေ့ရပါမယ်။)

Questions

Queue ကို နားလည်သွားပြီ ဆိုရင် Stack နဲ့ Queue ၂ ခု ဆက်စပ်ပုံ မြင်သာအောင် classic ပုစ္ဆာ ၃ ပုဒ်ကို ကြည့်ရအောင်။

Implement Queue using Stacks

Stack ၂ ခုကိုသာ သုံးပြီး FIFO Queue တစ်ခု (push, pop, peek, empty) ကို တည်ဆောက်ပါ။

Stack က LIFO ဖြစ်ပေမယ့် Stack ၂ ခု တွဲသုံးရင် order ကို ပြောင်းပြန် လှန်ပြီး FIFO ဖြစ်အောင် လုပ်နိုင်ပါတယ်။

• input stack — အသစ်ဝင်လာတာတွေ push လုပ်ဖို့။
• output stack — ထုတ်ဖို့။ output လွတ်နေချိန် input ထဲက အကုန် ကူးထည့် လိုက်ရင် အစဉ်အတိုင်း ပြောင်းပြန် ဖြစ်သွားလို့ FIFO ရတယ်။

ဒီ "ကူးထည့်ခြင်း" က ရံဖန်ရံခါသာ ဖြစ်တဲ့အတွက် operation တစ်ခုချင်း amortized $O(1)$ ဖြစ်ပါတယ်။

import java.util.Stack;

class MyQueue {
    private Stack<Integer> input;
    private Stack<Integer> output;

    public MyQueue() {
        input = new Stack<>();
        output = new Stack<>();
    }

    public void push(int x) {
        input.push(x);
    }

    public int pop() {
        peek(); // output ထဲ data ရှိအောင် အရင်ပြင်သည်
        return output.pop();
    }

    public int peek() {
        // output လွတ်နေမှသာ input ထဲက အကုန် ကူးထည့်သည် (order ပြောင်းပြန်ဖြစ်သွားသည်)
        if (output.isEmpty()) {
            while (!input.isEmpty()) {
                output.push(input.pop());
            }
        }
        return output.peek();
    }

    public boolean empty() {
        return input.isEmpty() && output.isEmpty();
    }
}

Implement Stack using Queues

ဒီတစ်ခါ ပြောင်းပြန်ပါ။ Queue သုံးပြီး LIFO Stack (push, pop, top, empty) တည်ဆောက်ပါ။

Queue တစ်ခုတည်းနဲ့ လုပ်လို့ ရပါတယ်။ နည်းလမ်းက — element အသစ် push လုပ်တိုင်း၊ အဲ့ဒီနောက် Queue ထဲမှာ ရှေ့က ကျန်နေတဲ့ element တွေ အကုန် ကို dequeue လုပ်ပြီး ပြန် enqueue လုပ်လိုက်တယ်။ ဒါဆို အသစ်ဝင်တဲ့ element က အရှေ့ဆုံးကို ရောက်သွားလို့ Stack လို နောက်ဆုံးဝင်တာ အရင်ထွက်တဲ့ ပုံစံ ဖြစ်သွားတယ်။

ဒီနည်းမှာ push က $O(n)$ ဖြစ်ပြီး၊ pop/top က $O(1)$ ဖြစ်ပါတယ်။

import java.util.ArrayDeque;
import java.util.Queue;

class MyStack {
    private Queue<Integer> queue;

    public MyStack() {
        queue = new ArrayDeque<>();
    }

    public void push(int x) {
        queue.offer(x);
        // အသစ်ဝင်တာ အရှေ့ဆုံးရောက်အောင် ရှေ့က ကျန်သမျှကို နောက်ပြန်ပို့သည်
        for (int i = 1; i < queue.size(); i++) {
            queue.offer(queue.poll());
        }
    }

    public int pop() {
        return queue.poll();
    }

    public int top() {
        return queue.peek();
    }

    public boolean empty() {
        return queue.isEmpty();
    }
}

Next Greater Element I

nums1 သည် nums2 ၏ subset ဖြစ်သည်။ nums1 ထဲက ဂဏန်းတစ်ခုစီအတွက်၊ nums2 ထဲမှာ ၎င်းရဲ့ ညာဘက်က ပထမဆုံး ပိုကြီးတဲ့ ဂဏန်း ကို ရှာပါ။ မရှိရင် -1။

Example:

Input:  nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]

ဒါက Daily Temperatures နဲ့ တူတဲ့ Monotonic Stack pattern ပါ။ nums2 ကို ဖြတ်ရင်း Stack (ကြီးစဉ်ငယ်လိုက်) သုံးပြီး ဂဏန်းတစ်ခုစီရဲ့ "next greater" ကို HashMap ထဲ မှတ်ထားပါမယ်။ ပြီးရင် nums1 အတွက် Map ထဲက အဖြေကို ထုတ်ယူရုံပါပဲ။ Time $O(n + m)$။

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> nextGreater = new HashMap<>();
        Stack<Integer> stack = new Stack<>();

        for (int num : nums2) {
            // လက်ရှိ num သည် Stack အပေါ်ဆုံးထက် ကြီးနေသရွေ့ ၎င်းတို့၏ next greater ဖြစ်သည်
            while (!stack.isEmpty() && num > stack.peek()) {
                nextGreater.put(stack.pop(), num);
            }
            stack.push(num);
        }

        int[] result = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            result[i] = nextGreater.getOrDefault(nums1[i], -1);
        }

        return result;
    }
}