Java তে Stack এর ইমপ্লিমেন্টেশন (using Array এবং Linked List)

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: ইনফিক্স, পোস্টফিক্স, এবং প্রিফিক্স এক্সপ্রেশনের মূল্য নির্ধারণে স্ট্যাক ব্যবহৃত হয়।

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