স্ট্যাক (Stack) গাইড ও নোট

স্ট্যাক (Stack) একটি LIFO (Last In First Out) ডেটা স্ট্রাকচার, যা তার উপাদানগুলির অ্যাক্সেসের জন্য একটি নির্দিষ্ট পদ্ধতি অনুসরণ করে। স্ট্যাকের মধ্যে, সর্বশেষ ইনসার্ট করা উপাদানটি প্রথমে অ্যাক্সেস করা হয়। এটি এক ধরনের ধাপের কাঠামো, যেখানে উপাদানগুলি একে একে স্ট্যাকে রাখা হয় এবং সেগুলি pop বা push অপারেশন এর মাধ্যমে বের করা হয়।

স্ট্যাকের বৈশিষ্ট্যসমূহ

1. LIFO (Last In First Out): এর মানে হলো, সর্বশেষ ইনসার্ট করা উপাদানটি প্রথমে বের হবে।
2. Push: স্ট্যাকে একটি নতুন উপাদান যোগ করা।
3. Pop: স্ট্যাক থেকে উপাদান বের করা।
4. Peek: স্ট্যাকে সর্বশেষ যোগ করা উপাদানটি দেখতে পাওয়া, তবে তা সরানো হয় না।
5. IsEmpty: স্ট্যাকটি খালি কিনা তা পরীক্ষা করা।

স্ট্যাক ব্যবহৃত হয় বিভিন্ন সমস্যা সমাধানে, যেমন ফাংশন কল স্ট্যাক, অব্যাহত ইভেন্ট সিস্টেম, অ্যাওয়ে অভ্যন্তরীণ কার্যক্রম, ব্যাকট্র্যাকিং সমস্যা, ইত্যাদি।

1. স্ট্যাকের অপারেশনসমূহ

স্ট্যাকের মৌলিক অপারেশনগুলি হলো:

• Push: একটি উপাদান স্ট্যাকে যোগ করা।
• Pop: স্ট্যাকের শীর্ষ উপাদানটি সরানো এবং তা ফেরত দেওয়া।
• Peek: স্ট্যাকের শীর্ষ উপাদানটি দেখানো, কিন্তু সরানো না।
• IsEmpty: স্ট্যাক খালি কিনা তা চেক করা।

2. স্ট্যাক তৈরি এবং ব্যবহার (Java)

Java তে স্ট্যাক তৈরি করতে আমরা java.util.Stack ক্লাস ব্যবহার করতে পারি। তবে, যদি আমাদের নিজস্ব স্ট্যাক তৈরি করতে হয়, তবে Array বা Linked List ব্যবহার করা যেতে পারে।

Java এর Built-in Stack Class ব্যবহার:

import java.util.Stack;

public class StackExample {

    public static void main(String[] args) {
        // Stack তৈরি
        Stack<Integer> stack = new Stack<>();

        // Push অপারেশন
        stack.push(10);
        stack.push(20);
        stack.push(30);

        // Peek অপারেশন
        System.out.println("Top element: " + stack.peek());

        // Pop অপারেশন
        System.out.println("Popped element: " + stack.pop());

        // IsEmpty অপারেশন
        System.out.println("Is stack empty? " + stack.isEmpty());

        // Stacked elements
        System.out.println("Stacked elements:");
        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }
}

ব্যাখ্যা:

• push(): এটি একটি নতুন উপাদান স্ট্যাকে যোগ করে।
• peek(): এটি স্ট্যাকের শীর্ষ উপাদানটি দেখায় কিন্তু তা সরায় না।
• pop(): এটি স্ট্যাকের শীর্ষ উপাদানটি সরায় এবং তা রিটার্ন করে।
• isEmpty(): এটি চেক করে স্ট্যাকটি খালি কিনা।

আউটপুট:

Top element: 30
Popped element: 30
Is stack empty? false
Stacked elements:
20
10

3. কাস্টম স্ট্যাক (Custom Stack) ক্লাস তৈরি করা

Java তে নিজস্ব Stack ক্লাস তৈরি করার জন্য, আমরা একটি Array বা Linked List ব্যবহার করতে পারি। এখানে একটি Array-based Stack এর উদাহরণ দেয়া হলো।

public class CustomStack {

    private int[] stackArray;
    private int top;
    private int capacity;

    // Constructor to initialize the stack
    public CustomStack(int size) {
        capacity = size;
        stackArray = new int[capacity];
        top = -1;  // Stack is initially empty
    }

    // Push operation
    public void push(int element) {
        if (top == capacity - 1) {
            System.out.println("Stack Overflow");
        } else {
            stackArray[++top] = element;
            System.out.println("Pushed " + element);
        }
    }

    // Pop operation
    public int pop() {
        if (top == -1) {
            System.out.println("Stack Underflow");
            return -1;
        } else {
            return stackArray[top--];
        }
    }

    // Peek operation
    public int peek() {
        if (top == -1) {
            System.out.println("Stack is empty");
            return -1;
        } else {
            return stackArray[top];
        }
    }

    // Check if the stack is empty
    public boolean isEmpty() {
        return top == -1;
    }

    // Size of the stack
    public int size() {
        return top + 1;
    }

