우선 순위 대기열

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

우선 순위 변발 일반 큐와 유사하지만 각 요소와 연관된 우선 순위가있는 데이터 구조 유형입니다. 우선 순위가 높을수록 요소가 더 빨리 게재됩니다. 경우에 따라 우선 순위가 동일한 요소가 두 개 있으며 대기열에 먼저 추가 된 요소가 먼저 제공됩니다.

예

작업 A가 작업 B보다 우선 순위가 높은 A와 B라는 두 개의 작업이 있다고 가정합니다. 작업 예약 순서는 다음과 같습니다.

1. A
2. B
3. A

다음 순서로 우선 순위 대기열이 형성됩니다.

핀

따라서 여기에서 우선 순위가 높은 작업이 우선 순위가 낮은 작업보다 먼저 할당되는 것을 볼 수 있습니다.

우선 순위 대기열 유형

1. 오름차순 우선 순위 대기열

   이 유형의 priority_queue에서는 더 낮은 우선 순위 번호가 더 높은 우선 순위의 작업에 지정됩니다.
   예 : 두 개의 작업, 즉 A와 B에 번호 1과 2가 할당 된 경우 작업 A가 우선 순위가 더 높은 경우 A에 1이 할당되고 작업 B에 2가 할당됩니다.

2. 내림차순 우선 순위 대기열

   이 유형의 priority_queue에서는 우선 순위가 더 높은 작업에 더 높은 우선 순위 번호가 지정됩니다.
   예 : 두 개의 작업, 즉 A와 B에 번호 1과 2가 할당 된 경우 작업 A가 우선 순위가 더 높은 경우 A에 2이 할당되고 작업 B에 1가 할당됩니다.

우선 순위 대기열에서 수행하는 작업

priority_queue에 의해 수행되는 기본 작업은 다음과 같습니다.

1. 삽입: 우선 순위에 따라 대기열에 항목을 삽입합니다.
2. 지우다: 대기열에서 항목을 제거합니다.
3. getHighestPriority : 가장 높은 우선 순위 요소를 제공합니다.

Priority_queue는 몇 가지 추가 작업을 지원합니다.

1. 몰래 엿보다: 대기열 앞에있는 요소를 가져옵니다.
2. 가득: 큐가 가득 찼는 지 확인합니다.
3. 비었다: 큐가 비어 있는지 확인합니다.

어플리케이션

1. CPU 스케줄링, 디스크 스케줄링 등과 같은 스케줄링에서
2. 그래프 알고리즘 (Dijkstra의 최단 경로 알고리즘, Prim의 최소 스패닝 트리 등)

실시

우선 순위 대기열은 배열, 연결 목록 등과 같은 다양한 데이터 구조를 사용하여 구현할 수 있습니다. 일부 데이터 구조는 시간 복잡성과 함께 아래에 제공됩니다.

1. 배열 (O (n * log (n)))
2. 연결된 목록 (O (n)
3. 힙 (O (log (n)))

모든 데이터 구조 중 힙 데이터 구조는 priority_queue를 구현하는 동안 최고의 시간 복잡성을 제공합니다.

참조