这篇文章是展现如何应用PHP语言实现栈(Stack)这种数据结构，Stack也是一种线性构造，相比 Array 而言，Stack 对应的操作是 Array 的子集，只能从一端增加元素，也只能从一端取出元素，是一种 Last In First Out(LIFO)，即 后进先出 的构造，Stack 的利用很多，如 'undo 操作(撤销)'、'程序调用零碎栈'。
1.ArrayStruct 类
<?php/** * 数据结构-数组的实现 * Class ArrayStruct */class ArrayStruct{ //用于存放数据 protected $data = []; //用于标记数组大小 protected $size = 0; //用于标记数组的容量 protected $capacity = 10; /** * 构造函数 定义数组容量 * ArrayStruct constructor. * @param int $capacity */ public function __construct(int $capacity = 10) { $this->capacity = $capacity; } /** * 获取数组元素个数 * @return int */ public function getSize(): int { return $this->size; } /** * 获取数组的容量 * @return int */ public function getCapacity(): int { return $this->capacity; } /** * 判断数组是否为空 * @return bool */ public function isEmpty(): bool { return $this->size == 0; } /** * 向数组指定地位插入元素 * @param int $index * @param $e * @throws Exception */ public function add(int $index, $e): void { if ($this->size == $this->capacity) { $this->resize(2); //扩充到原来的2倍 } if ($index < 0 || $index > $this->size) { echo "增加地位超出数组大小"; exit; } //为了不便了解，[1,2,4,5,6],假如 $index = 3; $e = 100,插入之后[1,2,4,100,5,6] for ($i = $this->size; $i >= $index; $i--) { $this->data[$i] = $this->data[$i - 1]; } $this->data[$index] = $e; $this->size++; } /** * 向数组开端增加元素 * @param $e * @throws Exception */ public function addLast($e): void { $this->add($this->size, $e); } /** * 向数组结尾插入元素 * @param $e * @throws Exception */ public function addFirst($e): void { $this->add(0, $e); } /** * 获取 index 地位数组元素 * @param int $index * @return mixed */ public function get(int $index) { if ($index < 0 || $index > $this->size) { echo "index值超出元素的地位范畴，"; exit; } return $this->data[$index]; } /** * 获取数组开端元素 * @return mixed */ public function getLast() { return $this->get($this->size - 1); } /** * 判断数组中是否存在某个元素 * @param $e * @return bool */ public function contains($e): bool { for ($i = 1; $i < $this->size; $i++) { if ($this->data[$i] == $e) { return true; } } return false; } /** * 查某个元素在数组的地位索引值，若不存在则返回 -1 * @param $e * @return int */ public function find($e): int { for ($i = 0; $i < $this->size; $i++) { if ($this->data[$i] == $e) { return $i; } } return -1; } /** * 删除数组指定地位元素，返回删除元素的值 * @param $index * @return mixed */ public function remove($index) { if ($index < 0 || $index > $this->size) { echo "index值超出元素的地位范畴，"; exit; } $e = $this->data[$index]; for ($i = $index; $i < $this->size - 1; $i++) { $this->data[$i] = $this->data[$i + 1]; } $this->size--; $this->data[$this->size] = null; //loitering objects ! =memory /** 若以后数组大小，小于容量的一半，则重新分配一半的数组空间大小 **/ if ($this->size <= $this->capacity / 4 && $this->capacity % 2 == 0) { $this->resize(0.5); } return $e; } /** * 删除数组首个元素，返回删除元素的值 */ public function removeFirst() { return $this->remove(0); } /** * 删除数组首个元素，返回删除元素的值 */ public function removeLast() { return $this->remove($this->size - 1); } /** * 删除数组中特定元素 * @param $e */ public function removeElement($e) { for ($i = 0; $i < $this->size; $i++) { if ($this->data[$i] == $e) { $this->remove($i); $this->removeElement($e); break; } } } /** * 数组扩容，若是其余语言，如JAVA这里须要从新开拓空间 * @param $factor */ protected function resize($factor) { $this->capacity = $factor * $this->capacity; } /** * 将数组转化为字符串 * @return string */ public function toString(): string { $str = "["; foreach ($this->data as $value) { $str .= $value . ","; } $str = trim($str, ","); $str .= "]"; return $str; }}Tips：这是一个封装好的数组类，可用于数组的插入、删除、查找。
2.StackStruct 类
<?phprequire 'ArrayStruct.php';require 'Stack.php';/** * 数组实现栈 * Class StackStruct */class StackStruct implements Stack{ //数组类对象，用于寄存栈元素 public $array = null; /** * 构造函数 定义栈的容量 * ArrayStruct constructor. * @param int $capacity */ public function __construct(int $capacity = 10) { $this->array = new ArrayStruct($capacity); } /** * 获取栈大小 * @return int */ public function getSize(): int { return $this->array->getSize(); } /** * 判断栈是否为空 * @return bool */ public function isEmpty(): bool { return $this->array->isEmpty(); } /** * 元素入栈 */ public function push($e): void { $this->array->addLast($e); } /** * 出栈 * @return mixed */ public function pop() { return $this->array->removeLast(); } /** * 查看栈顶元素 * @return mixed */ public function peek() { return $this->array->getLast(); } /** * 将栈数组转化为字符串 * @return string */ public function toString(): string { return rtrim($this->array->toString(), "]"); }}Tips：这是一个Stack类，通过继承Array类实现Stack的基本功能。
3.interface Stack
<?phpinterface Stack{ /** * 获取栈大小 * @return int */ public function getSize(): int; /** * 判断栈是否为空 * @return bool */ public function isEmpty(): bool; /** * 元素入栈 */ public function push($e): void; /** * 出栈 * @return mixed */ public function pop(); /** * 查看栈顶元素 * @return mixed */ public function peek();}4.output_stack.php
<?php/** * 栈输入相干 */require 'StackStruct.php';$stack = new StackStruct();$stack->push('aa');$stack->push('bb');$stack->push('cc');$stack->push('dd');$stack->push('ee');$stack->push('ff');$stack->push('gg');$stack->push('hh');echo $stack->peek(); //查看栈顶元素，打印 hhecho $stack->toString(); //打印栈数据 [aa,bb,cc,dd,ee,ff,gg,hhecho $stack->pop(); //出栈，打印 hhecho $stack->toString(); //打印栈数据 [aa,bb,cc,dd,ee,ff,gg