24. Stack - Problems

স্ট্যাকের লজিক পরিষ্কার করার জন্য বিভিন্ন অ্যালগরিদমিক প্রবলেম সলভ করা বুদ্ধমানের কাজ। এখানে ইন্টারভিউতে আসা জনপ্রিয় ৮টি স্ট্যাক প্রবলেম নিয়ে আলোচনা করা হলো।

---

1. ব্যালেন্সড প্যারেনথেসিস (Balanced Parentheses)

একটি স্ট্রিংয়ে বিভিন্ন ব্র্যাকেট (, ), {, }, [, ] ঠিকঠাকভাবে ক্লোজ হয়েছে কি না তা চেক করা।

🛠 কর্মপদ্ধতি (Step-by-Step Logic)

1. স্ট্রিংটির প্রতিটি ক্যারেক্টার চেক করুন।
2. যদি ওপেনিং ব্র্যাকেট হয়, স্ট্যাকে Push করুন।
3. যদি ক্লোজিং ব্র্যাকেট হয়:
   • চেক করুন স্ট্যাক খালি কি না। যদি খালি হয়, তবে এটি ব্যালেন্সড নয়।
   • স্ট্যাকের Top এলিমেন্টের সাথে বর্তমান ক্লোজিং ব্র্যাকেট ম্যাচ করে কি না চেক করুন। ম্যাচ করলে Pop করুন।
4. সবশেষে যদি স্ট্যাক খালি থাকে, তবে স্ট্রিংটি ব্যালেন্সড।

Implementation

// Java Balanced Parentheses
public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') stack.push(c);
        else {
            if (stack.isEmpty()) return false;
            char top = stack.pop();
            if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')) return false;
        }
    }
    return stack.isEmpty();
}

# Python Balanced Parentheses
def is_valid(s):
    stack = []
    mapping = {")": "(", "}": "{", "]": "["}
    for char in s:
        if char in mapping:
            top = stack.pop() if stack else '#'
            if mapping[char] != top: return False
        else:
            stack.append(char)
    return not stack

Broadway

2. নেক্সট গ্রেটার এলিমেন্ট (Next Greater Element)

একটি অ্যারের প্রতিটি এলিমেন্টের জন্য তার ডানদিকের প্রথম বড় এলিমেন্টটি খুঁজে বের করা।

🛠 কর্মপদ্ধতি (Step-by-Step Logic)

• Monotonic Stack: ডানদিক থেকে ট্রাভার্স করার সময় যদি স্ট্যাকের উপরের এলিমেন্ট ছোট হয়, তবে তা পপ করুন। স্ট্যাকের টপই হবে নেক্সট গ্রেটার এলিমেন্ট। এবার বর্তমান এলিমেন্টটি পুশ করুন।

Implementation

// Java Next Greater Element
public int[] nextGreater(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    Stack<Integer> s = new Stack<>();
    for (int i = n - 1; i >= 0; i--) {
        while (!s.isEmpty() && s.peek() <= nums[i]) s.pop();
        res[i] = s.isEmpty() ? -1 : s.peek();
        s.push(nums[i]);
    }
    return res;
}

# Python Next Greater Element
def next_greater(nums):
    n = len(nums)
    res = [-1] * n
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and stack[-1] <= nums[i]:
            stack.pop()
        if stack: res[i] = stack[-1]
        stack.append(nums[i])
    return res

Broadway

3. স্টক স্প্যান প্রবলেম (Stock Span Problem)

কোনো এক দিনে স্টকের দর তার আগের কয়দিন বর্তমান দরের সমান বা কম ছিল তা বের করা।

🛠 কর্মপদ্ধতি (Step-by-Step Logic)

• এটি মূলত 'Next Greater Element on Left' বের করার মতো। স্ট্যাকে ইনডেক্সগুলো স্টোর করে আগের বড় দরের দূরত্ব বের করা হয়।

---

4. স্ট্যাক দিয়ে কিউ ইমপ্লিমেন্ট (Implement Queue using Stacks)

দুটি স্ট্যাক ব্যবহার করে FIFO (First In First Out) মেকানিজম তৈরি করা।

🛠 কর্মপদ্ধতি (Step-by-Step Logic)

• এঙ্কু (Enqueue) করার সময় সব এলিমেন্ট একটি স্ট্যাকে রাখুন। ডিঙ্কু (Dequeue) করার সময় যদি দ্বিতীয় স্ট্যাক খালি থাকে, তবে প্রথম স্ট্যাকের সব এলিমেন্ট উল্টে দ্বিতীয় স্ট্যাকে নিয়ে সেখান থেকে পপ করুন।

