使用堆疊和佇列的正確姿勢（附案例）

透過堆疊和佇列的學習，我們似乎會感覺到其實資料結構還是很簡單的嘛。當然，這只是一個開始，我們從順序表、鍊錶開始，到現在的堆疊和佇列，其實都是為了將來在鋪路。在樹和圖的遍歷演算法中，都可以見到棧和佇列的身影。在這裡，我們先簡單的看看堆疊和佇列的一些實際應用。

回文題

假設有一段文字，我們要判斷它是不是「回文」（不是回族兄弟的文字）。就可以應用堆疊來解決這個問題。

回文指的就是將這段文字一分為二之後，前面一段內容和後面一段內容是完全相同的，但是順序是相反的。例如非常出名的：上海自來水來自海上。上海自來，來自海上，這樣的兩段結構在一句話裡就構成了一段回文。又例如雙數長度的一段字元：abcddcba，這也是一段回文。

類似的這種題目其實很容易出現在一些簡單的演算法面試題中，相信也有不少小夥伴已經看出端倪了，我們可以將前半段入棧，然後再一個一個的出棧與後半段進行比對就可以判斷目前的字串是否是回文了。別光說不練，我們就上程式碼來實現。

$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() 來進行的順序堆疊的操作而已。唯一要注意的就是對於字元長度奇偶數的不同，我們要取的中位數也會對應的要改變。

回文演算法還是比較簡單的，另外還常會出現的像是簡單的括號匹配、算式運算、中綴轉後綴表達式這類的題目都是棧的典型演算法面試題。大家可以自行尋找相關的內容來嘗試嘗試。

遞迴

在講遞歸前，我們要弄清楚一件事情，那就是：程式語言中的函數呼叫本質上就是堆疊的呼叫。

怎麼理解這句話呢？當我們執行程式碼時，如果遇到一個函數，總是會先進入到這個函數中，運行完這個函數中的程式碼之後才會再回到原來的程式碼執行線中繼續執行呼叫目前這個函數的程式碼。比如下面這段程式碼。

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 的階乘結果。

遞迴相關的面試題也是我們在面試中非常常見的內容，所以我們一定要把握好遞歸其實就是堆疊的一種表現形式，然後運用堆疊的思想來解構整個遞歸的呼叫過程。

隊列應用程式

最後，我們再講講隊列的一些實際應用。隊列在程式碼層面其實並沒有太多很好的範例，比較常見的可能有兩個隊列合併出隊（舞伴問題）或者兩組隊列一起出隊，一邊出兩個另一個才能出一個之類的這種問題。大家可以自行找相關的題目。相對來說，隊列的演算法題在面試題中還是比較少的，包括在考研的時候也多是以選擇判斷之類的題目出現的。不過，在實際應用中，隊列現在卻是解決高並發問題的超級法寶，也是面試官判斷你經驗的重要內容。

在實際的專案開發中，佇列最典型的功能就是秒殺問題。就像搶火車票或搶小米手機一樣，在整點的時候，大量的請求湧入，如果僅依靠伺服器來處理，超高的並發量不僅會帶給伺服器巨大壓力，而且還有可能出現各種高並發場景下才會出現的問題，例如超賣、事務異常等。 （多個執行緒同時更新資料）

而队列，正是解决这个问题的一把好手。通常我们会使用的队列系统（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中文網其他相關文章！