Posture correcte pour l'utilisation des piles et des files d'attente (avec exemples)

Grâce à l'étude des piles et des files d'attente, nous semblons sentir que la structure des données est en réalité très simple. Bien sûr, ce n'est qu'un début. Nous sommes partis des listes de séquences et des listes chaînées jusqu'aux piles et files d'attente actuelles, qui ouvrent la voie à l'avenir. Les piles et les files d'attente peuvent être vues dans les algorithmes de parcours d'arbres et de graphiques. Ici, nous examinons d'abord brièvement quelques applications pratiques des piles et des files d'attente.

Question Palindrome

Supposons qu'il y ait un texte et que nous devions déterminer s'il s'agit d'un "palindrome" (pas d'un texte écrit par les frères Hui). Vous pouvez utiliser la pile pour résoudre ce problème.

Un palindrome signifie qu'une fois le texte divisé en deux parties, le contenu du paragraphe précédent et le contenu du paragraphe suivant sont exactement les mêmes, mais l'ordre est inversé. Par exemple, c’est très célèbre : l’eau du robinet de Shanghai vient de la mer. Shanghai vient de la mer. Cette structure en deux parties forme en une phrase un palindrome. Un autre exemple est un caractère de longueur paire : abcddcba, qui est aussi un palindrome.

Des questions similaires sont en fait faciles à apparaître dans certaines questions d'entretien algorithmiques simples. Je pense que de nombreux amis l'ont déjà compris. Nous pouvons placer la première moitié du paragraphe dans la pile, puis la sortir une par une avec la seconde. moitié. En comparant les segments, vous pouvez déterminer si la chaîne actuelle est un palindrome. Ne vous contentez pas de parler sans pratiquer, implémentons le code.

$string1 = 'abcdedcba';
$string2 = 'abcdeedcba';
$string3 = 'abcdefcba';

function getIsPlalindrome($string)
{
    if (gettype($string) != 'string') {
        return false;
    }
    $strlen = strlen($string);
    $mid = floor($strlen / 2);
    $arr = [];

    if ($strlen < 2) {
        return false;
    }

    // 入栈
    for ($i = 0; $i < $mid; $i++) {
        array_push($arr, $string[$i]);
    }

    $j = $mid;
    $i = $strlen % 2 == 0 ? $mid : $mid + 1; // $i 从中位数开始
    for (; $i < $strlen; $i++) {
        $v = $arr[$j - 1]; // 获得栈顶元素
        if ($v != $string[$i]) {
            return false;
        }
        array_pop($arr); // 弹出栈顶元素
        $j--;
    }
    if ($arr) {
        return false;
    }
    return true;
}

var_dump(getIsPlalindrome($string1)); // bool(true)
var_dump(getIsPlalindrome($string2)); // bool(true)
var_dump(getIsPlalindrome($string3)); // bool(false)

C'est très simple, utilisez simplement array_push() et array_pop() pour effectuer des opérations de pile séquentielles. La seule chose à noter est que pour différentes longueurs de caractères paires et impaires, la médiane que nous souhaitons prendre changera également en conséquence.

L'algorithme palindrome est relativement simple. De plus, les questions telles que la simple correspondance entre parenthèses, les opérations arithmétiques et les expressions infixe-suffixe qui apparaissent souvent sont des questions d'entretien typiques de l'algorithme de pile. Vous pouvez rechercher du contenu pertinent et l'essayer vous-même.

Récursion

Avant de parler de récursion, nous devons clarifier une chose, à savoir : les appels de fonction dans les langages de programmation sont essentiellement des appels de pile.

Comment comprenez-vous cette phrase ? Lorsque nous exécutons du code, si nous rencontrons une fonction, nous entrerons toujours cette fonction en premier. Après avoir exécuté le code dans cette fonction, nous reviendrons à la ligne d'exécution du code d'origine pour continuer à exécuter le code qui appelle la fonction actuelle. Par exemple, le code suivant.

function testA()
{
    echo 'A start.', PHP_EOL;
    testB();
    echo 'A end.', PHP_EOL;
}
function testB()
{
    echo 'B start.', PHP_EOL;
    echo 'B end.', PHP_EOL;
}
echo 'P start.', PHP_EOL;
testA();
echo 'P end.', PHP_EOL;

// P start.
// A start.
// B start.
// B end.
// A end.
// P end.

La page P actuelle, lorsqu'elle exécute la fonction testA(), elle entre dans la fonction testA() pour exécuter son code interne, c'est-à-dire P -> Ensuite, la fonction testA() appelle la fonction testB(), et maintenant elle entre dans testB() et exécute le code dans le corps de la fonction, qui est P -> Lorsque le code de testB() est terminé, revenez à testA() pour continuer l'exécution du contenu dans le corps de la fonction testA(), et enfin revenez à la page P pour continuer l'exécution vers le bas, c'est-à-dire B -> P.

Si vous ne comprenez pas la description ci-dessus, veuillez la lire encore quelques fois et l'étudier attentivement. N'est-ce pas simplement un processus d'appel de pile ? !

En regardant les choses de cette façon, dans les langages de programmation, la pile est vraiment ancrée dans les os. Parce que tant que vous développez du code, vous devez utiliser la pile. "Récursion" est une implémentation plus typique de la pile.

function recursion($n)
{
    if ($n == 0 || $n == 1) {
        return 1;
    }
    $result = recursion($n - 1) * $n;
    return $result;
}

echo recursion(10), PHP_EOL;

Il s'agit d'une simple implémentation récursive de l'algorithme factoriel. Puisque la récursion créera une pile, la première chose que notre code calcule est que n au bas de la pile est 1. Après avoir éclaté la pile, il renvoie 1, puis le fait apparaître à nouveau. Multipliez simplement 1 par 2, puis continuez à extraire la pile en multipliant 2 par 3, et ainsi de suite, jusqu'à ce que le résultat factoriel de 1 à 10 soit calculé.

Les questions d'entretien liées à la récursivité sont également très courantes dans nos entretiens, nous devons donc comprendre que la récursivité est en fait une forme de pile, puis utiliser l'idée de​​la pile pour déconstruire l'ensemble du processus d'appel récursif .

Application de file d'attente

Enfin, parlons de quelques applications pratiques des files d'attente. En fait, il n'y a pas beaucoup de bons exemples de files d'attente au niveau du code. Les plus courants peuvent être que deux files d'attente sont fusionnées et retirées de la file d'attente (problème de partenaire de danse) ou que deux files d'attente sont retirées ensemble et que deux files d'attente sont retirées d'un côté avant. l'un peut être retiré de la file d'attente par l'autre. Vous pouvez rechercher vous-même des sujets connexes. Relativement parlant, les questions d'algorithme de file d'attente sont relativement rares parmi les questions d'entretien, et la plupart d'entre elles apparaissent sous la forme de questions de jugement de sélection, y compris lors des examens d'entrée de troisième cycle. Cependant, dans les applications pratiques, les files d'attente sont désormais une arme super magique pour résoudre les problèmes de concurrence élevée, et elles constituent également un facteur important permettant aux enquêteurs de juger votre expérience.

Dans le développement de projets réels, l'une des fonctions les plus typiques de la file d'attente est le problème de flash kill. Tout comme pour récupérer des billets de train ou des téléphones portables Xiaomi, en début d'heure, un grand nombre de demandes affluent. Si vous comptez uniquement sur le serveur pour les gérer, la simultanéité ultra-élevée n'exercera pas seulement une pression énorme sur le serveur. , mais peut également provoquer divers problèmes qui ne se produisent que dans des scénarios de concurrence élevée, tels que la survente, les exceptions de transaction, etc. (Plusieurs threads mettent à jour les données simultanément)

而队列，正是解决这个问题的一把好手。通常我们会使用的队列系统（redis、rabbitmq）都是以内存为主的队列系统，它们的特点就是存储非常快。由前端（生产者）生成的大量请求都存入队列中（入队），然后在后台脚本（消费者）中进行处理（出队）。前端只需要返回一个正在处理中，或者正在排队的提示即可，然后后台处理完成后，通知前台显示结果。这样，在一个秒杀场景中基本上就算是解决了高并发的问题了。当然，现实环境可能还需要考虑更多因素，但核心都是以队列的方式来解决这种瞬间高并发的业务功能。

另外，队列还有一个重要的业务场景，那就是通知、消息、邮件、短信之类的这种信息发送。因为队列的所能解决的一些问题的最大特点就是需要生产者/消费者的业务解耦。通常我们在群发消息时都会批量进行大规模的发送，这时就只需要准备好消息内容和对应的手机号、设备id，就可以让系统在后台队列中慢慢进行消息发送了，而不需要我们的前端一直等待消息全部发送完成。

这时，不少小伙伴又看出了一点点门道了。队列这货在实际应用中，就是多线程的感觉呀，JS 中的事件回调，CPU 的碎片时间轮询可不就是一种队列的真实应用嘛。还有设计模式中的“观察者模式”，本身就是事件回调这种机制的一种编程范式，所以，用它来实现的很多功能中，我们都能看到队列的影子。

总结

看看，一个栈，一个队列，竟然都是我们在开发过程中天天要接触的东西。是不是感觉自己的脑容量不够用了？仔细再想想，还有哪些东西和我们的栈、队列有关呢？其实只要把握住它们的两个本质就可以了：栈是后进先出（LIFO）或者说是先进后出（FILO），而队列是先进先出（FIFO）。

测试代码：

https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/3.栈和队列/source/3.3栈和队列的应用.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!