우선 대기열! 이를 분해하여 데이터 구조의 이 부분에 대해 알아 보겠습니다.-java지도 시간-php.cn

Priority Queue! Vamos destrinchar e aprender sobre essa parte de Estrutura de Dados.

대기줄

스택과 마찬가지로 대기열은 목록의 전문화입니다. 이는 FIFO 기반(선입선출)을 기반으로 합니다. 즉, 선입선출이 먼저임을 의미합니다. 즉, 대기열에서 "가장 나이가 많은" 사람이 먼저 떠나는 것이며, 더 나은 이해를 위해 은행 대기열을 고려해보세요.

⚠️

큐 애플리케이션: 운영 체제의 프로세스 관리; 동시 프로그래밍의 작업 간 통신 컴퓨터 네트워크(인쇄); 웹 서버의 요청에 대한 응답

큐 자체는 끝 부분에서만 데이터를 직접 조작할 수 있습니다.

public interface Queue<E> {
    void enqueue(E value); //enfileira
    E dequeue(); //remove e desenfileira
    E first(); //retorna primeiro elemento
    int size(); //algumas literaturas se chama lenght()
    boolean isEmpty();
}

로그인 후 복사

우선순위 대기열

일반적인 일상 대기열의 행동과 유사하지만 이제 은행에서 줄을 서고 여성이 대기열에 들어간다고 생각해보세요. 나이가 많을수록 우선순위가 더 높기 때문에 모두가 그녀를 먼저 놔줍니다.

우선순위 큐 데이터 구조에서 각 노드는 키-값을 가지며, 키는 우선순위를 저장하는 키, 값은 노드의 값입니다. Java 기본적으로 키는 처음에는 숫자이며 나중에 프로그래머가 변경할 수 있습니다.

Key와 Value의 집합을 Entry라고 하여 이 E.D의 인터페이스가 변경됩니다. 기타 세부 사항은 다음과 같습니다. 키를 정의한 후에는 변경할 수 없습니다. 두 노드가 키에 동일한 우선순위 값을 갖는 경우 프로그래머는 규칙을 선택합니다.

public interface PriorityQueueOg<K,V> {
    void insert(K key, V value);
    Entry<K,V> remove();
    int size();
    boolean isEmpty();
}

로그인 후 복사

다음 구조에서는 노드 및 항목, 첫 번째, 마지막 및 크기 속성, 그리고 CompareTo에 대한 클래스를 사용합니다

우선순위 큐는 정렬된(Sorted Priority Queue)과 정렬되지 않은(Unorted Priority Queue) 두 가지로 나누어집니다

정렬된 우선순위 대기열

정렬된 목록은 노드를 올바른 위치에 삽입하므로 제거가 쉽습니다. 첫 번째 노드만 제거하면 됩니다(ED를 수행하는 프로그래머가 우선 순위가 가장 높은 요소가 시작 부분에 있어야 한다고 정의한 경우)

어느 노드가 가장 높은 우선순위를 가지고 있는지 확인하기 위해 반환을 통해 이 E.D 실행에 대한 중요한 결과를 얻을 수 있는 컬렉션 함수인 CompareTo를 사용합니다.

부정적: 메소드를 호출하는 객체가 매개변수로 전달된 객체보다 "작은" 경우
0: 개체가 동일한 경우
긍정: 메소드를 호출하는 객체가 매개변수로 전달된 객체보다 "큰" 경우.

끼워 넣다

참가하려면 몇 가지 사항을 확인해야 합니다

1단계 → 새 노드 생성

Node newNode = new Node(key, value)

로그인 후 복사

2단계 → Queue가 비어 있는지 확인하고, 그렇다면 유일한 노드가 될 것이라는 점을 고려하여 Head와 Last를 새 노드로 배치합니다

public interface Queue<E> {
    void enqueue(E value); //enfileira
    E dequeue(); //remove e desenfileira
    E first(); //retorna primeiro elemento
    int size(); //algumas literaturas se chama lenght()
    boolean isEmpty();
}

