【原】PHP數(shù)據(jù)結(jié)構(gòu)-棧和隊列的應(yīng)用

硬核項目經(jīng)理 2021-05-31

展開全文

棧和隊列的應(yīng)用

通過棧和隊列的學(xué)習(xí)，我們似乎會感覺到其實數(shù)據(jù)結(jié)構(gòu)還是非常簡單的嘛。當(dāng)然，這只是一個開始，我們從順序表、鏈表開始，到現(xiàn)在的棧和隊列，其實都是為了將來在鋪路。在樹和圖的遍歷算法中，都可以見到棧和隊列的身影。在這里，我們先簡單的看看棧和隊列的一些實際應(yīng)用。

回文題

假設(shè)有一段文字，我們要判斷它是不是“回文”（不是回族兄弟的文字）。就可以應(yīng)用棧來解決這個問題。

回文指的就是將這段文字一分為二之后，前面一段內(nèi)容和后面一段內(nèi)容是完全相同的，但是順序是相反的。比如非常出名的：上海自來水來自海上。上海自來，來自海上，這樣的兩段結(jié)構(gòu)在一句話里就構(gòu)成了一段回文。又比如雙數(shù)長度的一段字符：abcddcba，這也是一段回文。

類似的這種題目其實很容易出現(xiàn)在一些簡單的算法面試題中，相信也有不少小伙伴已經(jīng)看出端倪了，我們可以將前半段入棧，然后再一個一個的出棧與后半段進行比對就可以判斷當(dāng)前的字符串是否是回文了。別光說不練，我們就上代碼來實現(xiàn)。

$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 從中位數(shù)開始
    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() 來進行的順序棧的操作而已。唯一需要注意的就是對于字符長度奇偶數(shù)的不同，我們要取的中位數(shù)也相應(yīng)的要發(fā)生改變。

回文算法還是比較簡單的，另外還經(jīng)常會出現(xiàn)的像是簡單的括號匹配、算式運算、中綴轉(zhuǎn)后綴表達(dá)式這類的題目都是棧的典型算法面試題。大家可以自行查找相關(guān)的內(nèi)容來嘗試嘗試。

遞歸

在講遞歸前，我們要弄清楚一件事情，那就是：編程語言中的函數(shù)調(diào)用本質(zhì)上就是棧的調(diào)用。

怎么理解這句話呢？當(dāng)我們執(zhí)行代碼時，如果遇到一個函數(shù)，總是會先進入到這個函數(shù)中，運行完這個函數(shù)中的代碼之后才會再回到原來的代碼執(zhí)行線中繼續(xù)執(zhí)行調(diào)用當(dāng)前這個函數(shù)的代碼。比如下面這段代碼。

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.

當(dāng)前頁面 P ，在運行到 testA() 函數(shù)時，就進入了 testA() 函數(shù)內(nèi)部執(zhí)行其內(nèi)部的代碼，也就是 P -> A 。然后 testA() 函數(shù)又調(diào)用了 testB() 函數(shù)，那么現(xiàn)在就進入了 testB() 中并執(zhí)行該函數(shù)體內(nèi)的代碼，也就是 P -> A -> B 。當(dāng) testB() 的代碼運行完成后，返回到 testA() 繼續(xù)執(zhí)行 testA() 函數(shù)體里面的內(nèi)容，最后回到頁面 P 繼續(xù)向下執(zhí)行，也就是 B -> A -> P 。

上面這段描述如果一次沒看明白的話，請再多看幾次，細(xì)細(xì)品。這不就是一個棧的調(diào)用過程嘛??！

這么一看，在編程語言中，棧還真是深入骨髓般的存在。因為你只要是在開發(fā)代碼，那么你一定就是在運用棧這個東西了。而“遞歸”，則是棧的更典型的實現(xiàn)。

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

echo recursion(10), PHP_EOL;

這是一段簡單的階乘算法的遞歸實現(xiàn)，由于遞歸會建立一個棧，所以我們這段代碼最先計算出來的是的棧底的 n 是 1，出棧返回 1 之后，再出棧時就是用 1 乘以 2 ，再繼續(xù)出棧就是 2 乘以 3 ，依次類推，直到計算出從 1 到 10 的階乘結(jié)果。

