লিঙ্কড লিস্ট ব্যবহার করে স্ট্যাক বাস্তবায়নের C++ প্রোগ্রাম

স্ট্যাক একটি অ্যাবস্ট্রাক্ট ডেটা স্ট্রাকচার যা উপাদানগুলির একটি সংগ্রহ ধারণ করে। স্ট্যাক LIFO (Last In First Out) মেকানিজম বাস্তবায়ন করে অর্থাৎ যে উপাদানটি শেষে পুশ করা হয় সেটিই প্রথমে পপ হয়। স্ট্যাকে কিছু মূল অপারেশন রয়েছে:

• Push - এটি স্ট্যাকের উপরে একটি ডেটা ভ্যালু যোগ করে।
• Pop - এটি স্ট্যাকের উপরে থাকা ডেটা ভ্যালু রিমুভ করে।
• Peek - এটি স্ট্যাকের শীর্ষ ডেটা ভ্যালু রিটার্ন করে।

লিঙ্কড লিস্ট ব্যবহার করে স্ট্যাক বাস্তবায়ন করার একটি প্রোগ্রাম নিচে দেওয়া হলো:

উদাহরণ

#include <iostream>
using namespace std;

struct Node {
    int data;
    struct Node *next;
};

struct Node* top = NULL;

void push(int val) {
    struct Node* newnode = (struct Node*) malloc(sizeof(struct Node));
    newnode->data = val;
    newnode->next = top;
    top = newnode;
}

void pop() {
    if (top == NULL)
        cout << "Stack Underflow" << endl;
    else {
        cout << "The popped element is " << top->data << endl;
        top = top->next;
    }
}

void display() {
    struct Node* ptr;
    if (top == NULL)
        cout << "stack is empty";
    else {
        ptr = top;
        cout << "Stack elements are: ";
        while (ptr != NULL) {
            cout << ptr->data << " ";
            ptr = ptr->next;
        }
    }
    cout << endl;
}

int main() {
    int ch, val;
    cout << "1) Push in stack" << endl;
    cout << "2) Pop from stack" << endl;
    cout << "3) Display stack" << endl;
    cout << "4) Exit" << endl;
    do {
        cout << "Enter choice: " << endl;
        cin >> ch;
        switch (ch) {
            case 1: {
                cout << "Enter value to be pushed:" << endl;
                cin >> val;
                push(val);
                break;
            }
            case 2: {
                pop();
                break;
            }
            case 3: {
                display();
                break;
            }
            case 4: {
                cout << "Exit" << endl;
                break;
            }
            default: {
                cout << "Invalid Choice" << endl;
            }
        }
    } while (ch != 4);
    return 0;
}

আউটপুট

1) Push in stack
2) Pop from stack
3) Display stack
4) Exit
Enter choice: 1
Enter value to be pushed: 2
Enter choice: 1
Enter value to be pushed: 6
Enter choice: 1
Enter value to be pushed: 8
Enter choice: 1
Enter value to be pushed: 7
Enter choice: 2
The popped element is 7
Enter choice: 3
Stack elements are: 8 6 2
Enter choice: 5
Invalid Choice
Enter choice: 4
Exit

উপরোক্ত প্রোগ্রামে, Node স্ট্রাকচারটি লিঙ্কড লিস্ট তৈরি করতে ব্যবহৃত হয়েছে যা স্ট্যাক হিসেবে বাস্তবায়ন করা হয়েছে। কোডটি নিচে দেওয়া হলো:

struct Node {
    int data;
    struct Node *next;
};

push() ফাংশনটি val আর্গুমেন্ট নেয় অর্থাৎ স্টാക്കে পুশ করার মান। তারপর একটি নতুন নোড তৈরি করা হয় এবং val ডেটা পάρ্টে ইনসার্ট করা হয়। এই নোডটি লিঙ্কড লিস্টের সামনে যোগ করা হয় এবং top এটি পয়েন্ট করে। এর কোড স্নিপেট নিচে দেওয়া হলো:

void push(int val) {
    struct Node* newnode = (struct Node*) malloc(sizeof(struct Node));
    newnode->data = val;
    newnode->next = top;
    top = newnode;
}

pop() ফাংশনটি স্ট্যাকের শীর্ষতম মান পপ করে, যদি কোনো মান থাকে। যদি স্ট্যাক খালি থাকে তবে আন্ডারফ্লো প্রিন্ট করা হয়। এটি নিচে দেওয়া হলো:

void pop() {
    if (top == NULL)
        cout << "Stack Underflow" << endl;
    else {
        cout << "The popped element is " << top->data << endl;
        top = top->next;
    }
}

display() ফাংশনটি স্ট্যাকের সমস্ত উপাদান প্রদর্শন করে। এটি ptr ব্যবহার করে যা প্রাথমিকভাবে top-কে পয়েন্ট করে কিন্তু স্ট্যাকের শেষ পর্যন্ত যায়। ptr-এর সাথে সম্পর্কিত সমস্ত ডেটা ভ্যালু প্রিন্ট করা হয়। এটি নিচে দেওয়া হলো:

void display() {
    struct Node* ptr;
    if (top == NULL)
        cout << "stack is empty";
    else {
        ptr = top;
        cout << "Stack elements are: ";
        while (ptr != NULL) {
            cout << ptr->data << " ";
            ptr = ptr->next;
        }
    }
    cout << endl;
}

main() ফাংশন ব্যবহারকারীকে পুশ, পপ বা ডিসপ্লে স্ট্যাক করার পছন্দ দেয়। ব্যবহারকারীর প্রতিক্রিয়া অনুযায়ী, উপযুক্ত ফাংশনটি স্যুইচ ব্যবহার করে কল করা হয়। যদি ব্যবহারকারী অবৈধ প্রতিক্রিয়া দেয়, তবে সেটি প্রিন্ট করা হয়। এর কোড স্নিপেট নিচে দেওয়া হলো:

int main() {
    int ch, val;
    cout << "1) Push in stack" << endl;
    cout << "2) Pop from stack" << endl;
    cout << "3) Display stack" << endl;
    cout << "4) Exit" << endl;
    do {
        cout << "Enter choice: " << endl;
        cin >> ch;
        switch (ch) {
            case 1: {
                cout << "Enter value to be pushed:" << endl;
                cin >> val;
                push(val);
                break;
            }
            case 2: {
                pop();
                break;
            }
            case 3: {
                display();
                break;
            }
            case 4: {
                cout << "Exit" << endl;
                break;
            }
            default: {
                cout << "Invalid Choice" << endl;
            }
        }
    } while (ch != 4);
    return 0;
}