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

码农天地 - 2020-10-21 02:12:45

---

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

php介绍

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

更多关于php的阅读

Tags 标签

php算法程序员

扩展阅读