ডেটা এবং প্রায়োরিটি (ইন্টিজার ভ্যালু) দেওয়া আছে এবং কাজ হলো প্রায়োরিটি অনুযায়ী ডাবলি লিংকড লিস্ট তৈরি করে ফলাফল দেখানো।
কিউ হলো একটি FIFO ডেটা স্ট্রাকচার যেখানে প্রথমে ইনসার্ট করা এলিমেন্ট প্রথমে রিমুভ হয়। প্রায়োরিটি কিউ হলো কিউর এক ধরন যেখানে এলিমেন্ট প্রায়োরিটি অনুযায়ী ইনসার্ট বা ডিলিট হয়। এটি কিউ, স্ট্যাক বা লিংকড লিস্ট দিয়ে বাস্তবায়ন করা যায়। প্রায়োরিটি কিউ নিচের নিয়মগুলো মেনে চলে:
- সর্বোচ্চ প্রায়োরিটivit वाले ডেটা বা এলিমেন্ট প্রথমে এক্সিকিউট হবে।
- দুই এলিমেন্টের প্রায়োরিটি সমান হলে সেগুলো যোগ হওয়ার ক্রমে এক্সিকিউট হবে।
প্রায়োরিটি কিউ বাস্তবায়নের জন্য ডাবলি লিংকড লিস্টের একটি নোডে তিনটি অংশ থাকবে:
- Data - ইন্টিজার ভ্যালু সংরক্ষণ করবে।
- Next Address - পরের নোডের ঠিকানা সংরক্ষণ করবে।
- Previous Address - আগের নোডের ঠিকানা সংরক্ষণ করবে।
- Priority - প্রায়োরিটি সংরক্ষণ করবে (ইন্টিজার ভ্যালু)। এটি ০-১০ পর্যন্ত হতে পারে, যেখানে ০ সর্বোচ্চ প্রায়োরিটি এবং ১০ ন্যূনতম।
উদাহরণ
ইনপুট -
আউটপুট -
অ্যালগরিদম
শুরু
ধাপ ১ -> struct Node ঘোষণা
info, priority ঘোষণা
struct Node *prev, *next ঘোষণা
ধাপ ২ -> push(Node** fr, Node** rr, int n, int p) ফাংশনে
Node* news = (Node*)malloc(sizeof(Node)) সেট
news->info = n সেট
news->priority = p সেট
যদি *fr == NULL হয়, তবে
*fr = news সেট
*rr = news সেট
news->next = NULL সেট
অন্যথায় যদি p <= (*fr)->priority হয়, তবে
news->next = *fr সেট
(*fr)->prev = news->next সেট
*fr = news সেট
অন্যথায় যদি p > (*rr)->priority হয়, তবে
news->next = NULL সেট
(*rr)->next = news সেট
news->prev = (*rr)->next সেট
*rr = news সেট
অন্যথায়
Node* start = (*fr)->next সেট
লুপ যতক্ষণ start->priority > p
start = start->next সেট
(start->prev)->next = news সেট
news->next = start->prev সেট
news->prev = (start->prev)->next সেট
start->prev = news->next সেট
ধাপ ৩ -> int peek(Node *fr) ফাংশনে
fr->info রিটার্ন
ধাপ ৪ -> bool isEmpty(Node *fr) ফাংশনে
(fr == NULL) রিটার্ন
ধাপ ৫ -> int pop(Node** fr, Node** rr) ফাংশনে
Node* temp = *fr সেট
res = temp->info সেট
(*fr) = (*fr)->next সেট
free(temp)
যদি *fr == NULL হয়, তবে
*rr = NULL সেট
res রিটার্ন
ধাপ ৬ -> int main() ফাংশনে
Node *front = NULL, *rear = NULL ঘোষণা এবং অ্যাসাইন
push(&front, &rear, 4, 3) কল
push(&front, &rear, 3, 2) কল
push(&front, &rear, 5, 2) কল
push(&front, &rear, 5, 7) কল
push(&front, &rear, 2, 6) কল
push(&front, &rear, 1, 4) কল
pop(&front, &rear) কল করে ফলাফল প্রিন্ট
peek(front) কল করে ফলাফল প্রিন্ট
শেষ
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
// ডাবলি লিংকড লিস্ট নোড
struct Node {
int info;
int priority;
struct Node *prev, *next;
};
// নতুন নোড ইনসার্ট
void push(Node** fr, Node** rr, int n, int p) {
Node* news = (Node*)malloc(sizeof(Node));
news->info = n;
news->priority = p;
// যদি লিংকড লিস্ট খালি হয়
if (*fr == NULL) {
*fr = news;
*rr = news;
news->next = NULL;
} else {
// যদি p ফ্রন্ট নোডের প্রায়োরিটির চেয়ে কম বা সমান হয়, তবে ফ্রন্টে ইনসার্ট
if (p <= (*fr)->priority) {
news->next = *fr;
(*fr)->prev = news->next;
*fr = news;
} else if (p > (*rr)->priority) {
news->next = NULL;
(*rr)->next = news;
news->prev = (*rr)->next;
*rr = news;
} else {
// নতুন নোড ইনসার্ট করার পজিশন খুঁজে বের করা
Node* start = (*fr)->next;
while (start->priority > p)
start = start->next;
(start->prev)->next = news;
news->next = start->prev;
news->prev = (start->prev)->next;
start->prev = news->next;
}
}
}
// শেষ ভ্যালু
int peek(Node *fr) {
return fr->info;
}
bool isEmpty(Node *fr) {
return (fr == NULL);
}
int pop(Node** fr, Node** rr) {
Node* temp = *fr;
int res = temp->info;
(*fr) = (*fr)->next;
free(temp);
if (*fr == NULL)
*rr = NULL;
return res;
}
// মেইন ফাংশন
int main() {
Node *front = NULL, *rear = NULL;
push(&front, &rear, 4, 3);
push(&front, &rear, 3, 2);
push(&front, &rear, 5, 2);
push(&front, &rear, 5, 7);
push(&front, &rear, 2, 6);
push(&front, &rear, 1, 4);
printf("%d\n", pop(&front, &rear));
printf("%d\n", peek(front));
return 0;
}
আউটপুট
5 3
