Explication détaillée des files d'attente en php

Aujourd'hui, nous allons apprendre un autre type de structure logique très classique : la file d'attente. Je pense que de nombreux étudiants ont déjà utilisé des outils de file d'attente de cache tels que Redis et RabbitMq. En fait, les bases de données et les codes de programme peuvent tous implémenter des opérations de file d'attente. Tout comme les piles, les files d'attente ont également leurs propres règles spécifiques. Tant qu'elles respectent ces règles, cela s'appelle une file d'attente.

Qu'est-ce qu'une file d'attente ?

Par rapport à la pile, la file d'attente est une structure logique séquentielle premier entré, premier sorti (FIFO). Qu'est-ce qui est premier entré, premier sorti ? Tout comme notre file d'attente, lorsque nous allons à la banque ou à l'hôpital, nous devons toujours prendre un numéro à la porte, et ce numéro est appelé dans l'ordre. La personne qui arrive en premier peut faire des affaires ou consulter un médecin en premier. Il s'agit d'une file d'attente typique. De la même manière, la file d'attente quotidienne est un mode de file d'attente standard.

S'il y a quelqu'un qui saute la file d'attente, nous pouvons le considérer comme ayant une priorité plus élevée s'il y a une raison légitime. Il s'agit d'une forme particulière d'éléments dans la file d'attente. Tout comme nous donnons la priorité aux femmes enceintes lorsqu'elles attendent le métro ou le bus, il existe également un guichet prioritaire pour les militaires lorsqu'ils font la queue pour acheter des billets de train. Cependant, cela sort cette fois du cadre de notre discussion.

Lorsque vous faites la queue à un arrêt de bus, bien sûr, la première personne en file peut monter dans le bus en premier, et ainsi de suite. A ce moment-là, vous arrivez à l'arrêt de bus, vous ne pouvez alors être que le dernier dans la file. C'est la manifestation spécifique de la file d'attente.

De même, comme les piles, il y a certains noms que nous devons comprendre. Lorsque vous arrivez à un arrêt de bus et que vous êtes le dernier dans la file, cette opération s'appelle « rejoindre la file d'attente ». Lorsque le bus entre en gare et que le premier passager monte dans le bus, cette opération est appelée « sortie ». La position du premier passager est appelée « tête de file d'attente ». En tant que dernier passager dans la file d'attente actuelle, votre position est appelée « queue de file d'attente ». Pour en revenir à la logique du code, c'est-à-dire que la file d'attente "entre" par la "queue" et "sort" par la "tête".

Sequential Queue

OK, regardons directement le code. La première chose que nous voyons est toujours l'implémentation de la file d'attente séquentielle.

class SqQueue{
    public $data;
    public $front;
    public $rear;
}

Comme il s'agit d'une équipe séquentielle, nous utilisons toujours un tableau de données pour représenter les éléments de l'équipe. Définissez ensuite deux pointeurs avant et arrière pour représenter la tête et la queue de l'équipe. Puisqu'il s'agit d'une file d'attente séquentielle, le pointeur stocke ici l'indice du tableau. L'opération suivante est en fait très simple, Rear++ est utilisé lors de "l'entrée dans la file d'attente", et front++ est utilisé lors de la "sortie de la file d'attente".

function InitSqQueue(){
    $queue = new SqQueue();
    $queue->data = [];
    $queue->front = 0;
    $queue->rear = 0;
    return $queue;
}

function EnSqQueue(SqQueue &$queue, $e){
    $queue->data[$queue->rear] = $e;
    $queue->rear ++;
}

function DeSqQueue(SqQueue &$queue){
    // 队列为空
    if($queue->front == $queue->rear){
        return false;
    }
    $e = $queue->data[$queue->front];
    $queue->front++;
    return $e;
}

$q = InitSqQueue();
EnSqQueue($q, 'A');
EnSqQueue($q, 'B');
print_r($q);
// SqQueue Object
// (
//     [data] => Array
//         (
//             [0] => A
//             [1] => B
//         )

