对于逻辑构造来说，咱们也是从最简略的开始。堆栈、队列，这两个词对于大部分人都不会生疏，然而，堆和栈其实是两个货色。在面试的时候千万不要被面试官绕晕了。堆是一种树结构，或者说是齐全二叉树的构造。而明天，咱们次要讲的就是这个栈的利用。

什么是栈？

栈个别就是一种程序的数据结构。它最大的特点就是后进先出（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

参考资料：

《数据结构》第二版，严蔚敏

《数据结构》第二版，陈越

《数据结构高分笔记》2020 版，天勤考研

各自媒体平台均可搜寻【硬核项目经理】