    // Main method to test the custom stack
    public static void main(String[] args) {
        CustomStack stack = new CustomStack(5);
        
        stack.push(10);
        stack.push(20);
        stack.push(30);
        
        System.out.println("Peek: " + stack.peek());
        
        System.out.println("Popped element: " + stack.pop());
        System.out.println("Size of stack: " + stack.size());

        System.out.println("Is the stack empty? " + stack.isEmpty());
    }
}

ব্যাখ্যা:

• CustomStack ক্লাসে আমরা একটি Array ব্যবহার করেছি স্ট্যাক তৈরি করার জন্য।
• push(), pop(), peek() এবং isEmpty() অপারেশনগুলি স্বতন্ত্রভাবে সংজ্ঞায়িত করা হয়েছে।

আউটপুট:

Pushed 10
Pushed 20
Pushed 30
Peek: 30
Popped element: 30
Size of stack: 2
Is the stack empty? false

4. স্ট্যাকের কিছু গুরুত্বপূর্ণ ব্যবহার

স্ট্যাক ব্যবহার করা হয় অনেক ক্ষেত্রে যেমন:

ফাংশন কল স্ট্যাক (Function Call Stack)

স্ট্যাকের সবচেয়ে সাধারণ ব্যবহার হল function call stack-এ, যেখানে recursive function calls ট্র্যাক করা হয়।

অ্যাওয়ে (Backtracking)

অনেক অ্যালগরিদম যেমন N-Queens, Maze Solver, Sudoku Solver ইত্যাদি Backtracking পদ্ধতি ব্যবহার করে, যেখানে স্ট্যাক ব্যবহৃত হয় স্থানীয় সিদ্ধান্তগুলি ট্র্যাক করতে।

অ্যাঙ্গুলার/রিয়্যাক্ট (Undo/Redo)

অ্যাঙ্গুলার, রিয়্যাক্ট বা অন্য ফ্রেমওয়ার্কে Undo/Redo অপারেশন করার জন্য স্ট্যাক ব্যবহৃত হয়। ব্যবহারকারী কোনো পরিবর্তন করার পর, সেই পরিবর্তন স্ট্যাকে সংরক্ষণ করা হয় এবং Undo অপারেশনের মাধ্যমে আগের অবস্থায় ফিরে যাওয়া সম্ভব হয়।

প্রিন্টার (Expression Evaluation)

স্ট্যাককে prefix, infix, এবং postfix এক্সপ্রেশন সমাধান এবং মূল্যায়নের জন্য ব্যবহার করা হয়।

5. স্ট্যাক সম্পর্কিত অ্যালগরিদম

স্ট্যাকের সাহায্যে ইনফিক্স এক্সপ্রেশন থেকে পোস্টফিক্স এক্সপ্রেশন কনভার্ট করা:

এটি একটি সাধারণ স্ট্যাক ব্যবহারকারী অ্যালগরিদম। ইনফিক্স এক্সপ্রেশন যেমন (A + B) * C কে পোস্টফিক্স এক্সপ্রেশন **A B + C *** এ রূপান্তরিত করা যায়।

import java.util.Stack;

public class InfixToPostfix {

    // Function to check if character is an operator
    public static boolean isOperator(char c) {
        return (c == '+' || c == '-' || c == '*' || c == '/');
    }

    // Function to convert infix to postfix
    public static String infixToPostfix(String infix) {
        Stack<Character> stack = new Stack<>();
        StringBuilder result = new StringBuilder();
        
        for (char c : infix.toCharArray()) {
            if (Character.isLetterOrDigit(c)) {
                result.append(c);
            } else if (isOperator(c)) {
                while (!stack.isEmpty() && precedence(c) <= precedence(stack.peek())) {
                    result.append(stack.pop());
                }
                stack.push(c);
            }
        }
        
        while (!stack.isEmpty()) {
            result.append(stack.pop());
        }

        return result.toString();
    }

    // Function to return precedence of operators
    public static int precedence(char c) {
        if (c == '+' || c == '-') {
            return 1;
        }
        if (c == '*' || c == '/') {
            return 2;
        }
        return -1;
    }

    public static void main(String[] args) {
        String infix = "A+B*C-D";
        System.out.println("Postfix: " + infixToPostfix(infix));
    }
}

আউটপুট:

Postfix: ABC*+D-

সারাংশ

স্ট্যাক (Stack) হল একটি LIFO (Last In, First Out) ডেটা স্ট্রাকচার যা Java এ খুবই সাধারণভাবে ব্যবহৃত হয়। এটি বিভিন্ন সমস্যার সমাধান যেমন undo/redo, expression evaluation, function call stack, এবং backtracking-এ ব্যবহৃত হয়। Java তে Stack ক্লাস অথবা কাস্টম স্ট্যাক তৈরি করে বিভিন্ন অপারেশন যেমন push, pop, peek, এবং isEmpty সহজে বাস্তবায়ন করা যায়।

Stack (স্ট্যাক) হল একটি ডেটা স্ট্রাকচার যা Last In, First Out (LIFO) নীতি অনুসরণ করে। এর মানে হল যে, স্ট্যাকের মধ্যে সবচেয়ে শেষের আইটেমটি প্রথমে বের হয়ে আসে। স্ট্যাক এমন একটি তালিকা যেখানে শুধুমাত্র একটিমাত্র প্রান্তে ডেটা ইনসার্ট (Push) এবং ডেটা রিমুভ (Pop) করা সম্ভব, অন্য কোন প্রান্তে অপারেশন সম্ভব নয়। স্ট্যাকের ব্যবহার অনেক ক্ষেত্রেই কার্যকর, যেমন রিকার্সন (recursion), এক্সপ্রেশন ইভ্যালুয়েশন, ব্যাকট্র্যাকিং ইত্যাদি।