//     [front] => 0
//     [rear] => 2
// )

Pensez-vous qu'après avoir appris la pile, la file d'attente est également facile à comprendre. Lors de l'initialisation de la file d'attente, définissez simplement les pointeurs de tête et de queue sur les enregistrements avec 0 indice. Lorsque vous rejoignez la file d'attente, laissez la queue de la file d'attente augmenter. Dans ce code, nous joignons deux éléments dans la file d'attente, et le contenu de la file d'attente séquentielle imprimé est tel qu'indiqué dans les commentaires.

EnSqQueue($q, 'C');
EnSqQueue($q, 'D');
EnSqQueue($q, 'E');
print_r($q);
// SqQueue Object
// (
//     [data] => Array
//         (
//             [0] => A
//             [1] => B
//             [2] => C
//             [3] => D
//             [4] => E
//         )

//     [front] => 0
//     [rear] => 5
// )

echo DeSqQueue($q), PHP_EOL; // A
echo DeSqQueue($q), PHP_EOL; // B
echo DeSqQueue($q), PHP_EOL; // C
echo DeSqQueue($q), PHP_EOL; // D
echo DeSqQueue($q), PHP_EOL; // E

echo DeSqQueue($q), PHP_EOL; // 

print_r($q);
// SqQueue Object
// (
//     [data] => Array
//         (
//             [0] => A
//             [1] => B
//             [2] => C
//             [3] => D
//             [4] => E 
//         )

//     [front] => 5
//     [rear] => 5
// )

En quittant l'équipe, laissez front effectuer l'opération d'ajout de 1. Cependant, lors de la suppression de la file d'attente, vous devez toujours déterminer si tous les éléments du tableau ont été retirés de la file d'attente. Ici, nous utilisons uniquement une condition de jugement très simple, c'est-à-dire si l'avant et l'arrière sont égaux pour déterminer si la file d'attente est vide. Vous pouvez utiliser une illustration pour vous aider à comprendre le code.

File d'attente circulaire

Je crois que de nombreux étudiants l'ont remarqué. L'opération de file d'attente ne modifie que les enregistrements de pointeur du début et de la fin de la file d'attente, mais le tableau continuera à augmenter, et le tableau remplira la mémoire. Ce n'est certainement pas une bonne implémentation de file d'attente. En fait, en langage C, les tableaux ont une longueur fixe. Le tableau en PHP ressemble plus à une structure de hachage, il peut donc croître à l'infini et nous n'avons pas besoin de définir une longueur de tableau spécifique au début.

C'est aussi la commodité de PHP, mais que devons-nous faire si nous ne voulons pas gaspiller d'espace mémoire ? Tout comme en langage C, nous spécifions également une longueur pour le tableau en PHP, et utilisons une "file d'attente circulaire" très classique pour résoudre le problème de stockage du tableau de files d'attente. Comme le montre l'image ci-dessous :

En fait, cela signifie que dans l'espace limité du tableau, lorsque nous atteignons la valeur maximale du tableau, les nouvelles données seront enregistrées à la position d'indice précédente. Par exemple, dans l'image, nous avons 6 éléments, le chef actuel de l'équipe est à l'indice 2 et la queue de l'équipe est à l'indice 5. Si nous mettons un élément en file d'attente, la fin de la file d'attente se déplace vers l'index 6. Si vous ajoutez un autre élément, la queue de file d'attente reviendra à l'indice 0. Si vous continuez à ajouter, lorsque l'indice de queue de file d'attente est égal à l'indice de tête de file d'attente moins 1, nous penserons que la file d'attente est pleine et qu'il n'y a plus d'éléments. peuvent être ajoutés.

De même, lors du retrait de la file d'attente, nous exploitons également l'élément chef d'équipe de manière cyclique. Lorsque l'élément chef d'équipe atteint l'indice 6, si nous continuons à retirer la file d'attente, il reviendra à la position d'indice 0 et continuera à sortir de la file d'attente. Lorsque la tête et la queue de la file d'attente sont égales, la file d'attente actuelle peut également être déterminée comme étant une file d'attente vide.

