PHP implémente la fonction de file d'attente: une méthode efficace pour optimiser les opérations de file d'attente avec deux piles

introduction

Les files d'attente sont des structures de données largement utilisées qui suivent le principe de la première entrée (FIFO). Bien que les tableaux en PHP puissent implémenter des fonctions de file d'attente, la manipulation directe des tableaux peut entraîner une réduction de l'efficacité. Cet article expliquera comment utiliser deux structures de pile pour réaliser des opérations de file d'attente efficaces et améliorer les performances du programme.

Le concept de base de la pile

La pile est une structure de données avec un dernier entrée (LIFO), et ses principales opérations incluent la poussée et la poping. Poussez l'élément sur le haut de la pile et retirez l'élément sur le haut de la pile lorsqu'il est sorti.

Idées d'implémentation de files d'attente pour deux piles

La file d'attente est implémentée via deux piles, l'une est responsable de l'élément en tant que pile d'entrée, et l'autre est responsable de la déshabitation de l'élément comme pile de sortie. Lorsque la pile de sortie est vide, les éléments de la pile d'entrée sont sortis un par un et poussés dans la pile de sortie, réalisant ainsi un comportement de file d'attente au premier entrée.

Rejoignez l'opération de file d'attente

L'opération d'entrée est relativement simple, appuyez simplement sur l'élément dans la pile d'entrée.

 class Queue {
    private $inputStack = [];
    private $outputStack = [];

    public function enqueue($item) {
        array_push($this->inputStack, $item);
    }
}

Opération de départ

L'opération de file d'attente détermine d'abord si la pile de sortie est vide. S'il est vide, alors faites apparaître tous les éléments de la pile d'entrée et poussez-les dans la pile de sortie, puis faites apparaître les éléments de la pile de sortie; S'il n'est pas vide, apparaissez directement les éléments de la pile de sortie.

 public function dequeue() {
    if (empty($this->outputStack)) {
        while (!empty($this->inputStack)) {
            array_push($this->outputStack, array_pop($this->inputStack));
        }
    }
    if (!empty($this->outputStack)) {
        return array_pop($this->outputStack);
    }
    return null;
}

Exemple de code

L'exemple suivant montre comment implémenter une opération de base d'une file d'attente à l'aide de deux piles:

 $queue = new Queue();
$queue->enqueue(1);
$queue->enqueue(2);
$queue->enqueue(3);
echo $queue->dequeue(); // Sortir1
echo $queue->dequeue(); // Sortir2
echo $queue->dequeue(); // Sortir3

Résumer

L'utilisation de deux piles pour implémenter les files d'attente peut éviter efficacement des problèmes de performances causés par un mouvement de tableau fréquent. Le fonctionnement de l'adhésion à l'équipe est simple et efficace, et la première fonctionnalité est assurée par le transfert d'éléments au départ. Bien que l'espace de pile supplémentaire soit requis, l'efficacité d'exécution globale des opérations de file d'attente est améliorée et elle convient particulièrement aux opérations de file d'attente lors du traitement de grandes quantités de données.