Stack এর ধারণা

স্ট্যাক একটি লিনিয়ার ডেটা স্ট্রাকচার যা একে একে উপাদান সংরক্ষণ করে, কিন্তু ডেটার অ্যাক্সেস শুধুমাত্র এক প্রান্ত থেকে হতে পারে। স্ট্যাকের দুটি প্রধান অপারেশন রয়েছে:

1. Push (পুশ): নতুন উপাদান স্ট্যাকের উপরে যোগ করা।
2. Pop (পপ): স্ট্যাকের শীর্ষ থেকে উপাদান মুছে ফেলা এবং বের করা।

স্ট্যাকের মধ্যে সাধারণত আরও দুটি অ্যাক্সেসযোগ্য অপারেশন থাকে:

• Peek (পীক): স্ট্যাকের শীর্ষে থাকা উপাদান দেখা, তবে এটি মুছে ফেলা হয় না।
• IsEmpty (ইজএম্পটি): স্ট্যাকটি খালি কি না তা পরীক্ষা করা।

স্ট্যাকের কাজের নীতি Last In, First Out (LIFO), যা এর নামের সাথে মেলে। উদাহরণস্বরূপ, একটি পুস্তক স্ট্যাকের মধ্যে যদি ৩টি বই রাখা হয়, তবে সর্বশেষে রাখা বইটি প্রথমে উঠানো হবে।

Stack এর ব্যবহার

স্ট্যাকের অনেকগুলি বাস্তব জীবনের ব্যবহার রয়েছে, যেগুলি বিভিন্ন ক্ষেত্রে গুরুত্বপূর্ণ। এখানে কিছু উদাহরণ দেওয়া হলো:

1. রিকার্সন (Recursion)

স্ট্যাক সাধারণত রিকার্সন ফাংশন কলের জন্য ব্যবহৃত হয়। যখন একটি ফাংশন পুনরায় নিজেকে কল করে, তখন সিস্টেম স্ট্যাক ব্যবহার করে তার কলগুলির সারণী তৈরি করে।

উদাহরণ:

public class RecursionExample {

    public static void recursiveFunction(int n) {
        if (n == 0) return;
        System.out.println(n);
        recursiveFunction(n - 1); // Recursive call
    }

    public static void main(String[] args) {
        recursiveFunction(5); // আউটপুট হবে 5, 4, 3, 2, 1
    }
}

2. ব্যাকট্র্যাকিং (Backtracking)

ব্যাকট্র্যাকিং অ্যালগরিদমে স্ট্যাক ব্যবহৃত হয় বিভিন্ন বিকল্প পছন্দের উপর পরীক্ষা-নিরীক্ষা করার জন্য। এটি সাধারণত পাজল সলভিং, ম্যাজিক সিউব ইত্যাদি ক্ষেত্রে ব্যবহৃত হয়।

3. এক্সপ্রেশন ইভ্যালুয়েশন (Expression Evaluation)

স্ট্যাক ব্যবহৃত হয় এক্সপ্রেশন যেমন ইনফিক্স (Infix), পোস্টফিক্স (Postfix), এবং প্রিফিক্স (Prefix) এক্সপ্রেশন গুলি ইভ্যালুয়েট করার জন্য।

4. ইউজার ইনপুট হ্যান্ডলিং

অনেক অ্যাপ্লিকেশন যেমন ব্রাউজার বা টেক্সট এডিটরে, ব্যবহারকারীর আগের ইনপুট বা কর্মকাণ্ড সঠিকভাবে ট্র্যাক করতে স্ট্যাক ব্যবহার করা হয়, যাতে সহজে ফিরে আসা যায়।

Stack এর জাভা ইমপ্লিমেন্টেশন

জাভায় স্ট্যাক ইমপ্লিমেন্ট করতে আমরা সাধারণত java.util.Stack ক্লাস ব্যবহার করি। এটি স্ট্যাকের কার্যকারিতা প্রদান করে যেমন push(), pop(), peek(), isEmpty() ইত্যাদি।

উদাহরণ:

import java.util.Stack;

public class StackExample {

    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();

        // Push operation
        stack.push(10);
        stack.push(20);
        stack.push(30);

        // Pop operation
        System.out.println("Popped element: " + stack.pop()); // আউটপুট হবে 30

        // Peek operation
        System.out.println("Top element: " + stack.peek()); // আউটপুট হবে 20

        // Check if stack is empty
        System.out.println("Is stack empty? " + stack.isEmpty()); // আউটপুট হবে false
    }
}

এখানে:

• push() স্ট্যাকের শীর্ষে একটি নতুন উপাদান যোগ করে।
• pop() শীর্ষের উপাদানটি মুছে ফেলে এবং সেটি রিটার্ন করে।
• peek() শুধুমাত্র শীর্ষের উপাদানটি রিটার্ন করে, কিন্তু তা মুছে ফেলে না।
• isEmpty() স্ট্যাকটি খালি কিনা তা পরীক্ষা করে।

