सिंगली लिंक्ड लिस्ट का उपयोग कर प्राथमिकता कतार


कठिनाई स्तर मध्यम
में अक्सर पूछा BrowserStack Hulu महिंद्रा कॉमिवा पॉकेट रत्न सोरोको
लिंक्ड सूची पंक्ति

प्राथमिकता में पंक्ति एक अकेले का उपयोग कर लिंक्ड सूची समस्या, हमें एक एकल लिंक की गई सूची का उपयोग करके प्राथमिकता कतार लागू करने की आवश्यकता है। एक प्राथमिकता कतार में निम्नलिखित ऑपरेशन शामिल हैं,

  1. पुश (x, p): प्राथमिकता पी में एक उपयुक्त स्थिति में प्राथमिकता पी के साथ एक तत्व x जोड़ें।
  2. pop (): उच्चतम प्राथमिकता वाले तत्व को निकालें और वापस लौटाएँ
  3. झांकना (): उच्चतम प्राथमिकता वाले तत्व को वापस लौटाएं

उदाहरण

इनपुट:
धक्का (5, 2)
धक्का (1, 3)
झांकना ()
धक्का (7, 5)
धक्का (9, 1)
पॉप()
पॉप()
झांकना ()
आउटपुट:
1
7
1
5

एकल पंक्ति सूची का उपयोग कर प्राथमिकता कतार के लिए एल्गोरिथ्म

विचार लिंक की गई सूची को प्राथमिकता के अवरोही क्रम में बनाए रखना है ताकि सबसे अधिक प्राथमिकता वाला तत्व सबसे आगे हो।

धक्का (एक्स, पी)

चूंकि तत्वों को प्राथमिकताओं के अवरोही क्रम में व्यवस्थित किया जाता है, इसलिए प्राथमिकता वाले तत्व को पहले तत्व से पहले पी से कम प्राथमिकता के साथ डाला जाता है, ताकि प्राथमिकताओं का क्रम परेशान न हो। तीन मामले सामने आए,

  1. पी से कम प्राथमिकता वाला कोई तत्व नहीं, लिंक किए गए सूची के अंत में नया तत्व जोड़ें।
  2. सभी तत्वों में पी से कम प्राथमिकता है, लिंक किए गए सूची की शुरुआत में नया तत्व जोड़ें।
  3. कुछ तत्वों की प्राथमिकता पी से कम है जबकि अन्य की पी से अधिक प्राथमिकता है, पहले तत्व की तुलना में पी से कम प्राथमिकता वाले नए तत्व को जोड़ें।

सिंगली लिंक्ड लिस्ट का उपयोग कर प्राथमिकता कतार

समय जटिलता = पर)

एकल लिंक लिस्ट का उपयोग करते हुए प्राथमिकता कतार के लिए छद्म कोड

  1. डेटा = x और प्राथमिकता = p के साथ एक नया नोड बनाएं, इसे नयाकोड दें
  2. यदि सिर अशक्त है, तो यह डाला जाने वाला पहला नोड है, इसलिए सिर = newNode करें और वापस लौटें।
  3. एक नोड अस्थायी सिर के बराबर बनाएँ और एक नोड प्रचलित शून्य के बराबर है।
  4. पहले नोड को एक लूप चलाकर पी से कम प्राथमिकता के साथ खोजें, जबकि अस्थायी शून्य नहीं है और टेम्प की प्राथमिकता पी से अधिक है। प्रत्येक पुनरावृत्ति पर, अस्थायी और अस्थायी के रूप में अस्थायी के रूप में अद्यतन करें।
  5. लूप के अंत के बाद, यदि अस्थायी अशक्त है, तो इसका मतलब है कि पी की तुलना में कम प्राथमिकता वाला कोई नोड नहीं है, लिंक किए गए सूची के अंत में नया नोड डालें, अर्थात, prev.next = newNode।
  6. एल्स यदि प्रचलित है तो अशक्त है, इसका अर्थ है कि सभी नोड्स पी से अधिक प्राथमिकता वाले हैं। NewNode.next = सिर और सिर = newNode करें।
  7. और, अस्थायी से पहले नया नोड डालें, अर्थात् newNode.next = temp और prev.next = नया नोड करें।

पॉप()

