আমাদের ডেটা এবং প্রায়োরিটি (priority) ইন্টিজার ভ্যালু হিসেবে দেওয়া আছে এবং টাস্ক হলো প্রায়োরিটি অনুযায়ী একটি লিংকড লিস্ট (linked list) তৈরি করে রেজাল্ট ডিসপ্লে করা।
কিউ (Queue) হল একটি FIFO (First In First Out) ডেটা স্ট্রাকচার যেখানে প্রথমে ইনসার্ট করা এলিমেন্টটি প্রথমে রিমুভ হয়। একটি প্রায়োরিটি কিউ (Priority Queue) হল একটি কিউ টাইপ যেখানে এলিমেন্টগুলো প্রায়োরিটি অনুযায়ী ইনসার্ট বা ডিলিট করা হয়। এটি কিউ, স্ট্যাক বা লিংকড লিস্ট ডেটা স্ট্রাকচার দিয়ে ইমপ্লিমেন্ট করা যায়। প্রায়োরিটি কিউ নিচের রুলগুলো ফলো করে:
- হাইএস্ট প্রায়োরিটি ওয়ালা ডেটা বা এলিমেন্ট লোয়েস্ট প্রায়োরিটি ওয়ালা ডেটা বা এলিমেন্টের আগে এক্সিকিউট হবে।
- যদি দুটি এলিমেন্টের প্রায়োরিটি একই হয়, তবে সেগুলো লিস্টে যোগ হওয়ার ক্রম অনুযায়ী এক্সিকিউট হবে।
প্রায়োরিটি কিউ ইমপ্লিমেন্ট করার জন্য লিংকড লিস্টের একটি নোড (node) তিনটি অংশ ধারণ করবে:
- ডেটা (Data) − এটি ইন্টিজার ভ্যালু স্টোর করবে।
- অ্যাড্রেস (Address) − এটি পরবর্তী নোডের (next node) অ্যাড্রেস স্টোর করবে।
- প্রায়োরিটি (Priority) − এটি প্রায়োরিটি স্টোর করবে যা একটি ইন্টিজার ভ্যালু। এটি ০-১০ এর মধ্যে থাকতে পারে যেখানে ০ হাইএস্ট প্রায়োরিটি এবং ১০ লোয়েস্ট প্রায়োরিটি নির্দেশ করে।
উদাহরণ (Example)
ইনপুট (Input)
আউটপুট (Output)
আলগরিদম (Algorithm)
Start
Step 1 → Declare a struct node
Declare data, priority
Declare a struct node* next
Step 2 → In function Node* newNode(int d, int p)
Set Node* temp = (Node*)malloc(sizeof(Node))
Set temp->data = d
Set temp->priority = p
Set temp->next = NULL
Return temp
Step 3 → In function int peek(Node** head)
Return (*head)->data
Step 4 → In function void pop(Node** head)
Set Node* temp = *head
Set (*head) = (*head)->next
free(temp)
Step 5 → In function push(Node** head, int d, int p)
Set Node* start = (*head)
Set Node* temp = newNode(d, p)
If (*head)->priority > p then,
Set temp->next = *head
Set (*head) = temp
Else
Loop While start->next != NULL && start->next->priority < p
Set start = start->next
Set temp->next = start->next
Set start->next = temp
Step 6 → In function int isEmpty(Node** head)
Return (*head) == NULL
Step 7 → In function int main()
Set Node* pq = newNode(7, 1)
Call function push(&pq, 1, 2)
Call function push(&pq, 3, 3)
Call function push(&pq, 2, 0)
Loop While (!isEmpty(&pq))
Print the results obtained from peek(&pq)
Call function pop(&pq)
Stop
উদাহরণ (C প্রোগ্রাম)
#include <stdio.h>
#include <stdlib.h>
// priority Node
typedef struct node {
int data;
int priority;
struct node* next;
} Node;
Node* newNode(int d, int p) {
Node* temp = (Node*)malloc(sizeof(Node));
temp->data = d;
temp->priority = p;
temp->next = NULL;
return temp;
}
int peek(Node** head) {
return (*head)->data;
}
void pop(Node** head) {
Node* temp = *head;
(*head) = (*head)->next;
free(temp);
}
void push(Node** head, int d, int p) {
Node* start = (*head);
Node* temp = newNode(d, p);
if ((*head)->priority > p) {
temp->next = *head;
(*head) = temp;
} else {
while (start->next != NULL && start->next->priority < p) {
start = start->next;
}
temp->next = start->next;
start->next = temp;
}
}
// Function to check the queue is empty
int isEmpty(Node** head) {
return (*head) == NULL;
}
// main function
int main() {
Node* pq = newNode(7, 1);
push(&pq, 1, 2);
push(&pq, 3, 3);
push(&pq, 2, 0);
while (!isEmpty(&pq)) {
printf("%d ", peek(&pq));
pop(&pq);
}
return 0;
}
আউটপুট (Output)
2 7 1 3
ব্যাখ্যা: প্রায়োরিটি ০ (হাইএস্ট) ওয়ালা এলিমেন্ট ২ প্রথমে আউটপুট হয়। তারপর প্রায়োরিটি ১ (৭), প্রায়োরিটি ২ (১), প্রায়োরিটি ৩ (৩)। লিংকড লিস্ট বেসড ইমপ্লিমেন্টেশনে ইনসারশন O(n) টাইম নেয় (প্রায়োরিটি অনুযায়ী সর্টেড পজিশন খুঁজতে), ডিলিশন O(1) (হেড থেকে)।
