C ++의 우선 순위 대기열

난이도 쉽게
자주 묻는 질문 아마존 포카이트 인포시스 Microsoft 신탁
조회수 104

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

FIFO 방식은 대기열을 구현하는 데 사용됩니다. 대기열에서 삽입은 한쪽 끝 (후면)에서 이루어지고 삭제는 다른 쪽 끝 (앞쪽)에서 이루어집니다. 기본적으로 먼저 입력 된 요소가 먼저 삭제됩니다. C ++ 내장 함수를 사용하여 우선 순위 큐를 구현합니다.

Priority Queue의 특징

  1. 우선 순위 변발 단순 대기열의 확장입니다.
  2. 우선 순위 대기열에서 요소는 FIFO를 따르지 않습니다.
  3. 우선 순위 요소를 기준으로 우선 순위 대기열에서 삭제됩니다.
  4. 우선 순위 대기열의 모든 요소에는 우선 순위가 할당됩니다.
  5. 해당 우선 순위에 따라 요소가 우선 순위 대기열에서 제거됩니다.
  6. 우선 순위가 가장 높은 요소는 항상 대기열의 맨 위에 있습니다.
  7. 우선 순위가 가장 낮은 요소는 항상 대기열의 가장 낮은 위치에 있습니다.

통사론

priority_queue <int> pq;

입력

5,1,9,7,3

산출

9,7,5,3,1

 

C ++의 우선 순위 대기열

Priority Queue의 기능

C ++의 우선 순위 큐는 다양한 기능을 지원합니다. 다음은 일부 기능에 대한 설명입니다.

  1. push () : 큐에 요소를 삽입합니다.
  2. pop () : 대기열에서 우선 순위가 가장 낮은 요소를 삭제합니다.
  3. size () : 우선 순위 큐의 길이가 리턴됩니다.
  4. empty () : 우선 순위 큐가 비어 있으면 true를 반환하고 그렇지 않으면 false를 반환합니다.
  5. top () : 우선 순위가 가장 높은 요소가 반환됩니다.
  6. swap () : 요소를 비슷한 크기와 유형의 다른 우선 순위 큐에 복사합니다.
  7. emplace () : 맨 위에있는 우선 순위 대기열에 요소를 삽입합니다.

실시

우선 순위 큐 구현은 다음과 같은 다양한 데이터 구조를 사용하여 가능합니다. 정렬, 연결 목록, 또는 힙. 우선 순위 큐를 구현하는 가장 효율적이고 간단한 방법은 힙을 사용하는 것입니다. 힙은 다른 데이터 구조보다 더 나은 성능을 제공하기 때문에 다른 데이터 구조보다 선호됩니다.

C ++에서는 우선 순위 큐를 구현하는 데 쉽게 사용할 수있는 우선 순위 큐에 대한 stl 라이브러리가 제공됩니다.

#include <iostream>
#include <queue>
#include<stdlib.h>

using namespace std;

int pq_display(priority_queue <int> pq);

int main ()
{
    priority_queue <int> pq;
    int num, choice;
    cout <<" 1 - Insert an element into queue" <<endl;
    cout <<" 2 - Delete first element from queue" <<endl;
    cout <<" 3 - Display queue elements" <<endl;
    cout <<" 4 - Display highest priority queue element" <<endl;
    cout <<" 5 - Exit" <<endl;
    while (1)
    {
        cout <<endl<< "Enter your choice : ";
        cin >> choice;
        switch (choice)
        {
        case 1:
            cout << "Enter value to be inserted : ";
            cin >> num;
            pq.push(num);
            break;
        case 2:
            cout << "The first element " << pq.top() <<" has been removed from the queue" <<endl;
            pq.pop();
            break;
        case 3:
            pq_display(pq);
            break;
        case 4:
            cout <<"The highest priority element in the queue is " << pq.top() <<endl;
            break;
        case 5:
            exit(0);
        default:
            cout << "Choice is incorrect, Enter a correct choice";
        }
    }
    return 0;
}

int pq_display(priority_queue <int> pq)
{
    while (!pq.empty())
    {
        cout <<pq.top() <<'\t' ;
        pq.pop();
    }
    cout << '\n';
    return 0;
}
 1 - Insert an element into queue
 2 - Delete first element from queue
 3 - Display queue elements
 4 - Display highest priority queue element
 5 - Exit

Enter your choice : 1
Enter value to be inserted : 9

Enter your choice : 1
Enter value to be inserted : 7

Enter your choice : 1
Enter value to be inserted : 5

Enter your choice : 1
Enter value to be inserted : 3

Enter your choice : 1
Enter value to be inserted : 1

Enter your choice : 3
9       7       5       3       1

C ++를 사용한 Priority Queue의 복잡성 분석

시간 복잡성

O (N * 로그 (n)) 어디에 "엔" 수행 된 삽입 및 삭제 횟수입니다. "엔" 우선 순위 큐의 크기입니다.

공간 복잡성

O (N) 어디에 "엔" 우선 순위 큐에있는 요소의 수입니다.

참조

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