詳解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视频教程

以上是詳解php中的棧的詳細內容。更多資訊請關注PHP中文網其他相關文章！