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

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

展開(kāi)全文

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

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

回文題

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

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

類(lèi)似的這種題目其實(shí)很容易出現(xiàn)在一些簡(jiǎn)單的算法面試題中，相信也有不少小伙伴已經(jīng)看出端倪了，我們可以將前半段入棧，然后再一個(gè)一個(gè)的出棧與后半段進(jìn)行比對(duì)就可以判斷當(dāng)前的字符串是否是回文了。別光說(shuō)不練，我們就上代碼來(lái)實(shí)現(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ù)開(kā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)

很簡(jiǎn)單吧，就是使用 array_push() 和 array_pop() 來(lái)進(jìn)行的順序棧的操作而已。唯一需要注意的就是對(duì)于字符長(zhǎng)度奇偶數(shù)的不同，我們要取的中位數(shù)也相應(yīng)的要發(fā)生改變。

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

遞歸

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

怎么理解這句話呢？當(dāng)我們執(zhí)行代碼時(shí)，如果遇到一個(gè)函數(shù)，總是會(huì)先進(jìn)入到這個(gè)函數(shù)中，運(yùn)行完這個(gè)函數(shù)中的代碼之后才會(huì)再回到原來(lái)的代碼執(zhí)行線中繼續(xù)執(zhí)行調(diào)用當(dāng)前這個(gè)函數(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)前頁(yè)面 P ，在運(yùn)行到 testA() 函數(shù)時(shí)，就進(jìn)入了 testA() 函數(shù)內(nèi)部執(zhí)行其內(nèi)部的代碼，也就是 P -> A 。然后 testA() 函數(shù)又調(diào)用了 testB() 函數(shù)，那么現(xiàn)在就進(jìn)入了 testB() 中并執(zhí)行該函數(shù)體內(nèi)的代碼，也就是 P -> A -> B 。當(dāng) testB() 的代碼運(yùn)行完成后，返回到 testA() 繼續(xù)執(zhí)行 testA() 函數(shù)體里面的內(nèi)容，最后回到頁(yè)面 P 繼續(xù)向下執(zhí)行，也就是 B -> A -> P 。

上面這段描述如果一次沒(méi)看明白的話，請(qǐng)?jiān)俣嗫磶状?，?xì)細(xì)品。這不就是一個(gè)棧的調(diào)用過(guò)程嘛??！

這么一看，在編程語(yǔ)言中，棧還真是深入骨髓般的存在。因?yàn)槟阒灰窃陂_(kāi)發(fā)代碼，那么你一定就是在運(yùn)用棧這個(gè)東西了。而“遞歸”，則是棧的更典型的實(shí)現(xiàn)。

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

echo recursion(10), PHP_EOL;

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

遞歸相關(guān)的面試題也是我們?cè)诿嬖囍蟹浅３Ｒ?jiàn)的內(nèi)容，所以我們一定要把握好遞歸其實(shí)就是棧的一種表現(xiàn)形式，然后運(yùn)用棧的思想來(lái)解構(gòu)整個(gè)遞歸的調(diào)用過(guò)程。

隊(duì)列應(yīng)用

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

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

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

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

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

總結(jié)

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

測(cè)試代碼：

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

參考資料：

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

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

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