【原】PHP數(shù)據(jù)結(jié)構(gòu)-棧的相關(guān)邏輯操作

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

展開(kāi)全文

棧的相關(guān)邏輯操作

對(duì)于邏輯結(jié)構(gòu)來(lái)說(shuō)，我們也是從最簡(jiǎn)單的開(kāi)始。堆棧、隊(duì)列，這兩個(gè)詞對(duì)于大部分人都不會(huì)陌生，但是，堆和棧其實(shí)是兩個(gè)東西。在面試的時(shí)候千萬(wàn)不要被面試官繞暈了。堆是一種樹(shù)結(jié)構(gòu)，或者說(shuō)是完全二叉樹(shù)的結(jié)構(gòu)。而今天，我們主要講的就是這個(gè)棧的應(yīng)用。

什么是棧？

棧一般就是一種順序的數(shù)據(jù)結(jié)構(gòu)。它最大的特點(diǎn)就是后進(jìn)先出（LIFO），或者反過(guò)來(lái)說(shuō)先進(jìn)后出（FILO）也是可以的。這兩句話到底是什么意思呢？最典型的例子就是大家看電視劇時(shí)，特別是槍?xiě)?zhàn)片時(shí)絕對(duì)會(huì)看到的一樣?xùn)|西：彈匣。

彈匣在裝彈的時(shí)候都是一個(gè)一個(gè)的將子彈壓進(jìn)彈匣的，也就是說(shuō)，第一顆子彈是被壓在最底下的，而開(kāi)槍的時(shí)候則是按相反的順序從彈匣的最頂部彈出來(lái)的，第一顆放進(jìn)去的子彈是最后一個(gè)才被打出來(lái)的。

這個(gè)例子其實(shí)已經(jīng)非常形象了，我們?cè)俳y(tǒng)一一下術(shù)語(yǔ)。將子彈壓進(jìn)彈匣叫做“入?！?，第一顆子彈在最底下，這個(gè)位置叫做“棧底”，最后一顆子彈在最頂上，這個(gè)位置叫做“棧頂”，打出的這顆子彈是“棧頂”的那顆子彈，這個(gè)操作叫做“出棧”。

通過(guò)上面術(shù)語(yǔ)的定義，我們就可以看出，棧的邏輯操作主要就是“入?！焙汀俺鰲！保壿嫿Y(jié)構(gòu)最需要關(guān)心的是這個(gè)“棧頂”和“棧底”在進(jìn)行出入棧時(shí)的狀態(tài)。當(dāng)然，棧的邏輯結(jié)構(gòu)使用順序或鏈?zhǔn)浇Y(jié)構(gòu)都是沒(méi)有問(wèn)題的，我們就一個(gè)一個(gè)地來(lái)看一下。

順序棧

首先還是比較簡(jiǎn)單的順序棧的實(shí)現(xiàn)。既然是順序結(jié)構(gòu)，那么就是用數(shù)組了。不過(guò)，我們還需要記錄一下“棧頂”或“棧底”的情況，所以我們將順序棧的這個(gè)數(shù)組封裝到一個(gè)類(lèi)中。同時(shí)，在這個(gè)類(lèi)中定義一個(gè)屬性來(lái)標(biāo)明當(dāng)前棧的“棧頂”或“棧底”指針，其實(shí)就是當(dāng)前“棧頂”或“棧底”在數(shù)組中的下標(biāo)位置。通常來(lái)說(shuō)，我們只需要記錄“棧頂”的位置就可以了，將“棧底”默認(rèn)為 -1 即可。因?yàn)閿?shù)組下標(biāo)本身是從 0 開(kāi)始的，所以當(dāng)“棧頂”屬性為 -1 時(shí)，這個(gè)棧就是一個(gè)空棧，因?yàn)樗摹皸ｍ敗焙汀皸５住痹谝黄?，里面并沒(méi)有元素。

class SqStack
{
    public $data;
    public $top;
}

初始化順序棧很簡(jiǎn)單，一個(gè)空的數(shù)組并將 $top 設(shè)置為 -1 。

function InitSqStack()
{
    $stack = new SqStack();
    $stack->data = [];
    $stack->top = -1;
    return $stack;
}

接下來(lái)就是“入棧”和“出?！钡牟僮髁?，先看代碼。

function PushSqStack(SqStack &$stack, $x){
    $stack->top ++;
    $stack->data[$stack->top] = $x;
}

function PopSqStack(SqStack &$stack){
    // ?？?/span>
    if($stack->top == -1){
        return false;
    }

    $v = $stack->data[$stack->top];
    $stack->top--;
    return $v;
}

