【原】PHP數(shù)據(jù)結構-棧的相關邏輯操作

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

展開全文

棧的相關邏輯操作

對于邏輯結構來說，我們也是從最簡單的開始。堆棧、隊列，這兩個詞對于大部分人都不會陌生，但是，堆和棧其實是兩個東西。在面試的時候千萬不要被面試官繞暈了。堆是一種樹結構，或者說是完全二叉樹的結構。而今天，我們主要講的就是這個棧的應用。

什么是棧？

棧一般就是一種順序的數(shù)據(jù)結構。它最大的特點就是后進先出（LIFO），或者反過來說先進后出（FILO）也是可以的。這兩句話到底是什么意思呢？最典型的例子就是大家看電視劇時，特別是槍戰(zhàn)片時絕對會看到的一樣東西：彈匣。

彈匣在裝彈的時候都是一個一個的將子彈壓進彈匣的，也就是說，第一顆子彈是被壓在最底下的，而開槍的時候則是按相反的順序從彈匣的最頂部彈出來的，第一顆放進去的子彈是最后一個才被打出來的。

這個例子其實已經(jīng)非常形象了，我們再統(tǒng)一一下術語。將子彈壓進彈匣叫做“入?！?，第一顆子彈在最底下，這個位置叫做“棧底”，最后一顆子彈在最頂上，這個位置叫做“棧頂”，打出的這顆子彈是“棧頂”的那顆子彈，這個操作叫做“出?！薄?/p>

通過上面術語的定義，我們就可以看出，棧的邏輯操作主要就是“入?！焙汀俺鰲！?，而邏輯結構最需要關心的是這個“棧頂”和“棧底”在進行出入棧時的狀態(tài)。當然，棧的邏輯結構使用順序或鏈式結構都是沒有問題的，我們就一個一個地來看一下。

順序棧

首先還是比較簡單的順序棧的實現(xiàn)。既然是順序結構，那么就是用數(shù)組了。不過，我們還需要記錄一下“棧頂”或“棧底”的情況，所以我們將順序棧的這個數(shù)組封裝到一個類中。同時，在這個類中定義一個屬性來標明當前棧的“棧頂”或“棧底”指針，其實就是當前“棧頂”或“棧底”在數(shù)組中的下標位置。通常來說，我們只需要記錄“棧頂”的位置就可以了，將“棧底”默認為 -1 即可。因為數(shù)組下標本身是從 0 開始的，所以當“棧頂”屬性為 -1 時，這個棧就是一個空棧，因為它的“棧頂”和“棧底”在一起，里面并沒有元素。

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

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

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

接下來就是“入?！焙汀俺鰲！钡牟僮髁?，先看代碼。

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;
}

入棧很簡單，給數(shù)組元素添加內容，然后 $top++ 就可以了。不過如果是 C 語言的話，因為它有數(shù)組長度的限制，所以在入棧的時候，我們也需要判斷一下棧是否已經(jīng)滿了。當然，在 PHP 中我們就沒有這個顧慮啦。

順序棧入棧圖示

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

順序棧出棧圖示

我們來看一下這個順序棧的測試結果。

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

通過數(shù)組來操作棧是不是非常地簡單?？赐陮W習完鏈棧之后，我們還會講到 PHP 已經(jīng)為我們準備好的數(shù)組棧的操作函數(shù)哦，使用起來會更加的方便。

鏈棧

其實對于鏈式存儲結構來說，核心的內容還是一樣的，同樣是要關心我們的棧頂，也同樣要關心出入棧的操作。但是，在鏈式中，我們可以使有頭插法，也就是讓插入的數(shù)據(jù)保持在鏈的頂端來實現(xiàn)“棧頂”的效果。這樣，我們就不需要一個專門的屬性來保存當前的棧頂位置了。直接通過一個圖來理解會更清晰。

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

數(shù)據(jù)的結構就是一個典型的鏈式結構就可以了，主要還是看出入棧的操作是如何進行的。

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;
}

在鏈棧中其實初始化空棧的操作意義不大。我們可以直接定義一個 null 變量然后針對它進行鏈式操作就可以了，但在這里我們還是與順序棧保持統(tǒng)一。就像順序棧中的棧底為 -1 一樣，在鏈棧中，我們也約定好棧底為一個 null 對象節(jié)點。

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

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

最后，我們同樣的測試一下這一套鏈式棧的代碼運行情況如何。

$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)看出之前我們花費了 4 篇文章的時間來講述線性結構中的順序表和鏈表的重要作用了吧。它們真的是一切其它邏輯結構的基礎。不光是棧，在隊列、樹、圖中我們都會有不同結構的線性和鏈式的實現(xiàn)。當然，更重要的是能體會它們之間的區(qū)別，在不同的業(yè)務場景中，兩種不同的存儲結構可能真的會帶來完全不一樣的體驗。

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

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

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

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

總結

棧這個邏輯結構是不是非常的簡單清晰呀，在日常應用中其實棧的使用非常廣泛。比如算式中的前綴算式、中綴算式、后綴算式的轉化，比如我們后面學習樹、圖時要接觸到了BFS（深度搜索），再根據(jù)BFS引出遞歸這個概念。另外，在解析字符時的一些對稱匹配、回文算法的判斷等等，這些都是棧的典型應用?？梢哉f，棧這個東西撐起了計算機算法的半壁江山。而另外半壁呢？當然就是我們下回要講的：隊列。

測試代碼：

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

參考資料：

《數(shù)據(jù)結構》第二版，嚴蔚敏

《數(shù)據(jù)結構》第二版，陳越

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