スタックとキューを使用するための正しい姿勢 (例付き)

スタックとキューの研究を通じて、データ構造は実際には非常に単純であると感じられるようです。もちろん、これはほんの始まりにすぎず、シーケンス リストとリンク リストから現在のスタックとキューに至るまで、実際に将来への道を切り開いています。スタックとキューは、ツリーおよびグラフの走査アルゴリズムで見ることができます。ここでは、まずスタックとキューの実際のアプリケーションをいくつか簡単に見ていきます。

回文の質問

テキストがあると仮定します。それが「回文」(ホイ兄弟のテキストではない) かどうかを判断する必要があります。スタックを使用すると、この問題を解決できます。

回文とは、この段落のテキストを 2 つに分割した後、前の段落の内容と次の段落の内容はまったく同じですが、順序が逆になっていることを意味します。たとえば、非常に有名な話ですが、上海の水道水は海から来ています。上海は海から来た、この 2 部構成は 1 つの文で回文を形成します。もう 1 つの例は、偶数長の文字 abcddcba です。これも回文です。

同様の質問は、単純なアルゴリズムによる面接の質問で実際に簡単に現れます。多くの友人がすでにヒントを目にしていると思います。段落の前半をスタックにプッシュし、次の方法で 1 つずつポップアウトできます。スタックを後半と比較することで、現在の文字列が回文であるかどうかを判断できます。練習せずに話すだけでなく、コードを実装してみましょう。

$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)

これは非常に簡単で、array_push() と array_pop() を使用して順次スタック操作を実行するだけです。注意する必要がある唯一のことは、奇数文字と偶数文字の長さが異なると、必要な中央値もそれに応じて変化するということです。

回文アルゴリズムは比較的単純であり、さらに、単純な括弧の一致、算術演算、中置子から接尾辞への式など、スタック アルゴリズムの典型的な面接質問がよく出題されます。関連するコンテンツを検索して自分で試すことができます。

再帰

再帰について話す前に、1 つ明確にする必要があります。それは、プログラミング言語の関数呼び出しは本質的にスタック呼び出しであるということです。

この文をどう理解すればよいでしょうか?コードを実行するとき、関数が見つかった場合は、必ず最初にこの関数に入ります。この関数のコードを実行した後、元のコード実行行に戻り、現在の関数を呼び出すコードの実行を続けます。たとえば、次のコードです。

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.

現在のページ P が testA() 関数に実行されると、 testA() 関数に入り、その内部コード、つまり P -> A が実行されます。次に、 testA() 関数は testB() 関数を呼び出し、今度は testB() に入り、関数本体のコード ( P -> A -> B ) を実行します。 testB() のコードが完了したら、testA() に戻って testA() 関数本体の内容の実行を継続し、最後にページ P に戻って下方向の実行を継続します (つまり、B -> A -> )。 P .

上記の説明が理解できない場合は、何度か読んで慎重に勉強してください。これは単なるスタック呼び出し処理ではないでしょうか? ！

#こうしてみると、プログラミング言語ではスタックが非常に奥深いものになっています。コードを開発している限り、スタックを使用する必要があるからです。 「再帰」は、スタックのより一般的な実装です。

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

echo recursion(10), PHP_EOL;

これは、階乗アルゴリズムの単純な再帰実装です。再帰によってスタックが作成されるため、コードで最初に計算されるのは、スタックの一番下の n が 1 であることです。スタックをポップして 1 を返した後、 , 再度スタックからポップする場合は 1 に 2 を掛け、再びスタックからポップする場合には 2 に 3 を掛けます。というように、1 から 10 までの階乗結果が計算されます。

再帰に関連した面接の質問は、私たちの面接でも非常に一般的です。そのため、再帰が実際にはスタックの形式であることを理解し、スタックの思考を使用してスタックを分解する必要があります。再帰呼び出しプロセス全体。

キュー アプリケーション

最後に、キューの実際的なアプリケーションについて説明します。実際、コード レベルでのキューの良い例はあまりありません。より一般的なものとしては、2 つのキューがマージされてキューから取り出される (ダンス パートナーの問題)、または 2 つのキューが一緒にデキューされ、2 つのキューが片側でデキューされてからキューから取り出される、というものがあります。一方がもう一方によってデキューされる可能性がある、この種の問題です。関連するトピックを自分で検索できます。キューアルゴリズムの質問は面接質問の中では比較的まれであり、その多くは大学院入試を含めて選考判定質問の形で出題されます。しかし、実際のアプリケーションでは、キューは現在、同時実行性の高い問題を解決するための超魔法の武器であり、面接官があなたの経験を判断する重要な部分でもあります。

実際のプロジェクト開発において、キューの最も典型的な機能の 1 つはフラッシュ セール問題です。電車の切符や Xiaomi の携帯電話を手に入れるのと同じように、時間の終わりには大量のリクエストが押し寄せます。サーバーのみに処理を依存している場合、超高同時実行性によりサーバーに多大な負荷がかかるだけでなく、が、売られすぎやトランザクション例外など、同時実行性が高いシナリオでのみ発生する問題など、さまざまな問題が発生する可能性があります。 (複数のスレッドが同時にデータを更新します)

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

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

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

总结

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

测试代码：

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

推荐学习：php视频教程

以上がスタックとキューを使用するための正しい姿勢 (例付き)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。