단일 연결 목록을 사용하는 우선 순위 대기열

난이도 중급
자주 묻는 질문 BrowserStack 훌루 마힌 드라 콤비 바 포켓 보석 소로코
연결된 목록 조회수 99

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

우선 변발 단독으로 사용 연결 목록 문제, 우리는 단일 연결 목록을 사용하여 우선 순위 대기열을 구현해야합니다. 우선 순위 대기열에는 다음 작업이 포함됩니다.

  1. push (x, p) : 우선 순위 큐의 적절한 위치에 우선 순위가 p 인 요소 x를 추가합니다.
  2. pop () : 우선 순위가 가장 높은 요소를 제거하고 반환
  3. peek () : 우선 순위가 가장 높은 요소를 반환합니다.

입력:
푸시 (5, 2)
푸시 (1, 3)
몰래 엿보다()
푸시 (7, 5)
푸시 (9, 1)
팝()
팝()
몰래 엿보다()
출력:
1
7
1
5

단일 연결 목록을 사용하는 우선 순위 대기열 알고리즘

아이디어는 가장 높은 우선 순위 요소가 맨 앞에 오도록 연결 목록을 우선 순위의 내림차순으로 유지하는 것입니다.

푸시 (x, p)

우선 순위의 내림차순으로 배열되어 있으므로 우선 순위가 p보다 작은 첫 번째 요소보다 우선 순위가 p 인 요소가 먼저 삽입되므로 우선 순위의 순서를 방해하지 않는다. 세 가지 경우가 발생합니다.

  1. 우선 순위가 p보다 작은 요소가 없습니다. 연결 목록 끝에 새 요소를 추가하십시오.
  2. 모든 요소의 우선 순위가 p보다 작 으면 연결 목록의 시작 부분에 새 요소를 추가합니다.
  3. 일부 요소는 p보다 낮은 우선 순위를 갖는 반면 다른 요소는 p보다 높은 우선 순위를 갖습니다. 우선 순위가 p보다 작은 첫 번째 요소 앞에 새 요소를 추가하십시오.

단일 연결 목록을 사용하는 우선 순위 대기열

시간 복잡성 = O (N)

단일 연결 목록을 사용하는 우선 순위 대기열에 대한 의사 코드

  1. data = x 및 priority = p 인 새 노드를 만들고 newNode로 둡니다.
  2. 헤드가 null 인 경우 삽입 할 첫 번째 노드이므로 head = newNode로 만들고 반환합니다.
  3. 노드 temp는 head와 같고 노드 prev는 null과 같습니다.
  4. temp가 null이 아니고 temp의 우선 순위가 p보다 큰 동안 루프를 실행하여 우선 순위가 p보다 작은 첫 번째 노드를 찾습니다. 반복 할 때마다 prev를 temp로, temp를 temp.next로 업데이트합니다.
  5. 루프 종료 후 temp가 null이면 우선 순위가 p보다 작은 노드가 없음을 의미하며, 연결 목록의 끝에 newNode를 삽입합니다. 즉, do prev.next = newNode입니다.
  6. 그렇지 않으면 prev가 null이면 모든 노드의 우선 순위가 p보다 크다는 것을 의미합니다. newNode.next = head 및 head = newNode를 수행하십시오.
  7. 그렇지 않으면 temp 앞에 새 노드를 삽입합니다. 즉, newNode.next = temp 및 prev.next = newNode를 수행합니다.

팝()

연결 목록의 앞 부분에는 우선 순위가 가장 높은 요소가 포함되어 있으며 제거하고 반환합니다.

시간 복잡성 = O (1)

몰래 엿보다()

연결 목록의 앞 부분에는 우선 순위가 가장 높은 요소가 포함되어 있습니다.

시간 복잡성 = O (1)

단일 연결 목록을 사용하는 우선 순위 대기열에 대한 JAVA 코드

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

단일 연결 목록을 사용하는 우선 순위 대기열에 대한 C ++ 코드

#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    참조 2

균열 시스템 설계 인터뷰
Translate »