लिंक की गई सूची के सामने सर्वोच्च प्राथमिकता तत्व है, इसे हटा दें, और वापस लौटें।

समय जटिलता = ओ (1)

झांकना ()

लिंक की गई सूची के सामने सर्वोच्च प्राथमिकता वाला तत्व है, इसे वापस लौटाएं।

समय जटिलता = ओ (1)

एकल पंक्ति सूची का उपयोग करते हुए प्राथमिकता कतार के लिए जावा कोड

public class PriorityQueueUsingSinglyLinkedList {
    // class representing node of a linked list
    static class Node {
        int data;
        int priority;
        Node next;
        
        public Node(int data, int priority) {
            this.data = data;
            this.priority = priority;
        }
    }

    // Variable representing the head of linked list
    private static Node head = null;

    private static void push(int x, int p) {
        // Create a new node
        Node newNode = new Node(x, p);

        // If head is null, this is the first node to be added
        // so make head = newNode
        if (head == null) {
            head = newNode;
            return;
        }

        Node temp = head;
        Node prev = null;

        // search for first node having priority less than p
        while (temp != null && temp.priority > p) {
            prev = temp;
            temp = temp.next;
        }

        if (temp == null) {
            // no node with priority less than this node (Case 1)
            prev.next = newNode;
        } else {
            if (prev == null) {
                // all the nodes have priority less than p (Case 2)
                // add this node at the starting
                newNode.next = head;
                head = newNode;
            } else {
                // Case 3
                // add this node before the node with priority less than p 
                newNode.next = temp;
                prev.next = newNode;
            }
        }
    }

    private static int peek() {
        // head of the linked list contains the maximum priority element
        if (head != null) {
            return head.data;
        }
        return -1;
    }

    private static int pop() {
        // head of the linked list contains the maximum priority element
        if (head != null) {
            int data = head.data;
            // removing the highest priority element
            head = head.next;
            return data;
        }
        return -1;
    }

    public static void main(String[] args) {
        // Example
        push(5, 2);
        push(1, 3);
        System.out.println(peek());
        push(7, 5);
        push(9, 1);
        System.out.println(pop());
        System.out.println(pop());
        System.out.println(peek());
    }
}
1
7
1
5

सी + + कोड प्राथमिकता कतार के लिए एकल लिंक की गई सूची का उपयोग करके

#include<bits/stdc++.h> 
using namespace std;

// class representing a tree node
class Node {
    public:
    int data;
    int priority;
    Node *next;
    
    Node(int d, int p) {
        data = d;
        priority = p;
        next = NULL;
    }
};

// function to create a new node
Node* newNode(int x, int p) {
    Node *node = new Node(x, p);
    return node;
}

// Variable representing the head of linked list
Node *head = NULL;

void push(int x, int p) {
    // Create a new node
    Node *node = newNode(x, p);
    
    // If head is null, this is the first node to be added
    // so make head = newNode
    if (head == NULL) {
        head = node;
        return;
    }
    
    Node *temp = head;
    Node *prev = NULL;
    
    // search for first node having priority less than p
    while (temp != NULL && temp->priority > p) {
        prev = temp;
        temp = temp->next;
    }
    
    if (temp == NULL) {
        // no node with priority less than this node (Case 1)
        prev->next = node;
    } else {
        if (prev == NULL) {
            // all the nodes have priority less than p (Case 2)
            // add this node at the starting
            node->next = head;
            head = node;
        } else {
            // Case 3
            // add this node before the node with priority less than p
            node->next = temp;
            prev->next = node;
        }
    }
}

int pop() {
    // head of the linked list contains the maximum priority element
    if (head != NULL) {
        int data = head->data;
        // removing the highest priority element
        head = head->next;
        return data;
    }
    return -1;
}

int peek() {
    // head of the linked list contains the maximum priority element
    if (head != NULL) {
        return head->data;
    }
    return -1;
}

int main() {
    // Example
    push(5, 2);
    push(1, 3);
    cout<<peek()<<endl;
    push(7, 5);
    push(9, 1);
    cout<<pop()<<endl;
    cout<<pop()<<endl;
    cout<<peek()<<endl;
    
    return 0;
}
1
7
1
5

संदर्भ 1    संदर्भ २