로그인 후 복사

3단계 → 목록의 유일한 요소가 아닌 경우 새 노드가 첫 번째 노드에 비해 우선순위가 높은지 여부를 확인해야 합니다.

public interface PriorityQueueOg<K,V> {
    void insert(K key, V value);
    Entry<K,V> remove();
    int size();
    boolean isEmpty();
}

로그인 후 복사

3단계 → 목록의 마지막 요소와 비교

Node newNode = new Node(key, value)

로그인 후 복사

4단계 → 다 안되면 중간만 남습니다! 이를 위해서는 newNode(nN) 앞으로 갈 보조 노드를 만들고 두 노드를 비교해야 합니다. auxNode가 아무 것도 가리키지 않거나 nN이 auxNode보다 클 때(더 크므로 비교는 종료됩니다) 줄이 늦었습니다.) 이 while은 aux가 두 노드의 값을 비교하고 이를 찾으면 auxNode 뒤에 nN을 배치하는 데 사용됩니다

        if(isEmpty()){
            first = newNode;
            last = newNode;
        }else{

로그인 후 복사

제거하다

Sorted의 제거 방법은 이미 언급했듯이 대기열이 이미 구성되어 있기 때문에 훨씬 간단합니다.

첫 번째 단계 → 모든 제거 메소드는 제거할 요소를 반환하므로 항목을 생성하는 단계가 됩니다(왜 노드가 아닌가?)

         if(compare(newNode, first)<0){
                 //Se o nN for menor que o F
                 //Levando em consideração que a prioridade maior é 0
                 //Se o nN for menor que F, ele será o de maior prioridade pegando o lugar do primeiro
                newNode.next = first;
                first.previous = newNode;
                first = newNode;
          }

로그인 후 복사

2단계 → 그런 다음 이미 첫 번째 노드를 제거할 예정이므로 First 옆에 있는 노드를 First로 지정하세요

             }else if(compare(newNode, last)>=0){
           //Se o nN for maior que o L
           //Significa que o número de nN é maior que L
           //Então bota o nN para ultimo
                newNode.previous=last;
                last.next=newNode;
                last = newNode;
            }else{

로그인 후 복사

3단계 → 대기열에 요소가 하나만 있는지 확인하세요. 그렇다면 대기열이 비어 있기 때문입니다! 그런 다음 F와 L을 null로 설정해야 합니다

            }else{
                //se nao for nada, está no meio
                //entao temos que achar entre qual dos meios
                Node auxNode = first;
                while(compare(newNode, auxNode)>0 && auxNode.next!=null){
                    //enquanto o newNode tiver prioridade maior que o auxiliar
                    //e o auxiliar tiver um proximo
                    auxNode = auxNode.next;
                }
                newNode.next = auxNode;
                newNode.previous = auxNode.previous;
            }
        }

로그인 후 복사

4단계 → 유일한 요소가 아니라면 다른 요소도 있다는 뜻입니다! 따라서 2단계에서 첫 번째 항목을 제거하면 이전에 First였던 항목이 여전히 이전 항목에 의해 연결되어 있으므로 다음을 수행해야 합니다.

        Entry<K,V> max = maxPriority();

로그인 후 복사

최대 우선순위

목록에서 우선순위가 가장 높은 요소를 반환하는 메서드이며, 순서가 있으므로 첫 번째 요소만 반환합니다.

        first = first.next;

로그인 후 복사

점근적 분석

Método	O(_)
size	O(1)
isEmpty	O(1)
insert	O(n)
remove	O(1)
maxPriority	O(1)

정렬되지 않은 우선순위 대기열

무질서한 대기열은 주문한 대기열과 매우 다릅니다! 그의 방법부터 시작해 보겠습니다.

끼워 넣다

정렬되지 않음, 좋아요, 무질서에 추가하려면 이 새 요소가 어디에 있을지 걱정할 필요 없이 마지막에 추가하기만 하면 됩니다!

