关于php:数据结构PHP通过链表类对象实现-栈

这篇文章是展现如何应用 PHP 语言实现的链表类 (LinkedList)，而后通过链表来实现的 栈(Stack) 只能从栈顶增加元素，也只能从栈顶取出元素，是一种 Last In First Out(LIFO)，即  后进先出 的构造。

1.output_stack_by_linked_list.php

这是一个调用和打印输出后果的展现文件：

<?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(); // 查看栈顶元素，打印 hh
echo "<br>";
echo $stack->toString(); // 打印栈数据 hh->gg->ff->ee->dd->cc->bb->aa->null
echo "<br>";
echo $stack->pop();  // 出栈，打印 hh
echo "<br>";
echo $stack->toString(); // 打印栈数据 gg->ff->ee->dd->cc->bb->aa->null

2.StackByLinkedList 类

这是一个封装好的 栈 (Stack)，通过实例化 链表类 (LinkedList) 实现了 入栈 (push) 和 出栈 (pop)，还有 查看栈顶(peek):

<?php
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

<?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.LinkedList 类

这是封装好的一个链表类，能实现链表的基本功能：

<?php
/**
 * 链表的实现
 * 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;
    }
}