قائمة انتظار الأولوية باستخدام قائمة مرتبطة بشكل مضاعف


مستوى الصعوبة متوسط
كثيرا ما يطلب في أمازون قلعة MAQ ووكر
قائمة مرتبطة طابور الأولوية طابور

المشكلة بيان

تتطلب مشكلة "أولوية قائمة الانتظار باستخدام قائمة مرتبطة بشكل مزدوج" تنفيذ الوظائف التالية لقائمة انتظار الأولوية باستخدام مضاعفة قائمة مرتبطة.

  1. دفع (س ، ع) : قم بإدراج عنصر x بأولوية p في قائمة انتظار الأولوية في الموضع المناسب.
  2. pop () : قم بإزالة العنصر ذي الأولوية القصوى وإعادته إلى قائمة انتظار الأولوية.
  3. نظرة خاطفة () : أعد العنصر ذي الأولوية القصوى في قائمة انتظار الأولوية دون إزالته.

مثال

push(5, 2)
push(1, 3)
peek()
push(7, 5)
push(9, 1)
pop()
pop()
peek()
1
7
1
5

خوارزمية لتنفيذ أولوية قائمة الانتظار باستخدام قائمة مرتبطة بشكل مزدوج

طابور الأولوية يتم تنفيذ استخدام قائمة مرتبطة بشكل مزدوج بنفس طريقة قائمة انتظار الأولوية باستخدام قائمة مرتبطة بشكل فردي. هنا في القائمة المرتبطة بشكل مضاعف ، يتعين علينا تعديل بعض المؤشرات الإضافية أثناء الإدراج والحذف.
الفكرة هي نفسها ، للحفاظ على القائمة المرتبطة بشكل مزدوج بترتيب تنازلي للأولوية ، بحيث يكون العنصر ذو الأولوية القصوى دائمًا في المقدمة.

دفع (س ، ع)

لدفع عنصر x بأولوية p إلى قائمة انتظار الأولوية ، ابحث عن المكان المناسب للعنصر ، وأدخله. المكان المناسب يقع مباشرة قبل العنصر الأول بأولوية أقل من p.

على سبيل المثال،
الأولويةQueue = (7، 5) -> (9، 4) -> (8، 2)
دفع (6 ، 3)
المكان المناسب لـ (6 ، 3) قبل (8 ، 2) مباشرة ، قائمة الانتظار بعد الإدراج هو ،
الأولويةQueue = (7، 5) -> (9، 4) -> (6، 3) -> (8، 2)
انظر الصورة أدناه للتوضيح.

قائمة انتظار الأولوية باستخدام قائمة مرتبطة بشكل مضاعف

  1. اجتياز في طابور الأولوية بدءًا من الرأس والعثور على العقدة الأولى ذات الأولوية الأقل من p.
  2. واحدة من الحالات الثلاث ممكنة.
  3. لا يوجد عنصر له أولوية أقل من p. في مثل هذه الحالة ، أدخل العقدة الجديدة في نهاية قائمة انتظار الأولوية.
  4. جميع العقد لها أولويات أقل من p. في مثل هذه الحالة ، أدخل العقدة الجديدة في بداية قائمة انتظار الأولوية.
  5. هناك بعض العقد ذات الأولوية الأقل من p وبعض العقد ذات الأولوية أكبر من p. في مثل هذه الحالة ، أدخل العقدة الجديدة قبل العقدة الأولى ذات الأولوية الأقل من p. تظهر هذه الحالة في الصورة أعلاه.

تعقيد الوقت = O (ن)
تعقيد الفضاء = يا (1)
حيث n هو العدد الإجمالي للعقد في قائمة انتظار الأولوية قبل الإدراج.

pop ()

يوجد العنصر ذو الأولوية القصوى في بداية قائمة انتظار الأولوية. إذا لم تكن قائمة انتظار الأولوية فارغة ، فاحذف العنصر الأول وأعده ، وإلا فلن يكون من الممكن الظهور.

تعقيد الوقت = يا (1)

نظرة خاطفة ()