遞歸相關(guān)的面試題也是我們在面試中非常常見的內(nèi)容，所以我們一定要把握好遞歸其實就是棧的一種表現(xiàn)形式，然后運用棧的思想來解構(gòu)整個遞歸的調(diào)用過程。

隊列應(yīng)用

最后，我們再講講隊列的一些實際應(yīng)用。隊列在代碼層面其實并沒有太多很好的示例，比較常見的可能有兩個隊列合并出隊（舞伴問題）或者兩組隊列一起出隊，一邊出兩個另一個才能出一個之類的這種問題。大家可以自行查找一下相關(guān)的題目。相對來說，隊列的算法題在面試題中還是比較少的，包括在考研的時候也多是以選擇判斷之類的題目出現(xiàn)的。不過，在實際應(yīng)用中，隊列現(xiàn)在卻是解決高并發(fā)問題的超級法寶，也是面試官判斷你經(jīng)驗的一個重要內(nèi)容。

在實際的項目開發(fā)中，隊列最典型的一個功能就是秒殺問題。就像搶火車票或者搶小米手機一樣，在整點的時候，大量的請求涌入，如果僅僅依靠服務(wù)器來處理，超高的并發(fā)量不僅會帶給服務(wù)器巨大壓力，而且還有可能出現(xiàn)各種高并發(fā)場景下才會出現(xiàn)的問題，比如超賣、事務(wù)異常等。（多個線程同時更新數(shù)據(jù)）

而隊列，正是解決這個問題的一把好手。通常我們會使用的隊列系統(tǒng)（redis、rabbitmq）都是以內(nèi)存為主的隊列系統(tǒng)，它們的特點就是存儲非常快。由前端（生產(chǎn)者）生成的大量請求都存入隊列中（入隊），然后在后臺腳本（消費者）中進行處理（出隊）。前端只需要返回一個正在處理中，或者正在排隊的提示即可，然后后臺處理完成后，通知前臺顯示結(jié)果。這樣，在一個秒殺場景中基本上就算是解決了高并發(fā)的問題了。當(dāng)然，現(xiàn)實環(huán)境可能還需要考慮更多因素，但核心都是以隊列的方式來解決這種瞬間高并發(fā)的業(yè)務(wù)功能。

另外，隊列還有一個重要的業(yè)務(wù)場景，那就是通知、消息、郵件、短信之類的這種信息發(fā)送。因為隊列的所能解決的一些問題的最大特點就是需要生產(chǎn)者/消費者的業(yè)務(wù)解耦。通常我們在群發(fā)消息時都會批量進行大規(guī)模的發(fā)送，這時就只需要準(zhǔn)備好消息內(nèi)容和對應(yīng)的手機號、設(shè)備id，就可以讓系統(tǒng)在后臺隊列中慢慢進行消息發(fā)送了，而不需要我們的前端一直等待消息全部發(fā)送完成。

這時，不少小伙伴又看出了一點點門道了。隊列這貨在實際應(yīng)用中，就是多線程的感覺呀，JS 中的事件回調(diào)，CPU 的碎片時間輪詢可不就是一種隊列的真實應(yīng)用嘛。還有設(shè)計模式中的“觀察者模式”，本身就是事件回調(diào)這種機制的一種編程范式，所以，用它來實現(xiàn)的很多功能中，我們都能看到隊列的影子。

總結(jié)

看看，一個棧，一個隊列，竟然都是我們在開發(fā)過程中天天要接觸的東西。是不是感覺自己的腦容量不夠用了？仔細(xì)再想想，還有哪些東西和我們的棧、隊列有關(guān)呢？其實只要把握住它們的兩個本質(zhì)就可以了：棧是后進先出（LIFO）或者說是先進后出（FILO），而隊列是先進先出（FIFO）。

測試代碼：

https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/3.棧和隊列/source/3.3棧和隊列的應(yīng)用.php

參考資料：

《數(shù)據(jù)結(jié)構(gòu)》第二版，嚴(yán)蔚敏

《數(shù)據(jù)結(jié)構(gòu)》第二版，陳越

《數(shù)據(jù)結(jié)構(gòu)高分筆記》2020版，天勤考研