시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
FIFO 방식은 대기열을 구현하는 데 사용됩니다. 대기열에서 삽입은 한쪽 끝 (후면)에서 이루어지고 삭제는 다른 쪽 끝 (앞쪽)에서 이루어집니다. 기본적으로 먼저 입력 된 요소가 먼저 삭제됩니다. C ++ 내장 함수를 사용하여 우선 순위 큐를 구현합니다.
차례
Priority Queue의 특징
- 우선 순위 변발 단순 대기열의 확장입니다.
- 우선 순위 대기열에서 요소는 FIFO를 따르지 않습니다.
- 우선 순위 요소를 기준으로 우선 순위 대기열에서 삭제됩니다.
- 우선 순위 대기열의 모든 요소에는 우선 순위가 할당됩니다.
- 해당 우선 순위에 따라 요소가 우선 순위 대기열에서 제거됩니다.
- 우선 순위가 가장 높은 요소는 항상 대기열의 맨 위에 있습니다.
- 우선 순위가 가장 낮은 요소는 항상 대기열의 가장 낮은 위치에 있습니다.
통사론
priority_queue <int> pq;
예
입력
5,1,9,7,3
산출
9,7,5,3,1
Priority Queue의 기능
C ++의 우선 순위 큐는 다양한 기능을 지원합니다. 다음은 일부 기능에 대한 설명입니다.
- push () : 큐에 요소를 삽입합니다.
- pop () : 대기열에서 우선 순위가 가장 낮은 요소를 삭제합니다.
- size () : 우선 순위 큐의 길이가 리턴됩니다.
- empty () : 우선 순위 큐가 비어 있으면 true를 반환하고 그렇지 않으면 false를 반환합니다.
- top () : 우선 순위가 가장 높은 요소가 반환됩니다.
- swap () : 요소를 비슷한 크기와 유형의 다른 우선 순위 큐에 복사합니다.
- 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) 어디에 "엔" 우선 순위 큐에있는 요소의 수입니다.