يوجد العنصر ذو الأولوية القصوى في بداية قائمة انتظار الأولوية. إذا لم تكن قائمة انتظار الأولوية فارغة ، فارجع قيمة العنصر الأول في قائمة انتظار الأولوية.

تعقيد الوقت = يا (1)

رمز

Java Code لتنفيذ Priority Queue باستخدام قائمة مرتبطة بشكل مزدوج

class PriorityQueueUsingDoublyLinkedList {
    // class representing node of a doubly linked list
    static class Node {
        int data;
        int priority;
        Node next, prev;

        public Node(int data, int priority) {
            this.data = data;
            this.priority = priority;
        }
    }

    // head of doubly linked list
    private static Node head = null;

    private static void push(int data, int priority) {
        // if head is null this is the first node to be inserted
        // mark head as new Node
        if (head == null) {
            Node newNode = new Node(data, priority);
            head = newNode;
            return;
        }

        // create a new node with specified data
        Node node = new Node(data, priority);
        // find the first node having priority less than 'priority'
        Node temp = head, parent = null;
        while (temp != null && temp.priority >= priority) {
            parent = temp;
            temp = temp.next;
        }

        // Case 1 : All the nodes are having priorities less than 'priority'
        if (parent == null) {
            // insert the new node at the beginning of linked list
            node.next = head;
            head.prev = node;
            head = node;
        }
        // Case 2 : All the nodes are having priorities greater than 'priority'
        else if (temp == null) {
            // insert the node at the end of the linked list
            parent.next = node;
            node.prev = parent;
        }
        // Case 3 : Some nodes have priority higher than 'priority' and
        // some have priority lower than 'priority'
        else {
            // insert the new node before the first node having priority
            // less than 'priority'
            parent.next = node;
            node.prev = parent;
            node.next = temp;
            temp.prev = node;
        }
    }

    private static int peek() {
        // if head is not null, return the element at first position
        if (head != null) {
            return head.data;
        }
        return -1;
    }

    private static int pop() {
        // if head is not null, delete the element at first position and return its value
        if (head != null) {
            int curr = head.data;
            head = head.next;
            if (head != null) {
                head.prev = null;
            }
            return curr;
        }
        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

كود C ++ لتنفيذ Priority Queue باستخدام قائمة مرتبطة بشكل مزدوج

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

// class representing node of a doubly linked list
class Node {
    public:
    int data, priority;
    Node *next;
    Node *prev;
    
    Node(int d, int p) {
        data = d;
        priority = p;
        next = prev = NULL;
    }
};

// head of doubly linked list
Node *head = NULL;

void push(int data, int priority) {
    // if head is null this is the first node to be inserted
    // mark head as new Node
    if (head == NULL) {
        Node *newNode = new Node(data, priority);
        head = newNode;
        return;
    }
    
    // create a new node with specified data
    Node *node = new Node(data, priority);
    // find the first node having priority less than 'priority'
    Node *temp = head;
    Node *parent = NULL;
    while (temp != NULL && temp->priority >= priority) {
        parent = temp;
        temp = temp->next;
    }
    
    // Case 1 : All the nodes are having priorities less than 'priority'
    if (parent == NULL) {
        // insert the new node at the beginning of linked list
        node->next = head;
        head->prev = node;
        head = node;
    }
    // Case 2 : All the nodes are having priorities greater than 'priority'
    else if (temp == NULL) {
        // insert the node at the end of the linked list
        parent->next = node;
        node -> prev = parent;
    }
    // Case 3 : Some nodes have priority higher than 'priority' and
    // some have priority lower than 'priority'
    else {
        // insert the new node before the first node having priority
        // less than 'priority'
        parent->next = node;
        node->prev = parent;
        node->next = temp;
        temp->prev = node;
    }
}

int peek() {
    // if head is not null, return the element at first position
    if (head != NULL) {
        return head->data;
    }
    return -1;
}

int pop() {
    // if head is not null, delete the element at first position and return its value
    if (head != NULL) {
        int curr = head->data;
        head = head->next;
        if (head != NULL) {
            head->prev = NULL;
        }
        return curr;
    }
    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