PHP implémente les files d'attente de la liste liée: utilisez des pointeurs de queue pour implémenter les files d'attente du premier entrée

Qu'est-ce qu'une file d'attente de liste liée

Une file d'attente est une structure de données de première entrée (FIFO) qui permet d'ajouter uniquement des éléments à la fin de l'équipe et des éléments d'être supprimés à la fin de l'équipe. Une file d'attente de chaîne est une structure de file d'attente implémentée via une liste liée, qui peut étendre dynamiquement la taille de la file d'attente. Les files d'attente de chaîne sont largement utilisées dans de nombreux scénarios où des fonctionnalités de premier ordre sont nécessaires.

Implémentation de file d'attente liée

Une file d'attente de liste liée est implémentée à l'aide d'une structure de liste liée. Le nœud de liste lié contient deux parties: un domaine de données et un domaine de pointeur. Le champ de pointeur pointe vers le nœud de liste lié suivant. L'implémentation d'une file d'attente dépend des pointeurs de tête et de queue, que les pointeurs pointent vers le premier élément de la file d'attente, et le pointeur de queue pointe vers le dernier élément.

Définition du nœud de liste liée

Un nœud de liste lié se compose de deux parties: un domaine de données et un domaine de pointeur, et le domaine du pointeur pointe vers le nœud suivant. Ce qui suit est le code pour PHP pour implémenter les nœuds de liste liés:

 
class Node {
    public $data;
    public $next;
}

Définition de la file d'attente

La définition de la file d'attente comprend deux pointeurs: la tête et la queue de l'équipe. Le pointeur de queue pointe vers le dernier élément de la file d'attente et le pointeur de tête pointe vers le premier élément. La longueur de la file d'attente augmente avec l'ajout d'éléments. Ce qui suit est le code d'implémentation de la file d'attente dans PHP:

 
class Queue {
    private $head;
    private $tail;

    public function __construct() {
        $this->head = null;
        $this->tail = null;
    }

    public function isEmpty() {
        return $this->head === null;
    }

    public function enqueue($data) {
        $newNode = new Node();
        $newNode->data = $data;
        $newNode->next = null;

        if ($this->isEmpty()) {
            $this->head = $this->tail = $newNode;
        } else {
            $this->tail->next = $newNode;
            $this->tail = $newNode;
        }
    }

    public function dequeue() {
        if ($this->isEmpty()) {
            return null;
        }

        $data = $this->head->data;
        $this->head = $this->head->next;

        if ($this->head === null) {
            $this->tail = null;
        }

        return $data;
    }
}

Utiliser des scénarios

Les files d'attente de liste liée sont souvent utilisées dans les scénarios suivants:

• Algorithme de recherche de largeur (BFS)
• Allocation de tâches de pool de threads
• File d'attente d'impression, etc.

Résumer

Les files d'attente de liste liée sont un moyen courant d'implémenter les structures de données de première entrée (FIFO) et conviennent à de nombreux scénarios où les tâches doivent être traitées en séquence. Grâce à la flexibilité des listes liées, les files d'attente peuvent être étendues dynamiquement pour répondre à divers besoins d'application. L'implémentation des files d'attente de liste liée est non seulement simple et efficace, mais est un outil indispensable dans la programmation.