这篇文章是展现如何应用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(); //查看栈顶元素，打印 hhecho "<br>";echo $stack->toString(); //打印栈数据 hh->gg->ff->ee->dd->cc->bb->aa->nullecho "<br>";echo $stack->pop();  //出栈，打印 hhecho "<br>";echo $stack->toString(); //打印栈数据 gg->ff->ee->dd->cc->bb->aa->null

2.StackByLinkedList 类

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

<?phprequire '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

<?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.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;    }}