弹匣在装弹的时候都是一个一个的将子弹压进弹匣的，也便是说，第一颗子弹是被压在最底下的，而开枪的时候则是按相反的顺序从弹匣的最顶部弹出来的，第一颗放进去的子弹是末了一个才被打出来的。
这个例子实在已经非常形象了，我们再统一一下术语。将子弹压进弹匣叫做“入栈”，第一颗子弹在最底下，这个位置叫做“栈底”，末了一颗子弹在最顶上，这个位置叫做“栈顶”，打出的这颗子弹是“栈顶”的那颗子弹，这个操作叫做“出栈”。
通过上面术语的定义，我们就可以看出，栈的逻辑操作紧张便是“入栈”和“出栈”，而逻辑构造最须要关心的是这个“栈顶”和“栈底”在进行出入栈时的状态。当然，栈的逻辑构造利用顺序或链式构造都是没有问题的，我们就一个一个地来看一下。
首先还是比较大略的顺序栈的实现。既然是顺序构造，那么便是用数组了。不过，我们还须要记录一下“栈顶”或“栈底”的情形，以是我们将顺序栈的这个数组封装到一个类中。同时，在这个类中定义一个属性来标明当前栈的“栈顶”或“栈底”指针，实在便是当前“栈顶”或“栈底”在数组中的下标位置。常日来说，我们只须要记录“栈顶”的位置就可以了，将“栈底”默认为 -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; // cecho PopSqStack($stack), PHP_EOL; // becho PopSqStack($stack), PHP_EOL; // avar_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; // cecho PopLinkStack($stack), PHP_EOL; // becho PopLinkStack($stack), PHP_EOL; // avar_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;// barray_pop($sqStackList);echo count($sqStackList) > 0 ? $sqStackList[count($sqStackList) - 1] : false, PHP_EOL;// carray_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版，天勤考研