Implementation

// Java Queue using Stacks
class MyQueue {
    Stack<Integer> s1 = new Stack<>(), s2 = new Stack<>();
    void enqueue(int x) { s1.push(x); }
    int dequeue() {
        if (s2.isEmpty()) {
            while (!s1.isEmpty()) s2.push(s1.pop());
        }
        return s2.pop();
    }
}

# Python Queue using Stacks
class MyQueue:
    def __init__(self):
        self.s1, self.s2 = [], []
    def enqueue(self, x):
        self.s1.append(x)
    def dequeue(self, x):
        if not self.s2:
            while self.s1: self.s2.append(self.s1.pop())
        return self.s2.pop()

Broadway

5. মিন স্ট্যাক (Min Stack)

এমন একটি স্ট্যাক যেখানে পুশ এবং পপের পাশাপাশি রিলেভেন্ট মিনিমাম এলিমেন্টটি O(1) সময়ে পাওয়া যায়।

💡 টিপস

একটি এক্সট্রা স্ট্যাক (Auxiliary Stack) ব্যবহার করে প্রতি ধাপে বর্তমান মিনিমাম ভ্যালু ট্র্যাক করা যায়।

Implementation

// Java Min Stack
class MinStack {
    Stack<Integer> s = new Stack<>(), minS = new Stack<>();
    void push(int x) {
        s.push(x);
        if (minS.isEmpty() || x <= minS.peek()) minS.push(x);
    }
    int pop() {
        int x = s.pop();
        if (x == minS.peek()) minS.pop();
        return x;
    }
    int getMin() { return minS.peek(); }
}

# Python Min Stack
class MinStack:
    def __init__(self):
        self.s, self.min_s = [], []
    def push(self, x):
        self.s.append(x)
        if not self.min_s or x <= self.min_s[-1]:
            self.min_s.append(x)
    def pop(self):
        x = self.s.pop()
        if x == self.min_s[-1]: self.min_s.pop()
        return x
    def get_min(self):
        return self.min_s[-1]

Broadway

6. পোস্টফিক্স এক্সপ্রেশন ইভ্যালুয়েশন (Evaluate Postfix Expression)

গাণিতিক প্রকাশভঙ্গি যেমন: 2 3 * 5 + এর মান বের করা।

🛠 কর্মপদ্ধতি (Step-by-Step Logic)

1. স্ট্রিংটি বাম থেকে ডানদিকে ট্রাভার্স করুন।
2. যদি সংখ্যা হয়, স্ট্যাকে Push করুন।
3. যদি অপারেটর (+, -, *, /) হয়, তবে স্ট্যাক থেকে দুটি সংখ্যা Pop করুন, অপারেশনটি সম্পন্ন করুন এবং রেজাল্ট পুনরায় পুশ করুন।

---

7. ইনফিক্স থেকে পোস্টফিক্স (Infix to Postfix Conversion)

A + B কে A B + এ রূপান্তর করা। এই ক্ষেত্রে অপারেটরের প্রেসিডেন্স (Precedence) অনুযায়ী স্ট্যাক ব্যবহার করা হয়।

---

8. হিস্টোগ্রাম এরিয়া (Largest Rectangle in Histogram)

একটি বার চার্টে সবচেয়ে বড় আয়তক্ষেত্রের ক্ষেত্রফল বের করা।

🛠 কর্মপদ্ধতি (Step-by-Step Logic)

• প্রতিটি বারের জন্য তার বাম এবং ডানদিকের 'Smallest Element' খুঁজে বের করে এরিয়া ক্যালকুলেট করা হয়। এটি মোনোটোনিক স্ট্যাকের একটি জটিল কিন্তু কার্যকর ব্যবহার।

---

📊 কমপ্লেক্সিটি অ্যানালাইসিস (Complexity Analysis)

Problem	Time Complexity	Space Complexity
Balanced Parentheses	O(n)	O(n)
Next Greater Element	O(n)	O(n)
Min Stack	O(1) for min	O(n)
Postfix Evaluation	O(n)	O(n)

---

IMPORTANT

স্ট্যাক প্রবলেমগুলোর বেশিরভাগই O(n) সময়ে সমাধান করা সম্ভব, যা লিনিয়ার টাইম রেসপন্সের গ্যারান্টি দেয়।

---

TIP

Monotonic Stack টেকনিকটি নেক্সট গ্রেটার বা স্মলার এলিমেন্ট সংক্রান্ত প্রবলেমের জন্য একটি অত্যন্ত শক্তিশালী টুল।