对于逻辑结构，我们也是从最简单的开始。Stack和Queue是大多数人都比较熟悉的两个词，但是Heap和Stack其实是两个东西。面试的时候不要被面试官忽悠了。堆是一个树结构，或者说完全二叉树结构。今天主要说一下这个栈的应用。什么是堆栈？堆栈通常是顺序数据结构。它最大的特点是后进先出（LIFO），或者反过来说，先进后出（FILO）也是可以的。这两句话是什么意思？最典型的例子就是大家看电视剧尤其是枪战片肯定会看到的一个东西：杂志。装弹匣时，子弹是一颗一颗压入弹匣，即第一颗子弹压在底部，开枪时，则按相反的顺序从弹匣中装入。子弹顶部弹出，第一颗放入的子弹是最后一颗发射的。这个例子其实很形象，我们再统一一下术语。将子弹压入弹匣称为“堆叠”，第一颗子弹在底部，这个位置称为“堆叠底部”，最后一颗子弹在顶部，此位置称为“堆叠顶部”，子弹发射就是“栈顶”的子弹，这个操作叫做“出栈”。通过以上术语的定义，我们可以看出栈的逻辑操作主要是“入栈”和“出栈”，而逻辑结构中最需要关心的就是“栈”top”和“stackbottom”是入栈和出栈时间状态。当然，栈的逻辑结构的使用顺序或者链式结构是没有问题的。让我们一一看看。顺序栈首先是顺序栈的一个比较简单的实现。既然是顺序结构，那就用数组吧。但是，我们还需要记录“栈顶”或者“栈底”，所以我们把这个顺序栈的数组封装成一个类。同时在该类中定义一个属性，表示当前栈的“栈顶”或“栈底”指针，其实就是当前“栈顶”或“栈底”在数组中的下标位置。一般来说，我们只需要记录“栈顶”的位置即可，默认将“栈底”设置为-1即可。因为数组下标本身是从0开始的，所以当“栈顶”属性为-1时，栈为空栈，因为它的“栈顶”和“栈底”在一起，并且有里面没有元素。类SqStack{公共$data;public$top;}初始化序列堆栈很简单，一个空数组并将$top设置为-1。函数InitSqStack(){$stack=newSqStack();$堆栈->数据=[]；$堆栈->顶部=-1；return$stack;}接下来是“stack”和“pop”的操作好了，我们先看代码。函数PushSqStack(SqStack&$stack,$x){$stack->top++;$stack->data[$stack->top]=$x;}functionPopSqStack(SqStack&$stack){//栈为空if($stack->top==-1){returnfalse;}$v=$stack->data[$stack->top];$堆栈->顶部--;return$v;}栈很简单，给数组元素添加内容，然后$top++就可以了。但是如果是C语言，因为它对数组的长度有限制，所以我们在入栈的时候还需要判断栈是否满了。当然，我们在PHP中没有这个顾虑。顺序压栈图显示栈时，需要判断当前栈是否为空。这个不区分语言，因为如果小于-1，再次使用这个栈就会有问题。出栈的时候，如果栈已经空了，就不要再给$top--了，然后获取栈顶元素并返回。顺序栈弹出图我们来看看这个顺序栈的测试结果。$stack=InitSqStack();PushSqStack($stack,'a');PushSqStack($stack,'b');PushSqStack($stack,'c');var_dump($stack);//对象(SqStack)#1(2){//["data"]=>//array(3){//[0]=>//string(1)"a"//[1]=>//string(1)"b"//[2]=>//string(1)"c"//}//["top"]=>//int(2)//}echoPopSqStack($stack),PHP_EOL;//cechoPopSqStack($stack),PHP_EOL;//bechoPopSqStack($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为我们准备的数组栈的操作函数，使用起来会更方便。其实对于链式存储结构来说，链栈的核心内容还是一样的。我们还需要关心我们的栈顶，我们还需要关心入栈和出栈的操作。但是在链式模式下，我们可以进行有头插值，即让插入的数据保持在链的顶部，达到“栈顶”的效果。这样，我们就不需要一个特殊的属性来保存当前的栈顶位置了。直接通过一张图理解会更清楚。类LinkStack{公共$data;public$next;}数据的结构就是一个典型的链式结构。主要是看入栈操作是如何进行的。functionInitLinkStack(){returnnull;}functionPushLinkStack(?LinkStack&$stack,$x){$s=newLinkStack();$s->数据=$x；$s->next=$stack;$stack=$s;}functionPopLinkStack(?LinkStack&$stack){if($stack==NULL){返回假；}$v=$堆栈->数据；$stack=$stack->下一个；返回$v;}在链栈中，初始化空栈的操作其实意义不大。我们可以直接定义一个空变量，然后对其进行链式操作，但是这里我们还是和顺序栈保持一致。就像序列栈中栈底是-1一样，在链栈中，我们也约定栈底是一个空对象节点。下一步是压入堆栈。这里我们使用头插入法，其实就是把新元素放在链表的最前面。先实例化一个节点，然后将这个节点的next指向链表的头节点。然后让当前节点成为链表新的头节点，如下图所示。同理，出栈的操作其实也是类似的，将头节点变为当前头节点的下一个节点，直到当前节点变为null，即出栈为空，如图：最后，我们测试同一套链式栈的代码是如何工作的。$stack=InitLinkStack();PushLinkStack($stack,'a');PushLinkStack($stack,'b');PushLinkStack($stack,'c');var_dump($stack);//对象(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//}//}//}echoPopLinkStack($stack),PHP_EOL;//cechoPopLinkStack($stack),PHP_EOL;//bechoPopLinkStack($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);//数组//(//[0]=>a//[1]=>b//[2]=>c//)array_pop($sqStackList);print_r($sqStackList);//数组//(//[0]=>a//[1]=>b//)回声计数($sqStackList)>0?$sqStackList[count($sqStackList)-1]:false,PHP_EOL;//barray_pop($sqStackList);echocount($sqStackList)>0?$sqStackList[count($sqStackList)-1]:false,PHP_EOL;//carray_pop($sqStackList);print_r($sqStackList);//Array//(//)估计很多同学已经用过了Passed这两个功能。array_push()就是往数组中压入一条数据。其实说白了就是给数组增加一条数据而已，并没有什么特别之处。array_pop()弹出数组最后一个位置的数据。是不是和我们上面实现的顺序栈完全一样的概念。没错，既然已经为我们准备好了语言环境，除了一些需要链式结构的场景，大多数情况下我们可以直接使用这两个函数，轻松实现PHP中的栈操作。小结栈的逻辑结构是不是很简单明了？事实上，栈在日常应用中被广泛使用。比如公式中前缀公式、中缀公式、后缀公式的转换。比如后面学习树和图的时候会接触到BFS（深度搜索），然后根据BFS引入递归的概念。另外一些解析字符时的对称匹配，回文算法的判断等，都是栈的典型应用。可以说栈支持了一半的计算机算法。那另一半呢？当然，就是我们下次要说的：队列。测试代码：https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/3.Stacksandqueues/source/3.1Stack相关逻辑操作.php参考资料：《数据结构》第二版，严为民《数据结构》第二版，陈越《数据结构高分笔记》2020版，天琴考研各自媒体平台均可搜索【硬核项目经理】
