File d'attente prioritaire ! Décomposons-le et découvrons cette partie de la structure des données.

File d'attente

La Queue, comme la Stack, est une spécialisation de la List. Il est basé sur la base FIFO – premier entré, premier sorti, ce qui signifie que le premier entré est le premier sorti. Autrement dit, la personne « la plus âgée » de la file d'attente part en premier, pour une meilleure compréhension, considérons une file d'attente bancaire.

⚠️

Applications de file d'attente : gestion des processus dans les systèmes d'exploitation ; Communication entre tâches en programmation concurrente ; réseaux informatiques (impression); réponse à des requêtes sur un serveur Web

Les files d'attente elles-mêmes permettent uniquement la manipulation directe des données aux extrémités.

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();
}

File d'attente prioritaire

Cela ressemble au comportement d'une file d'attente quotidienne courante, mais considérez maintenant que vous faites la queue dans une banque et qu'une dame entre dans la file d'attente, tout le monde la laisse avancer car elle a une plus grande PRIORITÉ car elle est plus âgée.

Dans la structure de données de la file d'attente prioritaire, chaque nœud a une clé-valeur, Key est la clé qui stocke sa priorité, Value est la valeur du nœud. Par défaut Java, la clé est initialement numérique et peut être modifiée ultérieurement par le programmeur.

L'ensemble d'une clé et d'une valeur est appelé Entry, donc l'interface de cet E.D change. Les autres détails sont les suivants : une fois la clé définie, elle ne peut pas être modifiée. Si deux nœuds ont la même valeur de priorité dans la Clé, le programmeur choisit la règle.

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

Dans les prochaines structures, nous utiliserons les classes pour les attributs Node et Entry, first, last et size, et compareTo

La file d'attente prioritaire est divisée en deux : les triés (File d'attente prioritaire triée) et les non triés (File d'attente prioritaire non triée)

File d'attente prioritaire triée

La liste ordonnée se charge d'insérer le nœud dans la bonne position, donc la suppression est facile, il suffit de supprimer le premier (si le programmeur effectuant l'E.D définit que l'élément la plus prioritaire doit être au début)

Pour savoir quel nœud a la priorité la plus élevée, nous utilisons compareTo, une fonction Collections qui, grâce à son retour, nous pouvons obtenir des résultats cruciaux pour l'exécution de cet E.D, si le retour est :

• Négatif : Si l'objet qui appelle la méthode est "plus petit" que l'objet passé en paramètre.
• Zéro : Si les objets sont égaux.
• Positif : Si l'objet qui appelle la méthode est "plus grand" que l'objet passé en paramètre.

Insérer

Pour participer, vous devez vérifier quelques éléments

1ère étape → Créer un nouveau nœud

Node newNode = new Node(key, value)

2ème étape → Vérifiez si la File d'attente est vide, si c'est le cas, placez le Head et le Last comme nouveau nœud, en considérant qu'il sera le seul

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ème étape → S'il n'est pas le seul élément de la liste, vous devez vérifier si le nouveau nœud, par rapport au premier, a une priorité plus élevée ou non.

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

3ème étape → Puis comparer avec le dernier élément de la liste

Node newNode = new Node(key, value)

4ème étape → Sinon tout le reste, il ne reste que le milieu ! Pour ce faire, il faut créer un nœud auxiliaire pour passer devant le newNode (nN) et comparer les deux, la comparaison se termine lorsque le auxNode ne pointe vers rien, ou lorsque le nN est supérieur au auxNode (plus grand, donc il est en retard dans la file). Ce while sert à l'aux pour faire le tour et comparer la valeur des deux noeuds, quand il le trouve, il place le nN derrière l'auxNode

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

Retirer

La méthode de suppression dans Sorted est beaucoup plus simple car, comme déjà mentionné, la file d'attente est déjà organisée pour cela.

1ère étape → Comme chaque méthode Remove renvoie l'élément qu'elle va supprimer, l'étape sera de créer une entrée (Pourquoi pas un nœud ?)

         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ème étape → Ensuite, comme vous allez déjà éliminer le premier nœud, il suffit de pointer First sur celui à côté de 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ème étape → Vérifiez s'il n'y a qu'un seul élément dans la File d'attente, car si c'est le cas, la File d'attente sera vide ! Ensuite vous devrez mettre F et 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ème étape → Si ce n'est pas le seul élément, c'est qu'il y en a d'autres ! Ainsi, lorsque vous supprimez le premier à l'étape 2, ce qui était auparavant Premier est toujours là étant connecté par le précédent, il faut donc :

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

PrioritéMax

Méthode qui renvoie l'élément le plus prioritaire de la liste, et comme nous sommes dans l'ordre, elle ne renvoie que le premier.

        first = first.next;

Analyse asymptotique

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

File d'attente prioritaire non triée

La file d'attente désordonnée est très différente de celle ordonnée ! Commençons par ses méthodes :

Insérer

Pour ajouter des éléments non triés, semblables et désordonnés, vous n'avez pas à vous soucier de l'endroit où sera ce nouvel élément, ajoutez-le simplement à la fin !

1ère étape → Vérifiez si la liste est vide, car si c'est le cas, le nœud à ajouter sera le premier (Premier) et le dernier (Dernier)

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ème étape → s'il n'est pas vide, pensez simplement à ajouter ce nœud à la fin !

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

PrioritéMax

Supprimer dans Non trié est beaucoup plus complexe que les maigres lignes de code dans Trié…

« Pourquoi ? » demandez-vous, nous devrions utiliser une méthode (qui dans l'autre version était également beaucoup plus simple) appelée maxPriority, dont l'objectif est de trouver le nœud avec la priorité la plus élevée. Auparavant, cela était enseigné de manière simple avec seulement quelques lignes de code, maintenant, comme nous ne savons pas où se trouve réellement ce nœud la plus prioritaire, nous devons parcourir toute la file d'attente à sa recherche ! Donc, avant d'envisager la suppression elle-même, nous examinerons maxPriority.

1ère étape → Chaque fois que nous voulons parcourir une structure de données, nous avons besoin de deux nœuds : un nœud auxiliaire pour toujours avancer, et celui que nous voulons atteindre (qui dans ce cas est MaxPriority)

Node newNode = new Node(key, value)

2ème étape → Ces deux-là s'exécuteront au sein d'un nœud, cela ne se terminera que lorsque l'aux atteint null (fin de la file d'attente). Comparez ces nœuds et s'il est négatif, cela signifie que l'aux est plus petit que le max, donc le max est le plus grand, mettant à jour la valeur du nœud max, puis faisant exécuter l'aux.

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

Retirer

1ère étape → Dans toutes les emoves, créez une variable qui stockera le nœud qui sera supprimé. Dans ce cas, vous savez déjà lequel sera supprimé car vous appelez la méthode 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ème étape → Vérifiez ensuite si c'est le seul élément, si oui, F et L sont nuls !

             }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ème étape → Si ce n'est pas le seul, il y a d'autres options : si le max est le dernier, éliminez le dernier, si c'est le premier, éliminez le premier, si ce n'est ni deux deux, il est dans le milieu !

            }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ème étape → S'il est au milieu, il faudra supprimer le max qui est dans la foule, cela se produit lorsque personne d'autre ne le pointe.

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

Analyse asymptotique

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!