Tək Bağlı Siyahıdan istifadə etmək üçün növbə

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur BrowserStack Hulu Mahindra Comviva Cib daşları Soroko
Bağlı siyahı QueueBaxılıb 99

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Prioritet olaraq queue tək istifadə əlaqəli siyahı problem, bir-birinə bağlı bir siyahı istifadə edərək prioritet növbə tətbiq etməliyik. Prioritet növbə aşağıdakı əməliyyatları ehtiva edir,

  1. push (x, p): Prioritet növbəsində uyğun bir mövqedə prioritet p ilə x elementi əlavə edin.
  2. pop (): Ən yüksək prioritetli elementi çıxarın və qaytarın
  3. peek (): Ən yüksək prioritetli elementi qaytarın

misal

Input:
itələmək (5, 2)
itələmək (1, 3)
nəzər ()
itələmək (7, 5)
itələmək (9, 1)
pop ()
pop ()
nəzər ()
Çıxış:
1
7
1
5

Tək əlaqəli siyahıdan istifadə edərək prioritet növbə üçün alqoritm

Fikir, ən yüksək prioritet elementinin ön tərəfdə olması üçün bağlı siyahını prioritet azalan qaydada saxlamaqdır.

basmaq (x, p)

Elementlər prioritetlərin azalan sırası ilə yerləşdiyindən prioritetlərin pozulmaması üçün prioritet p olan bir element birinci elementin qarşısına p-dən az prioritet qoyulur. Üç hal yaranır,

  1. Prioriteti p-dən az olan heç bir element yoxdur, əlaqəli siyahının sonunda yeni element əlavə edin.
  2. Bütün elementlərin prioriteti p-dən azdır, əlaqəli siyahının əvvəlində yeni element əlavə edin.
  3. Bəzi elementlərin prioriteti p-dən az, digərlərinin isə p-dən çox olması, p-dən az prioriteti olan birinci elementdən əvvəl yeni element əlavə edin.

Tək Bağlı Siyahıdan istifadə etmək üçün növbəPin

Zaman Mürəkkəbliyi = O (n)

Tək əlaqəli siyahıdan istifadə etmək üçün prioritet növbə üçün yalançı kod

  1. Data = x və prioritet = p olan yeni bir qovşaq edin, qoy yeniNode olsun
  2. Baş boşdursa, bu daxil ediləcək ilk düyündür, buna görə head = newNode düzəldin və qayıdın.
  3. Bir node temp başına bərabərdir və bir node əvvəl null bərabərdir.
  4. Temp sıfır deyil və tempin prioriteti p-dən böyük olduğu dövrü işə salmaqla prioriteti p-dən az olan ilk nodu tapın. Hər təkrarlamada temp.next kimi temp və temp kimi əvvəlcədən yeniləyin.
  5. Döngünün bitməsindən sonra temp sıfırsa, p-dən az prioritetli bir qovşaq yoxdur deməkdir, əlaqəli siyahının sonuna newNode əlavə edin, yəni prev.next = newNode edin.
  6. Əks təqdirdə əvvəlcədən sıfır olduqda, bu, bütün qovşaqların p-dən böyük bir prioritetə ​​malik olduğunu göstərir. NewNode.next = head və head = newNode edin.
  7. Başqa bir vəziyyətdə, tempdən əvvəl yeni nodu əlavə edin, yəni newNode.next = temp və prev.next = newNode edin.

pop ()

Bağlı siyahının ön hissəsi ən yüksək prioritet elementini ehtiva edir, silin və qayıdın.

Zaman Mürəkkəbliyi = O (1)

nəzər ()

Bağlı siyahının ön hissəsi ən yüksək prioritet elementini ehtiva edir, geri qaytarın.

Zaman Mürəkkəbliyi = O (1)

Tək əlaqəli siyahıdan istifadə edərək prioritet növbə üçün JAVA kodu

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

Tək Bağlı Siyahıdan istifadə edərək prioritet növbə üçün C ++ kodu

#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

İstinad1    arayış2

Crack Sistemi Dizayn Müsahibələri
Translate »