সারাংশ

স্ট্যাক একটি অত্যন্ত গুরুত্বপূর্ণ ডেটা স্ট্রাকচার যা Last In, First Out (LIFO) নীতি অনুসরণ করে। এটি ব্যবহৃত হয় রিকার্সন, ব্যাকট্র্যাকিং, এক্সপ্রেশন ইভ্যালুয়েশন এবং অনেক ধরনের সিস্টেম অপারেশনে। জাভায় স্ট্যাকের জন্য Stack ক্লাস প্রদান করা হয়েছে, যা ইনবিল্ট ফাংশনালিটি দিয়ে স্ট্যাকের বিভিন্ন অপারেশন যেমন push(), pop(), peek(), isEmpty() ইত্যাদি সহজে ব্যবহার করতে সাহায্য করে। স্ট্যাকের কার্যকারিতা এবং ব্যবহার বিভিন্ন বাস্তব জীবনের সমস্যাগুলির সমাধানে অত্যন্ত গুরুত্বপূর্ণ ভূমিকা পালন করে।

Stack (স্ট্যাক) হল একটি LIFO (Last In, First Out) ডেটা স্ট্রাকচার, যার মানে হলো, যেই উপাদানটি সর্বশেষ অ্যাড করা হয়েছে, সেটিই প্রথমে আউট হবে। এটি সাধারণত Push (এlement যোগ করা) এবং Pop (এlement অপসারণ) অপারেশন দ্বারা পরিচালিত হয়। স্ট্যাকের অন্য একটি সাধারণ অপারেশন হল Peek, যা স্ট্যাকের উপরের উপাদানকে দেখতে দেয় কিন্তু অপসারণ করে না।

এখানে, আমরা দেখব Array এবং Linked List ব্যবহার করে স্ট্যাক কিভাবে ইমপ্লিমেন্ট করা যায়।

১. Array ব্যবহার করে Stack ইমপ্লিমেন্টেশন

Stack Class Definition

এখানে, আমরা একটি স্ট্যাক ইমপ্লিমেন্ট করবো যা অ্যারে ব্যবহার করে উপাদান সংরক্ষণ করবে। অ্যারের আকার স্থির হওয়ায়, আমরা উপাদানগুলি অ্যারে দ্বারা পরিচালনা করব এবং কিছু ম্যানুয়ালি ফাংশন তৈরি করব যেমন Push, Pop, Peek, এবং isEmpty।

public class StackUsingArray {
    private int maxSize;     // Stack এর সর্বোচ্চ সাইজ
    private int top;         // Stack এর টপ ইনডেক্স
    private int[] stackArray; // Stack এর জন্য অ্যারে

    // Stack Constructor
    public StackUsingArray(int size) {
        maxSize = size;
        stackArray = new int[maxSize];
        top = -1;  // Stack শূন্য হলে top হবে -1
    }

    // Push Operation: Stack এ নতুন উপাদান যোগ করা
    public void push(int value) {
        if (top < maxSize - 1) {
            stackArray[++top] = value;
            System.out.println(value + " pushed to stack");
        } else {
            System.out.println("Stack is full");
        }
    }

    // Pop Operation: Stack থেকে উপাদান মুছে ফেলা
    public int pop() {
        if (top >= 0) {
            int poppedValue = stackArray[top--];
            System.out.println(poppedValue + " popped from stack");
            return poppedValue;
        } else {
            System.out.println("Stack is empty");
            return -1;  // -1 Return করলে বোঝাবে Stack খালি
        }
    }

    // Peek Operation: Stack এর শীর্ষ উপাদান দেখানো
    public int peek() {
        if (top >= 0) {
            return stackArray[top];
        } else {
            System.out.println("Stack is empty");
            return -1;  // Stack খালি হলে -1 Return হবে
        }
    }

    // isEmpty Operation: Stack খালি কিনা পরীক্ষা করা
    public boolean isEmpty() {
        return top == -1;
    }

    // Stack এর সাইজ জানা
    public int size() {
        return top + 1;
    }
}

Main Method Example

public class Main {
    public static void main(String[] args) {
        StackUsingArray stack = new StackUsingArray(5); // Stack সাইজ 5

        stack.push(10);
        stack.push(20);
        stack.push(30);

        System.out.println("Top element is " + stack.peek());

        stack.pop();

        System.out.println("Top element is " + stack.peek());

        stack.pop();
        stack.pop();

        System.out.println("Stack empty: " + stack.isEmpty());
    }
}

আউটপুট:

10 pushed to stack
20 pushed to stack
30 pushed to stack
Top element is 30
30 popped from stack
Top element is 20
20 popped from stack
10 popped from stack
Stack empty: true

২. Linked List ব্যবহার করে Stack ইমপ্লিমেন্টেশন

এখন আমরা Linked List ব্যবহার করে স্ট্যাক ইমপ্লিমেন্ট করব। যেখানে, Node ক্লাস ব্যবহার করে স্ট্যাকের উপাদানগুলো সংরক্ষণ করা হবে, এবং Stack ক্লাসে push, pop, peek, এবং isEmpty অপারেশনগুলোর মাধ্যমে স্ট্যাক পরিচালিত হবে।

Node Class Definition

class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

StackUsingLinkedList Class

