数据结构-PHP通过 Array 类对象实现 "栈"

码农天地 - 2020-10-20 02:36:44

---

这篇文章是展示如何使用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

php介绍

PHP即“超文本预处理器”，是一种通用开源脚本语言。PHP是在服务器端执行的脚本语言，与C语言类似，是常用的网站编程语言。PHP独特的语法混合了C、Java、Perl以及 PHP 自创的语法。利于学习，使用广泛，主要适用于Web开发领域。

更多关于php的阅读

Tags 标签

php算法程序员

扩展阅读