C#의 우선 순위 대기열

Minahil Noor 2023년10월12일

Csharp

이 문서에서는 C#에 해당하는 우선 순위 대기열을 소개합니다.

`목록`을 C#의 우선 순위 대기열로 사용

C#에는 우선 순위 큐에 대한 특수 클래스가 없습니다. 하지만 배열과 목록을 사용하여 구현할 수 있습니다. 목록 데이터 구조를 사용하여 우선 순위 대기열을 구현합니다. 우선 순위 큐는 요소와 연관된 우선 순위가있는 추상 데이터 유형입니다. 목록은 항상 최우선 순위가 가장 높은 방식으로 생성됩니다. 목록을 사용하여 우선 순위 큐를 구현하는 알고리즘은 다음과 같습니다.

PUSH(HEAD, VALUE, PRIORITY)
Step 1 : Create a new node with VALUE and PRIORITY Step 2
    : Check if HEAD has lower priority.If true follow Steps 3 -
    4 and end.Else goto Step 5. Step 3 : NEW->NEXT = HEAD Step 4 : HEAD = NEW Step 5
    : Set TEMP to head of the list Step 6
    : While TEMP->NEXT != NULL and TEMP->NEXT->PRIORITY > PRIORITY Step 7
    : TEMP = TEMP->NEXT[END OF LOOP] Step 8 : NEW->NEXT = TEMP->NEXT Step 9
    : TEMP->NEXT = NEW Step 10 : End POP(HEAD) Step 2
    : Set the head of the list to the next node in the list.HEAD = HEAD->NEXT.Step 3
    : Free the node at the head of the list Step 4 : End TOP(HEAD)
    : Step 1 : Return HEAD->VALUE Step 2 : End

푸시 작업은 우선 순위가 가장 높은 요소가 항상 맨 위에 있도록 우선 순위 대기열에 요소를 추가합니다. 팝 작업은 대기열에서 우선 순위가 가장 높은 요소를 제거합니다. 최상위 작업은 제거하지 않고 우선 순위가 가장 높은 요소를 검색합니다. 아래 프로그램은 우선 순위 큐에서 요소를 푸시, 팝 및 상위 요소로 만드는 방법을 보여줍니다.

using System;

class PriorityQueue {
  public class Node {
    public int data;
    public int priority;
    public Node next;
  }

  public static Node node = new Node();

  public static Node newNode(int d, int p) {
    Node temp = new Node();
    temp.data = d;
    temp.priority = p;
    temp.next = null;
    return temp;
  }

  public static int top(Node head) {
    return (head).data;
  }

  public static Node pop(Node head) {
    Node temp = head;
    (head) = (head).next;
    return head;
  }

  public static Node push(Node head, int d, int p) {
    Node start = (head);
    Node temp = newNode(d, p);
    if ((head).priority > p) {
      temp.next = head;
      (head) = temp;
    } else {
      while (start.next != null && start.next.priority < p) {
        start = start.next;
      }
      temp.next = start.next;
      start.next = temp;
    }
    return head;
  }
  public static int isEmpty(Node head) {
    return ((head) == null) ? 1 : 0;
  }
  public static void Main(string[] args) {
    Node queue = newNode(1, 1);
    queue = push(queue, 9, 2);
    queue = push(queue, 7, 3);
    queue = push(queue, 3, 0);

    while (isEmpty(queue) == 0) {
      Console.Write("{0:D} ", top(queue));
      queue = pop(queue);
    }
  }
}

출력:

3 1 9 7

priority값이 낮은 요소가 더 높은 우선 순위를 갖습니다.

목록을 C#의 우선 순위 대기열로 사용

`목록`을 C#의 우선 순위 대기열로 사용