public class StackUsingLinkedList {
    private Node top;  // Stack এর টপ নোড

    // Constructor: Stack ইন্সট্যান্সিয়েট করা
    public StackUsingLinkedList() {
        top = null;
    }

    // Push Operation: Stack এ নতুন উপাদান যোগ করা
    public void push(int value) {
        Node newNode = new Node(value);  // নতুন নোড তৈরি করা
        newNode.next = top;              // নতুন নোডের পরবর্তী পয়েন্টার পুরনো টপে পয়েন্ট করছে
        top = newNode;                   // টপ পয়েন্ট করছে নতুন নোডে
        System.out.println(value + " pushed to stack");
    }

    // Pop Operation: Stack থেকে উপাদান মুছে ফেলা
    public int pop() {
        if (top != null) {
            int poppedValue = top.data;
            top = top.next;  // টপ পরবর্তী নোডে পয়েন্ট করছে
            System.out.println(poppedValue + " popped from stack");
            return poppedValue;
        } else {
            System.out.println("Stack is empty");
            return -1;  // Stack খালি হলে -1 Return হবে
        }
    }

    // Peek Operation: Stack এর শীর্ষ উপাদান দেখানো
    public int peek() {
        if (top != null) {
            return top.data;
        } else {
            System.out.println("Stack is empty");
            return -1;  // Stack খালি হলে -1 Return হবে
        }
    }

    // isEmpty Operation: Stack খালি কিনা পরীক্ষা করা
    public boolean isEmpty() {
        return top == null;
    }

    // Stack এর সাইজ জানা
    public int size() {
        int count = 0;
        Node temp = top;
        while (temp != null) {
            count++;
            temp = temp.next;
        }
        return count;
    }
}

Main Method Example

public class Main {
    public static void main(String[] args) {
        StackUsingLinkedList stack = new StackUsingLinkedList();

        stack.push(10);
        stack.push(20);
        stack.push(30);

        System.out.println("Top element is " + stack.peek());

        stack.pop();

        System.out.println("Top element is " + stack.peek());

        stack.pop();
        stack.pop();

        System.out.println("Stack empty: " + stack.isEmpty());
    }
}

আউটপুট:

10 pushed to stack
20 pushed to stack
30 pushed to stack
Top element is 30
30 popped from stack
Top element is 20
20 popped from stack
10 popped from stack
Stack empty: true

সারাংশ

• Array-based Stack: একটি স্ট্যাটিক (স্থির আকারের) স্ট্যাক তৈরি করার জন্য অ্যারে ব্যবহার করা হয়। এটি সাধারণত ছোট অ্যারে সাইজ এবং যখন জানি যে ডেটার সংখ্যা পূর্বনির্ধারিত থাকে তখন উপযুক্ত।
• Linked List-based Stack: এই স্ট্যাকটি ডাইনামিক এবং সহজে বাড়ানো বা ছোট করা যায়। এখানে, প্রতিটি উপাদান একটি লিংকড লিস্টের নোড হিসেবে সংরক্ষিত হয়, যা ডেটা এবং পরবর্তী নোডের রেফারেন্স ধারণ করে।

স্ট্যাক ব্যবহার করা হয় অনেক জটিল সমস্যা সমাধানে, যেমন:

• Function Calls: ফাংশন কল করার জন্য স্ট্যাক ব্যবহার হয়।
• Undo Mechanism: ইউজার ইনপুটের Undo করার জন্য স্ট্যাক ব্যবহার হয়।
• Expression Evaluation: ইনফিক্স, পোস্টফিক্স, এবং প্রিফিক্স এক্সপ্রেশনের মূল্য নির্ধারণে স্ট্যাক ব্যবহৃত হয়।

অ্যারে বা লিংকড লিস্ট ব্যবহার করে স্ট্যাক ইমপ্লিমেন্টেশন করতে আপনি সমস্যা অনুযায়ী যেকোনো একটি পদ্ধতি নির্বাচন করতে পারেন।

Stack হল একটি linear data structure যা Last In, First Out (LIFO) (শেষে প্রবেশ, প্রথমে প্রস্থান) পদ্ধতির মাধ্যমে কাজ করে। অর্থাৎ, স্ট্যাকের শীর্ষে যে উপাদানটি প্রবেশ করে, সেটি প্রথমে বের করা হয়। স্ট্যাক সাধারণত তিনটি মৌলিক অপারেশন সমর্থন করে:

1. Push: একটি নতুন উপাদান স্ট্যাকে প্রবেশ করানো।
2. Pop: স্ট্যাকের শীর্ষ উপাদানটি বের করা (অথবা অপসারণ করা)।
3. Peek: স্ট্যাকের শীর্ষ উপাদানটি দেখতে পাওয়া, তবে এটি অপসারিত হয় না।

স্ট্যাকের এই তিনটি মৌলিক অপারেশন কিভাবে জাভায় বাস্তবায়িত করা যায়, তা দেখে নেওয়া যাক।

১. Stack Class in Java

জাভাতে, Stack ডেটা স্ট্রাকচারটি java.util.Stack ক্লাসের মাধ্যমে সরবরাহ করা হয়। তবে, Stack একটি অবলুপ্ত ক্লাস (legacy class) হিসেবে বিবেচিত, এবং নতুন অ্যাপ্লিকেশনগুলির জন্য Deque অথবা ArrayDeque ব্যবহারের পরামর্শ দেওয়া হয়, কারণ এগুলো স্ট্যাকের মত কার্যকারিতা সরবরাহ করে এবং আরও কার্যকরী।