入棧很簡(jiǎn)單，給數(shù)組元素添加內(nèi)容，然后 $top++ 就可以了。不過(guò)如果是 C 語(yǔ)言的話，因?yàn)樗袛?shù)組長(zhǎng)度的限制，所以在入棧的時(shí)候，我們也需要判斷一下棧是否已經(jīng)滿了。當(dāng)然，在 PHP 中我們就沒(méi)有這個(gè)顧慮啦。

順序棧入棧圖示

出棧的時(shí)候需要判斷當(dāng)前的棧是否已經(jīng)空了，這個(gè)就不區(qū)分什么語(yǔ)言了，因?yàn)橐潜?-1 還小的話，再次使用這個(gè)棧就會(huì)出現(xiàn)問(wèn)題了。在出棧的時(shí)候如果棧已經(jīng)空了就不要再給 $top-- 了，然后獲取棧頂元素并返回就可以了。

順序棧出棧圖示

我們來(lái)看一下這個(gè)順序棧的測(cè)試結(jié)果。

$stack = InitSqStack();

PushSqStack($stack, 'a');
PushSqStack($stack, 'b');
PushSqStack($stack, 'c');

var_dump($stack);
// object(SqStack)#1 (2) {
//     ["data"]=>
//     array(3) {
//       [0]=>
//       string(1) "a"
//       [1]=>
//       string(1) "b"
//       [2]=>
//       string(1) "c"
//     }
//     ["top"]=>
//     int(2)
//   }

echo PopSqStack($stack), PHP_EOL; // c
echo PopSqStack($stack), PHP_EOL; // b
echo PopSqStack($stack), PHP_EOL; // a

var_dump($stack);
// object(SqStack)#1 (2) {
//     ["data"]=>
//     array(3) {
//       [0]=>
//       string(1) "a"
//       [1]=>
//       string(1) "b"
//       [2]=>
//       string(1) "c"
//     }
//     ["top"]=>
//     int(-1)
//   }

通過(guò)數(shù)組來(lái)操作棧是不是非常地簡(jiǎn)單?？赐陮W(xué)習(xí)完鏈棧之后，我們還會(huì)講到 PHP 已經(jīng)為我們準(zhǔn)備好的數(shù)組棧的操作函數(shù)哦，使用起來(lái)會(huì)更加的方便。

鏈棧

其實(shí)對(duì)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)來(lái)說(shuō)，核心的內(nèi)容還是一樣的，同樣是要關(guān)心我們的棧頂，也同樣要關(guān)心出入棧的操作。但是，在鏈?zhǔn)街校覀兛梢允褂蓄^插法，也就是讓插入的數(shù)據(jù)保持在鏈的頂端來(lái)實(shí)現(xiàn)“棧頂”的效果。這樣，我們就不需要一個(gè)專(zhuān)門(mén)的屬性來(lái)保存當(dāng)前的棧頂位置了。直接通過(guò)一個(gè)圖來(lái)理解會(huì)更清晰。

class LinkStack{
    public $data;
    public $next;
}

數(shù)據(jù)的結(jié)構(gòu)就是一個(gè)典型的鏈?zhǔn)浇Y(jié)構(gòu)就可以了，主要還是看出入棧的操作是如何進(jìn)行的。

function InitLinkStack(){
    return null;
}

function PushLinkStack(?LinkStack &$stack, $x){
    $s = new LinkStack();
    $s->data = $x;
    $s->next = $stack;
    $stack = $s;
}

function PopLinkStack(?LinkStack &$stack){
    if($stack == NULL){
        return false;
    }
    $v = $stack->data;
    $stack = $stack->next;
    return $v;
}

在鏈棧中其實(shí)初始化空棧的操作意義不大。我們可以直接定義一個(gè) null 變量然后針對(duì)它進(jìn)行鏈?zhǔn)讲僮骶涂梢粤?，但在這里我們還是與順序棧保持統(tǒng)一。就像順序棧中的棧底為 -1 一樣，在鏈棧中，我們也約定好棧底為一個(gè) null 對(duì)象節(jié)點(diǎn)。

接下來(lái)就是入棧操作了。這里我們使用的是頭插法，其實(shí)就是將新元素放到鏈表的頂端。先實(shí)例化一個(gè)節(jié)點(diǎn)，然后將這個(gè)節(jié)點(diǎn)的 next 指向鏈表的頭節(jié)點(diǎn)。接著再讓當(dāng)前這個(gè)節(jié)點(diǎn)成為鏈表的新的頭節(jié)點(diǎn)，就像下圖所示的那樣。

同理，出棧的操作其實(shí)也是類(lèi)似的，將頭節(jié)點(diǎn)變成當(dāng)前頭節(jié)點(diǎn)的 next 節(jié)點(diǎn)，直到當(dāng)前節(jié)點(diǎn)變成 null ，也就是棧已經(jīng)空了，如圖所示：

