23. Stack - Basics

Stack হলো একটি লিনিয়ার ডেটা স্ট্রাকচার যা একটি নির্দিষ্ট ক্রম মেনে চলে। এটি মূলত LIFO (Last In First Out) নীতিতে কাজ করে, অর্থাৎ যে এলিমেন্টটি সবার শেষে যোগ করা হয়, সেটি সবার আগে বের করা হয়।

---

1. Stack কি? (LIFO Principle)

স্ট্যাককে আপনি একটি প্লেটের স্তূপের সাথে তুলনা করতে পারেন। আপনি যখন নতুন প্লেট রাখেন, সেটি সবার উপরে রাখেন। আবার যখন প্লেট নিতে হয়, তখন সবার উপরের প্লেটটিই আগে নিতে হয়।

---

2. মূল অপারেশনসমূহ (Core Operations)

1. Push: স্ট্যাকে নতুন একটি এলিমেন্ট যোগ করা।
2. Pop: স্ট্যাকের সবার উপরের (Top) এলিমেন্টটি সরিয়ে ফেলা।
3. Peek / Top: স্ট্যাকের উপরের এলিমেন্টটি দেখা (না সরিয়ে)।
4. isEmpty: স্ট্যাক খালি কি না তা চেক করা।

---

3. অ্যারে দিয়ে ইমপ্লিমেন্টেশন (Array Implementation)

অ্যারে ব্যবহার করে স্ট্যাক তৈরি করলে একটি ফিক্সড সাইজ এবং top নামক একটি ভেরিয়েবল ব্যবহার করা হয়।

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

• Push: প্রথমে চেক করুন স্ট্যাক ফুল কি না। যদি না হয়, তবে top এক বাড়িয়ে সেই পজিশনে ডেটা রাখুন।
• Pop: চেক করুন স্ট্যাক খালি কি না। যদি না হয়, তবে top পজিশনের ডেটা রিটার্ন করে top এক কমিয়ে দিন।

Implementation

// Java Stack using Array
class Stack {
    int MAX = 1000;
    int top;
    int a[] = new int[MAX];
    Stack() { top = -1; }
    boolean push(int x) {
        if (top >= (MAX - 1)) return false;
        a[++top] = x;
        return true;
    }
    int pop() {
        if (top < 0) return 0;
        return a[top--];
    }
}

# Python Stack using List
class Stack:
    def __init__(self):
        self.stack = []
    def push(self, x):
        self.stack.append(x)
    def pop(self):
        if self.is_empty(): return None
        return self.stack.pop()
    def is_empty(self):
        return len(self.stack) == 0

---

4. লিঙ্কড লিস্ট দিয়ে ইমপ্লিমেন্টেশন (Linked List Implementation)

ডাইনামিক মেমরি ব্যবহারের জন্য লিঙ্কড লিস্ট স্ট্যাকের জন্য সেরা। এখানে প্রতিটি নতুন এলিমেন্ট লিঙ্কড লিস্টের Head হিসেবে যুক্ত হয়।

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

• Push: নতুন একটি নোড তৈরি করুন এবং তার next বর্তমান head-এ সেট করুন। এবার head-কে নতুন নোডে আপডেট করুন।
• Pop: বর্তমান head-কে সরিয়ে head.next-এ নিয়ে যান।

Implementation

// Java Stack using Linked List
class StackLL {
    Node top;
    class Node {
        int data;
        Node next;
        Node(int d) { data = d; }
    }
    public void push(int x) {
        Node newNode = new Node(x);
        newNode.next = top;
        top = newNode;
    }
    public int pop() {
        if (top == null) return -1;
        int res = top.data;
        top = top.next;
        return res;
    }
}

# Python Stack using Linked List
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Stack:
    def __init__(self):
        self.top = None
    def push(self, data):
        new_node = Node(data)
        new_node.next = self.top
        self.top = new_node
    def pop(self):
        if not self.top: return None
        res = self.top.data
        self.top = self.top.next
        return res

---

5. স্ট্যাক ওভারফ্লো এবং আন্ডারফ্লো (Overflow & Underflow)

• Stack Overflow: যখন স্ট্যাক ফুল থাকা সত্ত্বেও নতুন ডেটা পুশ (Push) করার চেষ্টা করা হয়।
• Stack Underflow: যখন স্ট্যাক খালি থাকা সত্ত্বেও কোনো ডেটা পপ (Pop) করার চেষ্টা করা হয়।

---

6. স্ট্যাকের ব্যবহার (Applications of Stack)

• Undo/Redo: এডিটর বা সফটওয়্যারে কাজ আগের অবস্থায় ফিরিয়ে নিতে।
• Function Calls: প্রোগ্রামিং ল্যাঙ্গুয়েজে রিকার্সন বা ফাংশন কল ম্যানেজ করতে (Call Stack)।
• Expression Parsing: গাণিতিক সমীকরণ (Infix to Postfix) সমাধান করতে।
• Browser History: ব্যাকে যাওয়ার সময় আগের ইউআরএল পেতে।

---

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

Operation	Time Complexity
Push	O(1)
Pop	O(1)
Peek	O(1)
Search	O(n)

---

IMPORTANT

স্ট্যাকের সব মূল অপারেশন (Push/Pop/Peek) সবসময় O(1) সময়ে সম্পন্ন হয়, যা একে পারফরম্যান্সের দিক থেকে খুব শক্তিশালী করে তোলে।

---

TIP

যখন আপনি জানেন না স্ট্যাকে ঠিক কত ডেটা আসবে, তখন Linked List Implementation বেছে নেওয়া বুদ্ধিমানের কাজ।