তবে, Stack ক্লাসটি এখনও ব্যবহারযোগ্য এবং এতে push(), pop(), peek() সহ স্ট্যাক অপারেশনগুলো সহজে ব্যবহার করা যায়।

২. Stack Operations in Java

এখানে আমরা Stack ক্লাস ব্যবহার করে Push, Pop, এবং Peek অপারেশনগুলো দেখব।

উদাহরণ: Stack Operations (Push, Pop, Peek)

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        // Stack তৈরি করা
        Stack<Integer> stack = new Stack<>();

        // Push অপারেশন
        stack.push(10);
        stack.push(20);
        stack.push(30);
        stack.push(40);

        // Stack এর বর্তমান অবস্থা
        System.out.println("Stack after push operations: " + stack);

        // Peek অপারেশন
        System.out.println("Top element using peek: " + stack.peek()); // 40

        // Pop অপারেশন
        System.out.println("Element popped: " + stack.pop()); // 40
        System.out.println("Stack after pop operation: " + stack);

        // আরও একটি pop অপারেশন
        System.out.println("Element popped: " + stack.pop()); // 30
        System.out.println("Stack after pop operation: " + stack);
    }
}

ব্যাখ্যা:

1. Push Operation: stack.push() মেথড ব্যবহার করে নতুন উপাদান স্ট্যাকে যোগ করা হয়। এখানে ১০, ২০, ৩০, এবং ৪০ এই মানগুলো স্ট্যাকে যোগ করা হয়েছে।
2. Peek Operation: stack.peek() মেথড ব্যবহার করে স্ট্যাকের শীর্ষ উপাদানটি দেখা যায়, কিন্তু এটি স্ট্যাক থেকে সরানো হয় না। এখানে, peek() ৪০ ফেরত দেবে কারণ এটি শীর্ষে রয়েছে।
3. Pop Operation: stack.pop() মেথড ব্যবহার করে শীর্ষ উপাদানটি সরানো হয় এবং তা রিটার্ন করা হয়। প্রথমে ৪০ সরানো হয় এবং তারপর ৩০ সরানো হয়।

আউটপুট:

Stack after push operations: [10, 20, 30, 40]
Top element using peek: 40
Element popped: 40
Stack after pop operation: [10, 20, 30]
Element popped: 30
Stack after pop operation: [10, 20]

৩. Stack Operations' Complexity

• Push: প্রতি push() অপারেশন O(1) সময়ে সম্পন্ন হয়। এর মানে, নতুন উপাদান স্ট্যাকে যোগ করতে সময় লাগবে না, যতটুকু জায়গা পাওয়া যায়।
• Pop: প্রতি pop() অপারেশন O(1) সময়ে সম্পন্ন হয়। এটি শীর্ষ উপাদানটি অপসারণ করে এবং সেই উপাদানকে রিটার্ন করে।
• Peek: প্রতি peek() অপারেশন O(1) সময়ে সম্পন্ন হয়। এটি শীর্ষ উপাদানটি শুধুমাত্র দেখতে দেয়, তবে সেটি অপসারিত হয় না।

৪. Stack এর ব্যবহার

Stack বিভিন্ন প্রোগ্রামিং পরিস্থিতিতে ব্যবহার করা হয়, যেমন:

1. Function Call Stack: যখন একটি ফাংশন কল করা হয়, তখন এটি একটি স্ট্যাক হিসেবে কাজ করে এবং প্রতিটি কল একটি নতুন ফ্রেম হিসাবে স্ট্যাকে প্রবেশ করে। ফাংশন শেষ হলে স্ট্যাক থেকে তা সরানো হয়।
2. Undo Operations: একটি অ্যাপ্লিকেশনে undo ফিচারের জন্য স্ট্যাক ব্যবহার করা হয়। ব্যবহারকারী শেষ যে কার্যক্রমটি করেছে, তা স্ট্যাকে প্রবেশ করে এবং undo করার জন্য স্ট্যাক থেকে অপসারিত হয়।
3. Expression Evaluation: স্ট্যাক গণনা এবং এক্সপ্রেশন প্রক্রিয়াকরণের জন্য ব্যবহার করা হয়, বিশেষ করে infix, prefix, এবং postfix এক্সপ্রেশন সমাধান করতে।
4. Depth First Search (DFS): গাছ বা গ্রাফের গহীর অনুসন্ধানের জন্য DFS অ্যালগরিদমে স্ট্যাক ব্যবহৃত হয়।

৫. Stack using Linked List (Custom Implementation)

যদিও Stack ক্লাস জাভাতে সহজেই ব্যবহৃত হয়, তবে আপনি যদি নিজস্ব স্ট্যাক ইমপ্লিমেন্টেশন করতে চান, তবে Linked List ব্যবহার করা যেতে পারে। এখানে একটি কাস্টম স্ট্যাক ইমপ্লিমেন্টেশন দেওয়া হল যা LinkedList ব্যবহার করে তৈরি করা হয়েছে:

class StackUsingLinkedList {
    private class Node {
        int data;
        Node next;
        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    private Node top;

