詳解php中的棧

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

什么是棧？

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

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

這個例子其實已經非常形象了，我們再統一一下術語。將子彈壓進彈匣叫做“入棧”，第一顆子彈在最底下，這個位置叫做“棧底”，最后一顆子彈在最頂上，這個位置叫做“棧頂”，打出的這顆子彈是“棧頂”的那顆子彈，這個操作叫做“出棧”。

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

順序棧

首先還是比較簡單的順序棧的實現。既然是順序結構，那么就是用數組了。不過，我們還需要記錄一下“棧頂”或“棧底”的情況，所以我們將順序棧的這個數組封裝到一個類中。

同時，在這個類中定義一個屬性來標明當前棧的“棧頂”或“棧底”指針，其實就是當前“棧頂”或“棧底”在數組中的下標位置。通常來說，我們只需要記錄“棧頂”的位置就可以了，將“棧底”默認為 -1 即可。因為數組下標本身是從 0 開始的，所以當“棧頂”屬性為 -1 時，這個棧就是一個空棧，因為它的“棧頂”和“棧底”在一起，里面并沒有元素。

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

初始化順序棧很簡單，一個空的數組并將 $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){     // 棧空     if($stack->top == -1){         return false;     }      $v = $stack->data[$stack->top];     $stack->top--;     return $v; }

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

順序棧入棧圖示

出棧的時候需要判斷當前的棧是否已經空了，這個就不區分什么語言了，因為要是比 -1 還小的話，再次使用這個棧就會出現問題了。在出棧的時候如果棧已經空了就不要再給 $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) //   }

通過數組來操作棧是不是非常地簡單。看完學習完鏈棧之后，我們還會講到 PHP 已經為我們準備好的數組棧的操作函數哦，使用起來會更加的方便。

鏈棧

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

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

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

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 變量然后針對它進行鏈式操作就可以了，但在這里我們還是與順序棧保持統一。就像順序棧中的棧底為 -1 一樣，在鏈棧中，我們也約定好棧底為一個 null 對象節點。

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

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

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

$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

是不是很多小伙伴已經看出之前我們花費了 4 篇文章的時間來講述線性結構中的順序表和鏈表的重要作用了吧。它們真的是一切其它邏輯結構的基礎。不光是棧，在隊列、樹、圖中我們都會有不同結構的線性和鏈式的實現。當然，更重要的是能體會它們之間的區別，在不同的業務場景中，兩種不同的存儲結構可能真的會帶來完全不一樣的體驗。

PHP 為我們提供的數組棧操作

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

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

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

總結

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

測試代碼：

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

推薦學習：php視頻教程