链表及链表实现栈

<?php
/**
 * @Author: fql
 * @Email: fangqiulin4923@gmail.com
 * @Date: 2020-12-24 23:04
 */

namespace fql\aglorthim\structure;


//单向链表
class Node{
    public $elem;
    public $next;

    public function __construct($elem = null,Node $node = null)
    {
        $this->elem = $elem;
        $this->next = $node;
    }

    public  function next(Node $node){
        $this->next = $node;
    }
}

<?php
/**
 * @Author: fql
 * @Email: fangqiulin4923@gmail.com
 * @Date: 2020-12-23 23:13
 */

namespace fql\aglorthim\structure;

use Exception;

/**
 * Class LinkList
 * @desc 链表数据结构
 * @package fql\aglorthim\structure
 */
class LinkList
{
    public $head;           //头节点(默认一个虚拟头节点)
    public $size;           //长度

    public function __construct()
    {
        $this->head = new Node();
        $this->size  = 0;
    }


    /**
     * @param $index
     * @param $value
     * @throws Exception
     */
    public function add($index, $value)
    {
        if ($index > $this->size) {
            throw  new Exception('超出链表范围');
        }
        $prev = $this->head;
        for ($i = 0; $i < $index; $i++) {
            $prev = $prev->next;
        }
        $prev->next = new Node($value,$prev->next);
        $this->size++;
    }


    /**
     * @param $value
     * @throws Exception
     */
    public  function addFirst($value){
        $this->add(0,$value);
    }


    public function addLast($value){
        $this->add($this->size,$value);
    }

    public function select($index){
        if( $index > $this->size-1 )
            throw new Exception('超过链表范围');

        $prev = $this->head->next;
        for($i=0;$i<=$index;$i++){
            if( $i==$index )
                return $prev->elem;
            $prev = $prev->next;
        }
    }

    public function delete( $index ){
        if( $index > $this->size-1 )
            throw new Exception('超过链表范围');

        $prev = $this->head;
        for($i=0;$i<=$index;$i++){
            if( $i==$index )
                $prev->next = $prev->next->next;
            $prev = $prev->next;
        }
        $this->size--;
    }


    public function tostring(){

        $prev = $this->head->next;

        $r = [];
        while( $prev ){
            $r[] = $prev->elem;
            $prev = $prev->next;
        }
        return implode('->',$r);

    }
}

//
//$node = new Linklist();
//$node->addFirst(1);
//$node->add(1,7);
//$node->add(2,10);
//$node->addLast(99);
//var_export($node->tostring());

<?php
/**
 * @Author: fql
 * @Email: fangqiulin4923@gmail.com
 * @Date: 2020-12-24 22:39
 */

namespace fql\aglorthim\structure;

/**
 * Class LinklistStack
 * @desc 链表实现栈
 * @package fql\aglorthim\structure
 */
class LinklistStack extends LinkList
{

    /**
     * @param $value
     */
    public function push( $value ){
        $this->addFirst($value);
    }

    /**
     * @return mixed
     */
    public function pop(){
        $r = $this->head->next->elem;
        $this->delete(0);
        return $r;
    }
}
//echo 'd';
//$stack = new LinklistStack();
//$stack->push(1);
//
//$stack->push(2);
//$stack->push(3);
//$stack->push(4);
//
//print_r($stack->pop());
//print_r($stack->head);