    public StackUsingLinkedList() {
        top = null;
    }

    // Push operation
    public void push(int data) {
        Node newNode = new Node(data);
        newNode.next = top;
        top = newNode;
    }

    // Pop operation
    public int pop() {
        if (top == null) {
            System.out.println("Stack is empty!");
            return -1;
        }
        int popped = top.data;
        top = top.next;
        return popped;
    }

    // Peek operation
    public int peek() {
        if (top == null) {
            System.out.println("Stack is empty!");
            return -1;
        }
        return top.data;
    }

    public boolean isEmpty() {
        return top == null;
    }
}

public class CustomStackExample {
    public static void main(String[] args) {
        StackUsingLinkedList stack = new StackUsingLinkedList();

        stack.push(10);
        stack.push(20);
        stack.push(30);

        System.out.println("Top element: " + stack.peek());  // 30
        System.out.println("Popped element: " + stack.pop()); // 30
        System.out.println("Popped element: " + stack.pop()); // 20
    }
}

ব্যাখ্যা:

• Node Class: একটি Node ক্লাস তৈরি করা হয়েছে যা স্ট্যাকের প্রতিটি উপাদান ধারণ করবে এবং পরবর্তী নোডের সাথে সংযুক্ত থাকবে।
• Push: নতুন নোড তৈরি করা হয় এবং সেটি স্ট্যাকের শীর্ষে যুক্ত করা হয়।
• Pop: শীর্ষ নোড থেকে ডেটা নিয়ে তা সরানো হয়।
• Peek: শীর্ষ নোডের ডেটা দেখা হয়, কিন্তু সরানো হয় না।

সারাংশ

Stack হল একটি গুরুত্বপূর্ণ ডেটা স্ট্রাকচার যা LIFO (Last In First Out) পদ্ধতির মাধ্যমে কাজ করে। এর তিনটি মৌলিক অপারেশন হল Push, Pop, এবং Peek। জাভাতে Stack ক্লাস ব্যবহার করে সহজেই এই অপারেশনগুলি সম্পাদন করা যায়। তাছাড়া, আপনি যদি কাস্টম স্ট্যাক ইমপ্লিমেন্ট করতে চান, তবে Linked List ব্যবহার করে নিজে স্ট্যাক তৈরি করতে পারেন। স্ট্যাকের এই অপারেশনগুলি বিভিন্ন সমস্যা সমাধানে যেমন function calls, undo operations, DFS ইত্যাদিতে ব্যবহার করা হয়।

Stack হল একটি লিনিয়ার ডাটা স্ট্রাকচার যা LIFO (Last In First Out) ভিত্তিতে কাজ করে। অর্থাৎ, একটি উপাদান স্ট্যাকের শীর্ষে (top) যুক্ত হলে, প্রথমে সেই উপাদানটি বের করা হয়। স্ট্যাকের প্রধান অপারেশনগুলির মধ্যে রয়েছে push(), pop(), peek() এবং isEmpty()। স্ট্যাক অনেক ধরনের সমস্যার সমাধানে ব্যবহার করা হয়, যেমন Balanced Parentheses Checking এবং Infix to Postfix Conversion।

এই টিউটোরিয়ালে, আমরা দুটি জনপ্রিয় স্ট্যাক সমস্যার সমাধান দেখব:

1. Balanced Parentheses Checking
2. Infix to Postfix Conversion

1. Balanced Parentheses Checking

Balanced Parentheses Checking সমস্যা হল, একটি স্ট্রিংয়ের মধ্যে সমস্ত বন্ধনী সঠিকভাবে বন্ধ হয়েছে কিনা তা পরীক্ষা করা। উদাহরণস্বরূপ, "()", "(())", এবং "({[]})" এগুলি সঠিকভাবে বন্ধনীবদ্ধ স্ট্রিং, তবে "(()" এবং ")(" এর মধ্যে সঠিকভাবে বন্ধনী নেই।

উদাহরণ: Balanced Parentheses Checking

import java.util.Stack;

public class BalancedParentheses {
    public static void main(String[] args) {
        String expression = "{[()]}";
        if (isBalanced(expression)) {
            System.out.println("The parentheses are balanced.");
        } else {
            System.out.println("The parentheses are not balanced.");
        }
    }

    // Function to check if parentheses are balanced
    public static boolean isBalanced(String expression) {
        Stack<Character> stack = new Stack<>();

        // Iterate through the expression
        for (char ch : expression.toCharArray()) {
            if (ch == '(' || ch == '{' || ch == '[') {
                stack.push(ch);  // Push opening brackets onto the stack
            } else if (ch == ')' || ch == '}' || ch == ']') {
                // Check if stack is empty or if the top doesn't match
                if (stack.isEmpty()) {
                    return false;  // Closing bracket without matching opening bracket
                }
                char top = stack.pop();
                if (!isMatchingPair(top, ch)) {
                    return false;  // Mismatched parentheses
                }
            }
        }
        return stack.isEmpty();  // If stack is empty, parentheses are balanced
    }

