第八章：第13节 PHP数据结构与算法——栈
更新于：2017-07-02 22:01:50
介绍新的数据结构——栈，有些地方也把“栈”笼统地叫做“堆栈”，堆栈就是指栈。
栈为何物？
说起“栈”，我们首先立马想到它的特点“后进先出”。
它和链表一样，也是一个线性表，它是一个受限的线性表。栈是限制插入和删除都只能发生在一个位置上进行的线性表，该位置是线性表的末端，叫做栈的顶。
在线性表的表尾（末端）进行插入和删除操作，这里表尾是指栈顶，而不是栈底。
过程：先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。
栈的特殊之处在于限制了这个线性表的插入和删除的位置，它始终只在栈顶进行。这也就使得：栈底是固定的，最先进栈的只能在栈底。
操作：
栈的插入操作，叫做进栈，也成压栈。类似子弹入弹夹（如下图所示）
栈的删除操作，叫做出栈，也有的叫做弾栈，退栈。如同弹夹中的子弹出夹（如下图所示）
栈的实现：
php编程中30%的地方会用到数组，可见php数组的重要性。
在强类型编程语言中，有专用的数据结构解决方案。通常是创建一个容器，在这个容器中可以存储任意类型的数据，并且可以根据容器中存储的数据决定容器的容量，打到可以变长的容器结构，比如链表、堆栈和队列等都是数据结构中常用的形式。在PHP中，通常都是使用数组来完成其它语言使用数据结构才能完成的工作。它是弱类型语言，在同一个数组中就可以存储多种类型的数据，而且php中的数组没有长度限制，数组存储数据的容量还可以根据里面元素个数的增减自动调整。
通常情况下，我们可以用PHP数组模拟一个“栈”。
还记得这两个函数吗？array_pop、array_push。PHP早就内置了两个入栈与出栈操作的函数。
我们不用这两个函数，用最简单的方法模拟出一个“栈”。
详解：
$top=-1; //当前操作的那个元素
其中MaxSize是该堆栈的最大容量。后面将会以MaxSize-1的值MaxTop作为栈最大顶端指针。虽然数组结构可直接使用下标来存取数据，但在此将数组视为堆栈，故只能从栈的顶端进行处理。所以需要一个变量来记录目前堆栈顶端的索引值。初始值设为-1表示堆栈为空，top会随着堆栈中数据量的移动改变其指向顶端的位置。
如果是C语言去实现“栈”，数组应该指定最大宽度，因为C语言数组不像php数组能自行增长，必须要有一个初始宽度。
数据结构的堆栈与内存的栈区、堆区有什么区别？
数据结构的堆栈和我们前面介绍的内存中栈区、堆区有时候会混肴关系，搞不懂他们之间的关系。尤其“栈”很多地方喜欢叫“堆栈”。楠神从其他地方摘录了一些解释供大家参考。
一个由C/C++编译的程序占用的内存分为以下几个部分
1、栈区（stack）— 由编译器自动分配释放 ，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。
2、堆区（heap） — 一般由程序员分配释放， 若程序员不释放，程序结束时可能由OS回收 。注意它与数据结构中的堆是两回事，分配方式倒是类似于链表，呵呵。
3、全局区（静态区）（static）—，全局变量和静态变量的存储是放在一块的，初始化的全局变量和静态变量在一块区域， 未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。 - 程序结束后有系统释放
4、文字常量区—常量字符串就是放在这里的。 程序结束后由系统释放
5、程序代码区—存放函数体的二进制代码。
数据结构中的一般称“栈(stack)”，是一种后进先出的数据结构。它是一种概念，或者说是一种逻辑技术，与语言、平台无关。
内存管理中的“堆栈”其实是分为堆(heap)和栈(stack)的，以引用变量为例，引用变量本身存储在栈中，引用变量指向的值存储在堆中。
如int[] arr = {1, 2, 3};
变量arr(数组名)存储在栈中，变量arr的值(数组元素)存储在堆中(普通结构)。
内存管理中的栈采用的就是数据结构中的栈的思想，即遵循后进先出的管理方法。
好比数据结构中的栈是一项先进的技术，在内存管理中采用了该技术，在CPU的调度中可能也采用这种技术。
堆区是采用了堆的数据结构管理，栈区是采用了栈的数据结构管理
栈区是采用栈技术的内存区域，但不能认定凡是采用栈技术的区域都叫栈区，虽然目前的实际情况是这样。这是一个关于定义的准确问题。