最后，我們同樣的測(cè)試一下這一套鏈?zhǔn)綏５拇a運(yùn)行情況如何。

$stack = InitLinkStack();

PushLinkStack($stack, 'a');
PushLinkStack($stack, 'b');
PushLinkStack($stack, 'c');

var_dump($stack);
// object(LinkStack)#3 (2) {
//     ["data"]=>
//     string(1) "c"
//     ["next"]=>
//     object(LinkStack)#2 (2) {
//       ["data"]=>
//       string(1) "b"
//       ["next"]=>
//       object(LinkStack)#1 (2) {
//         ["data"]=>
//         string(1) "a"
//         ["next"]=>
//         NULL
//       }
//     }
//   }

echo PopLinkStack($stack), PHP_EOL; // c
echo PopLinkStack($stack), PHP_EOL; // b
echo PopLinkStack($stack), PHP_EOL; // a

var_dump($stack);
// NULL

是不是很多小伙伴已經(jīng)看出之前我們花費(fèi)了 4 篇文章的時(shí)間來(lái)講述線性結(jié)構(gòu)中的順序表和鏈表的重要作用了吧。它們真的是一切其它邏輯結(jié)構(gòu)的基礎(chǔ)。不光是棧，在隊(duì)列、樹(shù)、圖中我們都會(huì)有不同結(jié)構(gòu)的線性和鏈?zhǔn)降膶?shí)現(xiàn)。當(dāng)然，更重要的是能體會(huì)它們之間的區(qū)別，在不同的業(yè)務(wù)場(chǎng)景中，兩種不同的存儲(chǔ)結(jié)構(gòu)可能真的會(huì)帶來(lái)完全不一樣的體驗(yàn)。

PHP 為我們提供的數(shù)組棧操作

最后，我們簡(jiǎn)單的看一下在 PHP 中已經(jīng)為我們準(zhǔn)備好的兩個(gè)數(shù)組操作函數(shù)。有了它們，對(duì)于順序棧來(lái)說(shuō)，我們的操作可以簡(jiǎn)化到非常傻瓜智能的效果。

$sqStackList = [];

array_push($sqStackList, 'a');
array_push($sqStackList, 'b');
array_push($sqStackList, 'c');

print_r($sqStackList);
// Array
// (
//     [0] => a
//     [1] => b
//     [2] => c
// )

array_pop($sqStackList);
print_r($sqStackList);
// Array
// (
//     [0] => a
//     [1] => b
// )

echo count($sqStackList) > 0 ? $sqStackList[count($sqStackList) - 1] : false, PHP_EOL;
// b

array_pop($sqStackList);

echo count($sqStackList) > 0 ? $sqStackList[count($sqStackList) - 1] : false, PHP_EOL;
// c

array_pop($sqStackList);

print_r($sqStackList);
// Array
// (
// )

估計(jì)不少同學(xué)早就用過(guò)這兩個(gè)函數(shù)了。array_push() 就是向數(shù)組中壓入一個(gè)數(shù)據(jù)，其實(shí)說(shuō)白了，增加一個(gè)數(shù)據(jù)到數(shù)組中而已，沒(méi)什么特別稀罕的功能。而 array_pop() 則是將數(shù)組最后一個(gè)位置的數(shù)據(jù)彈出。是不是和我們上面自己實(shí)現(xiàn)的那個(gè)順序棧是完全相同的概念。沒(méi)錯(cuò)，既然語(yǔ)言環(huán)境已經(jīng)為我們準(zhǔn)備好了，那么除了在某些場(chǎng)景下需要鏈?zhǔn)浇Y(jié)構(gòu)的話，大部分情況下我們直接使用這兩個(gè)函數(shù)就可以方便地實(shí)現(xiàn) PHP 中的棧操作了。

總結(jié)

棧這個(gè)邏輯結(jié)構(gòu)是不是非常的簡(jiǎn)單清晰呀，在日常應(yīng)用中其實(shí)棧的使用非常廣泛。比如算式中的前綴算式、中綴算式、后綴算式的轉(zhuǎn)化，比如我們后面學(xué)習(xí)樹(shù)、圖時(shí)要接觸到了BFS（深度搜索），再根據(jù)BFS引出遞歸這個(gè)概念。另外，在解析字符時(shí)的一些對(duì)稱(chēng)匹配、回文算法的判斷等等，這些都是棧的典型應(yīng)用。可以說(shuō)，棧這個(gè)東西撐起了計(jì)算機(jī)算法的半壁江山。而另外半壁呢？當(dāng)然就是我們下回要講的：隊(duì)列。

測(cè)試代碼：

https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/3.棧和隊(duì)列/source/3.1棧的相關(guān)邏輯操作.php

參考資料：

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

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

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