우선 순위 대기열은 할당된 우선 순위에 따라 요소가 삽입되거나 삭제되는 대기열 유형입니다. 여기서 우선 순위는 0-10 사이의 정수 값입니다. 여기서 0은 우선 순위가 가장 높은 요소를 나타내고 10은 다음을 가진 요소를 나타냅니다. 가장 낮은 우선 순위. 우선 순위 대기열을 구현하기 위해 따라야 할 두 가지 규칙이 있습니다 -
- 우선순위가 가장 높은 데이터 또는 요소가 우선순위가 가장 낮은 데이터 또는 요소보다 먼저 실행됩니다.
- 두 요소가 순서대로 실행되는 것보다 우선순위가 같으면 목록에 추가됩니다.
스택, 큐 및 연결 목록과 같은 우선 순위 큐를 구현하는 데 사용할 수 있는 여러 데이터 구조가 있습니다. 이 기사에서는 큐 데이터 구조에 대해 설명합니다. 다음과 같은 우선 순위 대기열을 구현하는 데 사용할 수 있는 두 가지 방법이 있습니다. -
- 단일 배열에서 여러 우선순위에 대한 대기열 유지
우선순위 큐를 구현하는 한 가지 방법은 각 우선순위에 대한 큐를 유지하는 것입니다. 이러한 여러 대기열을 단일 배열에 저장할 수 있습니다. 여기서 각 대기열에는 두 개의 포인터, 즉 전면과 후면이 있습니다. 대기열에서 Front 포인터는 요소를 대기열에 삽입하는 데 사용되며 요소가 삽입될 때마다 1씩 증가하고 대기열에서 요소를 삭제하거나 제거하는 데 사용되는 다른 포인터가 뒤에 있는 다른 포인터는 요소가 추가될 때마다 1씩 감소합니다. 대기열에서 제거됩니다. 결국 두 포인터의 위치를 통해 대기열의 요소 수를 결정할 수도 있습니다.
- 이러한 유형의 표현에서는 포인터를 이동하여 새로운 요소를 삽입할 공간을 만들어야 합니다. 그러면 시간과 공간 모두에서 복잡해집니다.
- 단일 배열에서 각 우선순위에 대한 대기열 유지
이 유형의 방법에서는 각 요소에 대해 별도의 화살표를 만듭니다. 모든 큐는 순환 배열로 구현되며 두 개의 포인터 변수가 있습니다. 전면 및 후면. 우선 순위 번호가 부여된 요소는 해당 대기열에 삽입됩니다. 마찬가지로 대기열에서 요소를 삭제하려면 우선 순위가 가장 높은 대기열의 요소여야 합니다. 가장 낮은 우선순위 정수는 가장 높은 우선순위(0)를 나타냅니다.
참고 - 각 큐의 크기가 같으면 1차원 배열을 여러 개 생성하는 대신 단일 2차원 배열을 생성할 수 있습니다.
우선순위 큐에 작업 삽입을 위한 알고리즘
insert(queue, data, priority) If(queue->Rear[priority] = MAX-1 AND queue->Front[priority] = 0) OR (queue->Rear[priority] +1 =queue->Front[priority]) Print Overflow End IF queue->Rear[priority - 1] = MAX-1 Set queue->Rear[priority - 1] = 0 Else Set queue->Rear[priority] = queue->Rear[priority - 1] +1 End Set queue->CQueue[priority - 1] [queue->Rear[priority - 1] = data IF queue->Front[priority - 1] = -1 Set queue->Front[priority - 1] = 0 End
우선순위 큐에 작업 삽입을 위한 알고리즘
delete(queue) Set flag = 0, priority = 0 While priority <= MAX-1 IF NOT queue->Front[priority] = -1 Set flag = 1 Set value = queue->CQueue[priority][queue->Front[priority]] IF queue->Front[priority] = queue->Rear[priority] Set queue->Front[priority] = queue->Rear[priority] = -1 Else IF queue->Front[priority] = MAX-1 Set queue->Front[priority] = 0 Else Set queue->Front[priority] = queue->Front[priority] + 1 End End Break End Set priority = priority + End If flag = 0 Print underflow Else Return value End