हमें डेटा और प्राथमिकता एक पूर्णांक मान के रूप में दी जाती है और कार्य दी गई प्राथमिकता के अनुसार एक डबल लिंक्ड सूची बनाना और परिणाम प्रदर्शित करना है।
Queue एक FIFO डेटा संरचना है जिसमें जो तत्व पहले डाला जाता है वह सबसे पहले निकाला जाता है। प्राथमिकता कतार एक प्रकार की कतार है जिसमें प्राथमिकता के आधार पर तत्वों को डाला या हटाया जा सकता है। इसे क्यू, स्टैक या लिंक्ड लिस्ट डेटा स्ट्रक्चर का उपयोग करके लागू किया जा सकता है। इन नियमों का पालन करके प्राथमिकता कतार लागू की जाती है -
- उच्चतम प्राथमिकता वाले डेटा या तत्व को न्यूनतम प्राथमिकता वाले डेटा या तत्व से पहले निष्पादित किया जाएगा।
- यदि दो तत्वों की प्राथमिकता समान है तो उन्हें सूची में जोड़े जाने के क्रम में निष्पादित किया जाएगा।
प्राथमिकता कतार को लागू करने के लिए एक डबल लिंक्ड सूची के नोड में तीन भाग होंगे -
- डेटा - यह पूर्णांक मान को संग्रहीत करेगा।
- अगला पता - यह अगले नोड का पता संग्रहीत करेगा
- पिछला पता - यह पिछले नोड के पते को संग्रहीत करेगा
- प्राथमिकता - यह प्राथमिकता को संग्रहीत करेगा जो एक पूर्णांक मान है। यह 0-10 के बीच हो सकता है जहां 0 सर्वोच्च प्राथमिकता का प्रतिनिधित्व करता है और 10 निम्नतम प्राथमिकता का प्रतिनिधित्व करता है।
उदाहरण
इनपुट -
आउटपुट-
एल्गोरिदम
Start Step 1-> Declare a struct Node Declare info, priority Declare struct Node *prev, *next Step 2-> In function push(Node** fr, Node** rr, int n, int p) Set Node* news = (Node*)malloc(sizeof(Node)) Set news->info = n Set news->priority = p If *fr == NULL then, Set *fr = news Set *rr = news Set news->next = NULL Else If p <= (*fr)->priority then, Set news->next = *fr Set (*fr)->prev = news->next Set *fr = news Else If p > (*rr)->priority then, Set news->next = NULL Set (*rr)->next = news Set news->prev = (*rr)->next Set *rr = news Else Set Node* start = (*fr)->next Loop While start->priority > p Set start = start->next Set (start->prev)->next = news Set news->next = start->prev Set news->prev = (start->prev)->next Set start->prev = news->next Step 3-> In function int peek(Node *fr) Return fr->info Step 4-> In function bool isEmpty(Node *fr) Return (fr == NULL) Step 5-> In function int pop(Node** fr, Node** rr) Set Node* temp = *fr Set res = temp->info Set (*fr) = (*fr)->next free(temp) If *fr == NULL then, *rr = NULL Return res Step 6-> In function int main() Declare and assign Node *front = NULL, *rear = NULL Call function push(&front, &rear, 4, 3) Call function push(&front, &rear, 3, 2) Call function push(&front, &rear, 5, 2) Call function push(&front, &rear, 5, 7) Call function push(&front, &rear, 2, 6) Call function push(&front, &rear, 1, 4) Print the results obtained from calling the function pop(&front, &rear) Print the results obtained from calling the function peek(front) Stop
उदाहरण
#include <bits/stdc++.h>
using namespace std;
//doubly linked list node
struct Node {
int info;
int priority;
struct Node *prev, *next;
};
//inserting a new Node
void push(Node** fr, Node** rr, int n, int p) {
Node* news = (Node*)malloc(sizeof(Node));
news->info = n;
news->priority = p;
// if the linked list is empty
if (*fr == NULL) {
*fr = news;
*rr = news;
news->next = NULL;
} else {
// If p is less than or equal front
// node's priority, then insert the node
// at front.
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 {
// Finding the position where we need to
// insert the new node.
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;
}
}
}
//the last value
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;
}
// main function
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