数据结构-PHP通过链表类对象实现 "栈"
作者：爱因诗贤
来源：SegmentFault 思否社区
这篇文章是展示如何使用PHP语言实现的链表类(LinkedList)，然后通过链表来实现的 栈(Stack) 只能从栈顶添加元素，也只能从栈顶取出元素，是一种 Last In First Out(LIFO)，即 后进先出 的结构。
1.output_stack_by_linked_list.php
这是一个调用和打印输出结果的展示文件：
/*** 栈输出相关*/require 'StackByLinkedList.php';$stack = new StackByLinkedList();$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 "
";echo $stack->toString(); //打印栈数据 hh->gg->ff->ee->dd->cc->bb->aa->nullecho "
";echo $stack->pop(); //出栈，打印 hhecho "
";echo $stack->toString(); //打印栈数据 gg->ff->ee->dd->cc->bb->aa->null
2.StackByLinkedList 类
这是一个封装好的 栈(Stack) ，通过实例化 链表类(LinkedList) 实现了入栈(push)和 出栈(pop)， 还有查看栈顶(peek):
require 'LinkedList.php';require 'Stack.php';class StackByLinkedList implements Stack{//链表类对象，用于存放栈元素protected $array = null;/*** 构造函数 定义栈的容量* ArrayStruct constructor.* @param int $capacity*/public function __construct() {$this->array = new LinkedList();}/*** 获取栈大小* @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->addFirst($e);}/*** 出栈* @return mixed*/public function pop() {return $this->array->removeFirst();}/*** 查看栈顶元素* @return mixed*/public function peek() {return $this->array->getFirst();}/*** 将栈数组转化为字符串* @return string*/public function toString(): string {return $this->array->toString();}}
Tips：这是一个Stack类，通过继承 LinkedList 类实现 Stack 的基本功能。
3.interface Stack
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.LinkedList 类
这是封装好的一个链表类，能实现链表的基本功能：
/*** 链表的实现* Class LinkedList*/class LinkedList{private $dummyHead;private $size;/*** 初始化链表 null->null* LinkedList constructor.*/public function __construct() {$this->dummyHead = new Node(null, null);$this->size = 0;}/*** 获取链表大小* @return int*/public function getSize(): int {return $this->size;}/*** 判断链表是否为空* @return bool*/public function isEmpty(): bool {return $this->size == 0;}/*** 在链表的第 index 位置添加元素* @param int $index* @param $e*/public function add(int $index, $e): void {if ($index < 0 || $index > $this->size) {echo "索引范围错误";exit;}$prve = $this->dummyHead;for ($i = 0; $i < $index; $i++) {$prve = $prve->next;}//将上插入位置的上一个位置的 next 节点指向插入节点，插入节点的 next 节点信息指向原上节点的 next 节点$prve->next = new Node($e, $prve->next);$this->size++;}/*** 向链表开头添加元素* @param $e*/public function addFirst($e): void {$this->add(0, $e);}/*** 向链表末尾添加元素* @param $e*/public function addLast($e): void {$this->add($this->size, $e);}/*** 获取链表第 index 位置元素* @param $index*/public function get($index) {if ($index < 0 || $index > $this->size) {echo "索引范围错误";exit;}$node = $this->dummyHead;for ($i = 0; $i < $index + 1; $i++) {$node = $node->next;}return $node->e;}/*** 获取链表第一个元素* @return mixed*/public function getFirst() {return $this->get(0);}/*** 获取链表最后一个元素* @return mixed*/public function getLast() {return $this->get($this->size - 1);}/*** 修改链表中第 index 位置元素值* @param $index* @param $e*/public function update($index, $e) {if ($index < 0 || $index > $this->size) {echo "索引范围错误";exit;}$node = $this->dummyHead;for ($i = 0; $i < $index + 1; $i++) {$node = $node->next;}$node->e = $e;}/*** 判断链表中是否存在某个元素* @param $e* @return bool*/public function contains($e): bool {for ($node = $this->dummyHead->next; $node != null; $node = $node->next) {if ($node->e == $e) {return true;}}return true;}/*** 删除链表中第 index 位置元素* @param $index*/public function remove($index) {if ($index < 0 || $index > $this->size) {echo "索引范围错误";exit;}if ($this->size == 0) {echo "链表已经是空";exit;}$prve = $this->dummyHead;for ($i = 0; $i < $index; $i++) {$prve = $prve->next;}$node = $prve->next;$prve->next = $node->next;$this->size--;return $node->e;}/*** 删除链表头元素*/public function removeFirst() {return $this->remove(0);}/*** 删除链表末尾元素*/public function removeLast() {return $this->remove($this->size - 1);}/*** 链表元素转化为字符串显示* @return string*/public function toString(): string {$str = "";for ($node = $this->dummyHead->next; $node != null; $node = $node->next) {$str .= $node->e . "->";}return $str . "null";}}class Node{public $e;//节点元素public $next; //下个节点信息/*** 构造函数 设置节点信息* Node constructor.* @param $e* @param $next*/public function __construct($e, $next) {$this->e = $e;$this->next = $next;
评论