Richtige Haltung bei der Nutzung von Stapeln und Warteschlangen (mit Beispielen)

Durch die Untersuchung von Stapeln und Warteschlangen scheinen wir das Gefühl zu haben, dass die Datenstruktur tatsächlich sehr einfach ist. Natürlich ist dies nur der Anfang. Wir haben von Sequenzlisten und verknüpften Listen bis hin zu den aktuellen Stapeln und Warteschlangen begonnen, die tatsächlich den Weg für die Zukunft ebnen. Stapel und Warteschlangen können in Baum- und Graph-Traversal-Algorithmen gesehen werden. Hier werfen wir zunächst einen kurzen Blick auf einige praktische Anwendungen von Stapeln und Warteschlangen.

Palindrom-Frage

Angenommen, es gibt einen Text und wir müssen feststellen, ob es sich um ein „Palindrom“ handelt (keinen Text der Hui-Brüder). Sie können den Stack verwenden, um dieses Problem zu lösen.

Ein Palindrom bedeutet, dass nach der Teilung des Textes in zwei Teile der Inhalt des vorherigen Absatzes und der Inhalt des folgenden Absatzes genau gleich sind, die Reihenfolge jedoch umgekehrt ist. Es ist zum Beispiel sehr berühmt: Shanghais Leitungswasser kommt aus dem Meer. Shanghai kommt vom Meer. Diese zweiteilige Struktur bildet in einem Satz ein Palindrom. Ein weiteres Beispiel ist ein Zeichen gerader Länge: abcddcba, das ebenfalls ein Palindrom ist.

Ähnliche Fragen tauchen tatsächlich leicht in einigen einfachen Algorithmus-Interviewfragen auf. Ich glaube, viele Freunde haben es bereits herausgefunden. Wir können die erste Hälfte des Absatzes in den Stapel schieben und sie dann nacheinander mit der zweiten herausholen Durch den Vergleich der Segmente können Sie feststellen, ob es sich bei der aktuellen Zeichenfolge um ein Palindrom handelt. Reden Sie nicht einfach ohne zu üben, sondern implementieren Sie den 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)

Es ist ganz einfach: Verwenden Sie einfach array_push() und array_pop(), um sequentielle Stapeloperationen auszuführen. Das Einzige, was zu beachten ist, ist, dass sich bei unterschiedlichen ungeraden und geraden Zeichenlängen auch der Median, den wir verwenden möchten, entsprechend ändert.

Der Palindrom-Algorithmus ist relativ einfach. Darüber hinaus sind Fragen wie einfache Klammerzuordnung, arithmetische Operationen und Infix-zu-Suffix-Ausdrücke typische Interviewfragen für Stapelalgorithmen. Sie können nach relevanten Inhalten suchen und es selbst ausprobieren.

Rekursion

Bevor wir über Rekursion sprechen, müssen wir eines klarstellen: Funktionsaufrufe in Programmiersprachen sind im Wesentlichen Stapelaufrufe.

Wie verstehst du diesen Satz? Wenn wir Code ausführen und auf eine Funktion stoßen, geben wir diese Funktion immer zuerst ein. Nachdem wir den Code in dieser Funktion ausgeführt haben, kehren wir zur ursprünglichen Codeausführungszeile zurück, um mit der Ausführung des Codes fortzufahren, der die aktuelle Funktion aufruft. Zum Beispiel der folgende Code.

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.

Wenn die aktuelle Seite P zur Funktion testA() ausgeführt wird, ruft sie die Funktion testA() auf, um ihren internen Code auszuführen, d. h. P -> Dann ruft die Funktion testA() die Funktion testB() auf und führt nun den Code im Funktionskörper aus, der P -> Wenn der Code von testB() abgeschlossen ist, kehren Sie zu testA() zurück, um mit der Ausführung des Inhalts im Funktionskörper testA() fortzufahren, und kehren Sie schließlich zu Seite P zurück, um mit der Ausführung nach unten fortzufahren, d. h. B -> A -> P .

Wenn Sie die obige Beschreibung nicht verstehen, lesen Sie sie bitte noch ein paar Mal und studieren Sie sie sorgfältig. Ist das nicht nur ein Stack-Calling-Prozess? !

So gesehen ist der Stack in Programmiersprachen wirklich tief in den Knochen verankert. Denn solange Sie Code entwickeln, müssen Sie den Stack verwenden. „Rekursion“ ist eine typischere Implementierung des Stapels.

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

echo recursion(10), PHP_EOL;

Dies ist eine einfache rekursive Implementierung des faktoriellen Algorithmus. Das erste, was unser Code berechnet, ist, dass n am Ende des Stapels 1 ist. Nach dem Öffnen des Stapels gibt er 1 zurück und dann Multiplizieren Sie einfach 1 mit 2 und fahren Sie dann fort, den Stapel herauszuholen, indem Sie 2 mit 3 multiplizieren, und so weiter, bis das Fakultätsergebnis von 1 bis 10 berechnet ist.

Interviewfragen im Zusammenhang mit Rekursion kommen in unseren Interviews ebenfalls sehr häufig vor. Daher müssen wir verstehen, dass Rekursion tatsächlich eine Form des Stapels ist, und dann die Idee des Stapels verwenden, um den gesamten rekursiven Aufrufprozess zu dekonstruieren .

Warteschlangenanwendung

Lassen Sie uns abschließend über einige praktische Anwendungen von Warteschlangen sprechen. Tatsächlich gibt es nicht viele gute Beispiele für Warteschlangen auf Codeebene. Die häufigeren Beispiele könnten sein, dass zwei Warteschlangen zusammengeführt und aus der Warteschlange entfernt werden (Tanzpartnerproblem) oder dass zwei Warteschlangen zusammen aus der Warteschlange entfernt werden und zwei Warteschlangen zuvor auf einer Seite aus der Warteschlange entfernt werden Das eine kann durch das andere aus der Warteschlange genommen werden. Sie können selbst nach verwandten Themen suchen. Relativ gesehen sind Fragen zum Warteschlangenalgorithmus unter den Interviewfragen relativ selten, und die meisten davon erscheinen in Form von Auswahlbeurteilungsfragen, auch in postgradualen Aufnahmeprüfungen. In praktischen Anwendungen sind Warteschlangen jedoch mittlerweile eine supermagische Waffe zur Lösung von Problemen mit hoher Parallelität, und sie sind auch ein wichtiger Teil der Beurteilung Ihrer Erfahrung durch den Interviewer.

In der tatsächlichen Projektentwicklung ist das Flash-Kill-Problem eine der typischsten Funktionen der Warteschlange. Genau wie beim Schnappen von Bahntickets oder Xiaomi-Handys strömen zu jeder vollen Stunde eine große Anzahl von Anfragen ein. Wenn Sie sich nur darauf verlassen, dass der Server damit umgeht, wird die extrem hohe Parallelität nicht nur den Server enorm belasten , kann aber auch verschiedene Probleme verursachen, die nur in Szenarien mit hoher Parallelität auftreten, wie z. B. Überverkauf, Transaktionsausnahmen usw. (Mehrere Threads aktualisieren Daten gleichzeitig)

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

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

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

总结

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

测试代码：

https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/3.栈和队列/source/3.3栈和队列的应用.php

推荐学习：php视频教程

Das obige ist der detaillierte Inhalt vonRichtige Haltung bei der Nutzung von Stapeln und Warteschlangen (mit Beispielen). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!