1단계 → 목록이 비어 있는지 확인합니다. 비어 있으면 추가할 노드가 첫 번째(First)와 마지막(Last)이 되기 때문입니다

public interface Queue<E> {
    void enqueue(E value); //enfileira
    E dequeue(); //remove e desenfileira
    E first(); //retorna primeiro elemento
    int size(); //algumas literaturas se chama lenght()
    boolean isEmpty();
}

로그인 후 복사

2단계 → 비어 있지 않으면 마지막에 이 노드를 추가하는 것만 신경쓰시면 됩니다!

public interface PriorityQueueOg<K,V> {
    void insert(K key, V value);
    Entry<K,V> remove();
    int size();
    boolean isEmpty();
}

로그인 후 복사

최대 우선순위

Unsorted에서 제거는 Sorted의 단순한 코드 줄보다 훨씬 더 복잡합니다…

“왜요?” 당신이 묻는다면, 우리는 maxPriority라는 메소드(다른 버전에서도 훨씬 간단했습니다)를 사용해야 합니다. 이 메소드의 목표는 가장 높은 우선순위를 가진 노드를 찾는 것입니다. 이전에는 단 몇 줄의 코드만으로 간단한 방식으로 가르쳤지만 이제는 우선순위가 가장 높은 노드가 실제로 어디에 있는지 모르기 때문에 이를 찾기 위해 전체 대기열을 통과해야 합니다! 따라서 제거 자체를 살펴보기 전에 maxPriority를 살펴보겠습니다.

첫 번째 단계 → 데이터 구조를 순회할 때마다 두 개의 노드가 필요합니다. 즉, 항상 진행되는 보조 노드와 달성하려는 노드(이 경우 MaxPriority)

Node newNode = new Node(key, value)

로그인 후 복사

2단계 → 이 두 개는 노드 내에서 실행되며 aux가 null(큐의 끝)에 도달할 때만 종료됩니다. 이들 노드를 비교하여 음수이면 aux가 max보다 작으므로 max가 가장 크다는 뜻이고, max node의 값을 업데이트한 후 aux를 실행하게 합니다.

        if(isEmpty()){
            first = newNode;
            last = newNode;
        }else{

로그인 후 복사

제거하다

1단계 → 모든 emove에서 제거할 노드를 저장할 변수를 만듭니다. 이 경우 maxPriority
메소드를 호출하기 때문에 어느 것이 제거될지 이미 알고 있습니다.

         if(compare(newNode, first)<0){
                 //Se o nN for menor que o F
                 //Levando em consideração que a prioridade maior é 0
                 //Se o nN for menor que F, ele será o de maior prioridade pegando o lugar do primeiro
                newNode.next = first;
                first.previous = newNode;
                first = newNode;
          }

로그인 후 복사

2단계 → 그런 다음 그것이 유일한 요소인지 확인하십시오. 그렇다면 F와 L은 null입니다!

             }else if(compare(newNode, last)>=0){
           //Se o nN for maior que o L
           //Significa que o número de nN é maior que L
           //Então bota o nN para ultimo
                newNode.previous=last;
                last.next=newNode;
                last = newNode;
            }else{

로그인 후 복사

3단계 → 유일한 것이 아니면 다른 옵션이 있습니다. max가 마지막이면 마지막을 제거하고, 첫 번째라면 첫 번째를 제거하고, 둘 중 하나도 아니면, 안에 있습니다. 가운데!

            }else{
                //se nao for nada, está no meio
                //entao temos que achar entre qual dos meios
                Node auxNode = first;
                while(compare(newNode, auxNode)>0 && auxNode.next!=null){
                    //enquanto o newNode tiver prioridade maior que o auxiliar
                    //e o auxiliar tiver um proximo
                    auxNode = auxNode.next;
                }
                newNode.next = auxNode;
                newNode.previous = auxNode.previous;
            }
        }

로그인 후 복사

4단계 → 중간에 있으면 군중 속에 있는 max를 제거해야 하며, 이는 아무도 지적하지 않을 때 발생합니다.