共计 4360 个字符，预计需要花费 11 分钟才能阅读完成。
这篇文章是展现如何应用 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 类
<?php
require '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
<?php
interface 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,hh
echo $stack->pop(); // 出栈，打印 hhecho $stack->toString(); // 打印栈数据 [aa,bb,cc,dd,ee,ff,gg
正文完
