C++ প্রোগ্রাম: প্রায়োরিটি কিউ ইমপ্লিমেন্টেশন

কিউ FIFO হিসেবে ইমপ্লিমেন্ট করা হয় যেখানে ইনসারশন একটা এন্ডে (rear) এবং ডিলিশন অন্য এন্ড থেকে (front) হয়। প্রথমে প্রবেশ করা এলিমেন্টটি প্রথমে ডিলিট হয়।

কিউ অপারেশন:

• EnQueue (int data): Rear এন্ডে ইনসারশন

• int DeQueue(): Front এন্ড থেকে ডিলিশন

কিন্তু প্রায়োরিটি কিউ First-In-First-Out ফলো করে না, বরং প্রতিটি এলিমেন্টের একটি প্রায়োরিটি থাকে জরুরি ভিত্তিতে।

একই প্রায়োরিটি वालা আইটেমগুলো First-In-First-Out সার্ভিস ভিত্তিতে প্রসেস হয়।

উচ্চ প্রায়োরিটির আইটেম নিম্ন প্রায়োরিটির আইটেমের আগে প্রসেস হয়।

ক্লাস বর্ণনা

Begin
    class Priority_Queue has following functions:
    function insert() to insert items at priority queue with their priorities:
        1) If queue is empty insert data from the left end of the queue.
        2) If queue is having some nodes then insert the new node at the end of those nodes having priority
            same with the new node and also before all the nodes having priority lesser than the
            current priority of the new node.
    function del() to delete items from queue.
        If queue is completely empty, print underflow otherwise delete the front element and update front.
End

উদাহরণ

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
struct n // node declaration {
    int p;
    int info;
    struct n *l;
};
class Priority_Queue {
    private:
        // Declare a front pointer f and initialize it to NULL.
        n *f;
    public:
        Priority_Queue() // constructor {
            f = NULL;
        }
        void insert(int i, int p) {
            n *t, *q;
            t = new n;
            t->info = i;
            t->p = p;
            if (f == NULL || p < f->p) {
                t->l = f;
                f = t;
            } else {
                q = f;
                while (q->l != NULL && q->l->p <= p)
                    q = q->l;
                t->l = q->l;
                q->l = t;
            }
        }
        void del() {
            n *t;
            if (f == NULL) // if queue is null
                cout << "Queue Underflow\n";
            else {
                t = f;
                cout << "Deleted item is: " << t->info << endl;
                f = f->l;
                free(t);
            }
        }
        void show() // print queue {
            n *ptr;
            ptr = f;
            if (f == NULL)
                cout << "Queue is empty\n";
            else {
                cout << "Queue is:\n";
                cout << "Priority Item\n";
                while (ptr != NULL) {
                    cout << ptr->p << " " << ptr->info << endl;
                    ptr = ptr->l;
                }
            }
        }
};
int main() {
    int c, i, p;
    Priority_Queue pq;
    do { // perform switch operation
        cout << "1.Insert\n";
        cout << "2.Delete\n";
        cout << "3.Display\n";
        cout << "4.Exit\n";
        cout << "Enter your choice: ";
        cin >> c;
        switch (c) {
            case 1:
                cout << "Input the item value to be added in the queue: ";
                cin >> i;
                cout << "Enter its priority: ";
                cin >> p;
                pq.insert(i, p);
                break;
            case 2:
                pq.del();
                break;
            case 3:
                pq.show();
                break;
            case 4:
                break;
            default:
                cout << "Wrong choice\n";
        }
    } while (c != 4);
    return 0;
}

আউটপুট

1.Insert
2.Delete
3.Display
4.Exit
Enter your choice: 1
Input the item value to be added in the queue: 7
Enter its priority: 2
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice: 1
Input the item value to be added in the queue: 6
Enter its priority: 1
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice: 1
Input the item value to be added in the queue: 3
Enter its priority: 3
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice: 1
Input the item value to be added in the queue: 4
Enter its priority: 3
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice: 3
Queue is:
Priority Item
1 6
2 7
3 3
3 4
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice: 4