    // Helper function to check if the pair of parentheses is valid
    public static boolean isMatchingPair(char opening, char closing) {
        return (opening == '(' && closing == ')') || 
               (opening == '{' && closing == '}') || 
               (opening == '[' && closing == ']');
    }
}

ব্যাখ্যা:

1. Stack ব্যবহার করে প্রতিটি ওপেনিং প্যারেন্টেসিস যেমন (, {, [ স্ট্যাকে পুশ করা হয়।
2. প্রতিটি ক্লোজিং প্যারেন্টেসিস যেমন ), }, ] পাওয়া গেলে, স্ট্যাক থেকে একটি এলিমেন্ট পপ করা হয় এবং এটি চেক করা হয় যে এটি সঠিক ওপেনিং প্যারেন্টেসিসের সাথে মেলে কি না।
3. শেষে, স্ট্যাক যদি খালি থাকে, তবে স্ট্রিংটি balanced এবং যদি না থাকে, তবে এটি unbalanced।

আউটপুট:

The parentheses are balanced.

2. Infix to Postfix Conversion

Infix to Postfix Conversion হল একটি সমস্যা যেখানে ইনফিক্স (প্রথাগত) এক্সপ্রেশনকে পোস্টফিক্স (Reverse Polish Notation) এক্সপ্রেশনে রূপান্তর করা হয়। ইনফিক্স এক্সপ্রেশনে অপারেটর অপার্যান্ডের মধ্যে থাকে, যেমন A + B। পোস্টফিক্সে, অপারেটরগুলো অপার্যান্ডের পরে আসে, যেমন A B +।

উদাহরণ: Infix to Postfix Conversion

import java.util.Stack;

public class InfixToPostfix {
    public static void main(String[] args) {
        String infixExpression = "A+B*(C^D-E)^(F+G*H)-I";
        System.out.println("Infix Expression: " + infixExpression);
        String postfixExpression = infixToPostfix(infixExpression);
        System.out.println("Postfix Expression: " + postfixExpression);
    }

    // Function to convert infix expression to postfix expression
    public static String infixToPostfix(String expression) {
        StringBuilder result = new StringBuilder();
        Stack<Character> stack = new Stack<>();

        // Iterate through the expression
        for (char ch : expression.toCharArray()) {
            // If the character is an operand, add it to the result
            if (Character.isLetterOrDigit(ch)) {
                result.append(ch);
            }
            // If the character is '(', push it to stack
            else if (ch == '(') {
                stack.push(ch);
            }
            // If the character is ')', pop and append until '(' is encountered
            else if (ch == ')') {
                while (!stack.isEmpty() && stack.peek() != '(') {
                    result.append(stack.pop());
                }
                stack.pop();  // Remove '(' from stack
            }
            // If the character is an operator, pop operators with higher or equal precedence
            else {
                while (!stack.isEmpty() && precedence(ch) <= precedence(stack.peek())) {
                    result.append(stack.pop());
                }
                stack.push(ch);  // Push the current operator to stack
            }
        }

        // Pop all remaining operators from the stack
        while (!stack.isEmpty()) {
            result.append(stack.pop());
        }

        return result.toString();
    }

    // Function to return precedence of operators
    public static int precedence(char operator) {
        switch (operator) {
            case '^': return 3;
            case '*':
            case '/': return 2;
            case '+':
            case '-': return 1;
            default: return -1;
        }
    }
}

ব্যাখ্যা:

1. Stack ব্যবহার করে ইনফিক্স এক্সপ্রেশনকে পোস্টফিক্স এক্সপ্রেশনে রূপান্তর করা হয়।
2. যদি একটি অপ্রচলিত অপার্যান্ড (অর্থাৎ, অক্ষর বা সংখ্যা) পাওয়া যায়, তা সরাসরি আউটপুটে যুক্ত করা হয়।
3. যদি একটি অপারেটর পাওয়া যায়, তবে সেগুলোকে স্ট্যাকে রাখা হয় এবং যতক্ষণ না স্ট্যাকের শীর্ষে একটি কম প্রাধান্যসম্পন্ন অপারেটর পাওয়া যায়, ততক্ষণ সেগুলো পপ করা হয়।
4. প্রাধান্য অনুযায়ী অপারেটরের গুরুত্ব নির্ধারণ করতে precedence() ফাংশন ব্যবহার করা হয়।

আউটপুট:

Infix Expression: A+B*(C^D-E)^(F+G*H)-I
Postfix Expression: ABCD^E-FGH*+^*+I-

সারাংশ

Stack ডাটা স্ট্রাকচারটি Balanced Parentheses Checking এবং Infix to Postfix Conversion এর মতো সমস্যা সমাধানের জন্য অত্যন্ত উপযোগী। Java তে স্ট্যাক ব্যবহার করে এই সমস্যাগুলো খুব সহজে এবং কার্যকরভাবে সমাধান করা যায়।

1. Balanced Parentheses Checking এর মাধ্যমে স্ট্যাকের সাহায্যে প্যারেন্টেসিসের সঠিকতা যাচাই করা যায়।
2. Infix to Postfix Conversion সমস্যা স্ট্যাক ব্যবহার করে ইনফিক্স এক্সপ্রেশনকে পোস্টফিক্স এক্সপ্রেশনে রূপান্তর করা হয়, যা পরবর্তীতে অ্যালগরিদমিক অপারেশনগুলো সহজতর করে।

Java তে স্ট্যাক ব্যবহার করে এই ধরনের সমস্যাগুলোর সমাধান করা সহজ এবং প্রোডাকটিভ হতে পারে।