由此，我们可以看出，循环队列相比普通的线性队列来说，多了一个队满的状态。我们还是直接从代码中来看看这个队满的条件是如何判断的。

define('MAX_QUEUE_LENGTH', 6);

function EnSqQueueLoop(SqQueue &$queue, $e){
    // 判断队列是否满了
    if(($queue->rear + 1) % MAX_QUEUE_LENGTH == $queue->front){
        return false;
    }
    $queue->data[$queue->rear] = $e;
    $queue->rear = ($queue->rear + 1) % MAX_QUEUE_LENGTH; // 改成循环下标
}

function DeSqQueueLoop(SqQueue &$queue){
    // 队列为空
    if($queue->front == $queue->rear){
        return false;
    }
    $e = $queue->data[$queue->front];
    $queue->front = ($queue->front + 1) % MAX_QUEUE_LENGTH; // 改成循环下标
    return $e;
}

$q = InitSqQueue();
EnSqQueueLoop($q, 'A');
EnSqQueueLoop($q, 'B');
EnSqQueueLoop($q, 'C');
EnSqQueueLoop($q, 'D');
EnSqQueueLoop($q, 'E');

EnSqQueueLoop($q, 'F');

print_r($q);
// SqQueue Object
// (
//     [data] => Array
//         (
//             [0] => A
//             [1] => B
//             [2] => C
//             [3] => D
//             [4] => E
//             [5] =>   // 尾
//         )

//     [front] => 0
//     [rear] => 5
// )

echo DeSqQueueLoop($q), PHP_EOL;
echo DeSqQueueLoop($q), PHP_EOL;
print_r($q);
// SqQueue Object
// (
//     [data] => Array
//         (
//             [0] => A
//             [1] => B
//             [2] => C // 头
//             [3] => D
//             [4] => E
//             [5] =>   // 尾
//         )

//     [front] => 2
//     [rear] => 5
// )

EnSqQueueLoop($q, 'F');
EnSqQueueLoop($q, 'G');

EnSqQueueLoop($q, 'H');
print_r($q);
// SqQueue Object
// (
//     [data] => Array
//         (
//             [0] => G
//             [1] => B // 尾
//             [2] => C // 头
//             [3] => D
//             [4] => E
//             [5] => F
//         )

//     [front] => 2
//     [rear] => 1
// )

出、入队的下标移动以及队满的判断，都是以 (queue->rear + 1) % MAX_QUEUE_LENGTH 这个形式进行的。根据队列长度的取模来获取当前的循环下标，是不是非常地巧妙。不得不感慨先人的智慧呀！当然，这也是基本的数学原理哦，所以，学习数据结构还是要复习一下数学相关的知识哦！

链式队列

顺序队列有没有看懵？没关系，队列的链式结构其实相比顺序结构还要简单一些，因为它真的只需要操作队头和队尾的指针而已，别的真的就不太需要考虑了。而且这个指针就是真的指向具体对象的指针了。

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

class LinkQueue{
    public $first; // 队头指针
    public $rear; // 队尾指针
}

这里我们需要两个基本的物理结构。一个是节点 Node ，一个是队列对象，节点对象就是一个正常的链表结构，没啥特别的。而队列对象里面就更简单了，一个属性是队头指针，一个属性是队尾指针。

function InitLinkQueue(){
    $node = new LinkQueueNode();
    $node->next = NULL;
    $queue = new LinkQueue();
    $queue->first = $node;
    $queue->rear = $node;
    return $queue;
}

function EnLinkQueue(LinkQueue &$queue, $e){
    $node = new LinkQueueNode();
    $node->data = $e;
    $node->next = NULL;

    $queue->rear->next = $node;
    $queue->rear = $node;
}

