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

什么是棧？

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

彈匣在裝彈的時(shí)候都是一個(gè)一個(gè)的將子彈壓進(jìn)彈匣的，也就是說(shuō)，第一顆子彈是被壓在最底下的，而開槍的時(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ǔ)的定義，我們就可以看出，棧的邏輯操作主要就是“入?！焙汀俺鰲！?，而邏輯結(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è)類中。

同時(shí)，在這個(gè)類中定義一個(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 開始的，所以當(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){     // 棧空     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è)專門的屬性來(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í)也是類似的，將頭節(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ì)列、樹、圖中我們都會(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í)要接觸到了BFS（深度搜索），再根據(jù)BFS引出遞歸這個(gè)概念。另外，在解析字符時(shí)的一些對(duì)稱匹配、回文算法的判斷等等，這些都是棧的典型應(yīng)用?？梢哉f(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

推薦學(xué)習(xí)：php視頻教程