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

কিউ একটি অ্যাবস্ট্রাক্ট ডেটা স্ট্রাকচার যা উপাদানগুলির একটি সংগ্রহ ধারণ করে। কিউ FIFO (First In First Out) মেকানিজম বাস্তবায়ন করে অর্থাৎ যে উপাদানটি প্রথমে ইনসার্ট করা হয় সেটিই প্রথমে ডিলিট হয়। অন্য কথায়, কিউ-তে সবচেয়ে কম সম্প্রতিকভাবে যোগ করা উপাদানটি প্রথমে রিমুভ হয়।

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

উদাহরণ

#include <iostream>
using namespace std;

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

struct node* front = NULL;
struct node* rear = NULL;
struct node* temp;

void Insert() {
    int val;
    cout << "Insert the element in queue : " << endl;
    cin >> val;
    if (rear == NULL) {
        rear = (struct node *)malloc(sizeof(struct node));
        rear->next = NULL;
        rear->data = val;
        front = rear;
    } else {
        temp = (struct node *)malloc(sizeof(struct node));
        rear->next = temp;
        temp->data = val;
        temp->next = NULL;
        rear = temp;
    }
}

void Delete() {
    temp = front;
    if (front == NULL) {
        cout << "Underflow" << endl;
        return;
    } else if (temp->next != NULL) {
        temp = temp->next;
        cout << "Element deleted from queue is : " << front->data << endl;
        free(front);
        front = temp;
    } else {
        cout << "Element deleted from queue is : " << front->data << endl;
        free(front);
        front = NULL;
        rear = NULL;
    }
}

void Display() {
    temp = front;
    if ((front == NULL) && (rear == NULL)) {
        cout << "Queue is empty" << endl;
        return;
    }
    cout << "Queue elements are: ";
    while (temp != NULL) {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << endl;
}

int main() {
    int ch;
    cout << "1) Insert element to queue" << endl;
    cout << "2) Delete element from queue" << endl;
    cout << "3) Display all the elements of queue" << endl;
    cout << "4) Exit" << endl;
    do {
        cout << "Enter your choice : " << endl;
        cin >> ch;
        switch (ch) {
            case 1: Insert(); break;
            case 2: Delete(); break;
            case 3: Display(); break;
            case 4: cout << "Exit" << endl; break;
            default: cout << "Invalid choice" << endl;
        }
    } while (ch != 4);
    return 0;
}

আউটপুট

1) Insert element to queue
2) Delete element from queue
3) Display all the elements of queue
4) Exit
Enter your choice : 1
Insert the element in queue : 4
Enter your choice : 1
Insert the element in queue : 3
Enter your choice : 1
Insert the element in queue : 5
Enter your choice : 2
Element deleted from queue is : 4
Enter your choice : 3
Queue elements are : 3 5
Enter your choice : 7
Invalid choice
Enter your choice : 4
Exit

উপরোক্ত প্রোগ্রামে, Insert() ফাংশনটি কিউ-তে একটি উপাদান ইনসার্ট করে। যদি rear NULL হয়, তবে কিউ খালি এবং একটি একক উপাদান ইনসার্ট করা হয়। অন্যথায়, একটি নোড rear-এর পরে প্রয়োজনীয় উপাদানসহ ইনসার্ট করা হয় এবং সেই নোডটিকে rear সেট করা হয়। এটি নিচে দেখানো হলো:

void Insert() {
    int val;
    cout << "Insert the element in queue : " << endl;
    cin >> val;
    if (rear == NULL) {
        rear = (struct node *)malloc(sizeof(struct node));
        rear->next = NULL;
        rear->data = val;
        front = rear;
    } else {
        temp = (struct node *)malloc(sizeof(struct node));
        rear->next = temp;
        temp->data = val;
        temp->next = NULL;
        rear = temp;
    }
}

Delete() ফাংশনে, যদি কিউ-তে কোনো উপাদান না থাকে তবে এটি আন্ডারফ্লো কন্ডিশন। যদি কিউ-তে শুধু একটি উপাদান থাকে যা ডিলিট হয় এবং front ও rear NULL সেট করা হয়। অন্যথায়, front-এ থাকা উপাদানটি ডিলিট হয় এবং front পরবর্তী উপাদানকে পয়েন্ট করে। এটি নিচে দেখানো হলো:

void Delete() {
    temp = front;
    if (front == NULL) {
        cout << "Underflow" << endl;
        return;
    } else if (temp->next != NULL) {
        temp = temp->next;
        cout << "Element deleted from queue is : " << front->data << endl;
        free(front);
        front = temp;
    } else {
        cout << "Element deleted from queue is : " << front->data << endl;
        free(front);
        front = NULL;
        rear = NULL;
    }
}

Display() ফাংশনে, যদি front এবং rear NULL হয় তবে কিউ খালি। অন্যথায়, temp ভেরিয়েবলের সাহায্যে একটি হয়েল লুপ ব্যবহার করে সমস্ত কিউ উপাদান প্রদর্শন করা হয়। এটি নিচে দেখানো হলো:

void Display() {
    temp = front;
    if ((front == NULL) && (rear == NULL)) {
        cout << "Queue is empty" << endl;
        return;
    }
    cout << "Queue elements are: ";
    while (temp != NULL) {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << endl;
}

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

int main() {
    int ch;
    cout << "1) Insert element to queue" << endl;
    cout << "2) Delete element from queue" << endl;
    cout << "3) Display all the elements of queue" << endl;
    cout << "4) Exit" << endl;
    do {
        cout << "Enter your choice : " << endl;
        cin >> ch;
        switch (ch) {
            case 1: Insert(); break;
            case 2: Delete(); break;
            case 3: Display(); break;
            case 4: cout << "Exit" << endl; break;
            default: cout << "Invalid choice" << endl;
        }
    } while (ch != 4);
    return 0;
}