function DeLinkQueue(LinkQueue &$queue){
    if($queue->front == $queue->rear){
        return false;
    }

    $node = $queue->first->next;
    $v = $node->data;

    $queue->first->next = $node->next;
    if($queue->rear == $node){
        $queue->rear = $queue->first;
    }

    return $v;
}

$q = InitLinkQueue();
EnLinkQueue($q, 'A');
EnLinkQueue($q, 'B');
EnLinkQueue($q, 'C');
EnLinkQueue($q, 'D');
EnLinkQueue($q, 'E');

print_r($q);
// LinkQueue Object
// (
//     [first] => LinkQueueNode Object
//         (
//             [data] => 
//             [next] => LinkQueueNode Object
//                 (
//                     [data] => A
//                     [next] => LinkQueueNode Object
//                         (
//                             [data] => B
//                             [next] => LinkQueueNode Object
//                                 (
//                                     [data] => C
//                                     [next] => LinkQueueNode Object
//                                         (
//                                             [data] => D
//                                             [next] => LinkQueueNode Object
//                                                 (
//                                                     [data] => E
//                                                     [next] => 
//                                                 )

//                                         )

//                                 )

//                         )

//                 )

//         )

//     [rear] => LinkQueueNode Object
//         (
//             [data] => E
//             [next] => 
//         )

// )

echo DeLinkQueue($q), PHP_EOL; // A
echo DeLinkQueue($q), PHP_EOL; // B

EnLinkQueue($q, 'F');
print_r($q);
// LinkQueue Object
// (
//     [first] => LinkQueueNode Object
//         (
//             [data] => 
//             [next] => LinkQueueNode Object
//                 (
//                     [data] => C
//                     [next] => LinkQueueNode Object
//                         (
//                             [data] => D
//                             [next] => LinkQueueNode Object
//                                 (
//                                     [data] => E
//                                     [next] => LinkQueueNode Object
//                                         (
//                                             [data] => F
//                                             [next] => 
//                                         )

//                                 )

//                         )

//                 )

//         )

//     [rear] => LinkQueueNode Object
//         (
//             [data] => F
//             [next] => 
//         )

// )

出、入队的代码函数和测试代码就一并给出了，是不是非常的简单。初始的队头元素依然是一个空节点做为起始节点。然后入队的时候，让 rear 等于新创建的这个节点，并在链表中建立链式关系。出队的时候也是同样的让 first 变成当前这个 first 的下一跳节点，也就是 first->next 就可以了。判断队空的条件也是简单的变成了队头和队尾指针是否相等就可以了。链队相比顺序队其实是简单了一些，不过同样的，next 这个东西容易让人头晕，硬记下来就可以了。大家还是可以结合图示来学习：

PHP 为我们提供的数组队列操作

最后，就和栈一样，PHP 代码中也为我们提供了一个可以用于队列操作的函数。

$sqQueueList = [];

array_push($sqQueueList, 'a');
array_push($sqQueueList, 'b');
array_push($sqQueueList, 'c');

print_r($sqQueueList);
// Array
// (
//     [0] => a
//     [1] => b
//     [2] => c
// )

array_shift($sqQueueList);
print_r($sqQueueList);
// Array
// (
//     [0] => b
//     [1] => c
// )

array_shift() 函数就是弹出数组中最前面的那个元素。请注意，这里元素的下标也跟着变动了，如果我们是 unset() 掉数组的 0 下标元素的话，b 和 c 的下标依然还会是 1 和 2 。而 array_shift() 则会重新整理数组，让其下标依然有序。

unset($sqQueueList[0]);
print_r($sqQueueList);
// Array
// (
//     [1] => c
// )

总结

关于栈的队列的内容我们就通过两篇文章介绍完了。不过光说不练假把式，接下来，我们来一点真实的干货，使用栈和队列来做做题呗，学算法就得刷题，一日不刷如隔三秋呀！！！

测试代码：

https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/3.栈和队列/source/3.2队列的相关逻辑操作.php

推荐学习：php视频教程

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!