数据结构--链表/栈/队列

末蓝、 2023-02-11 08:52 33阅读 0赞

<?php
    class Node {
    	public $val;
    	public $next;
    	
    	public function __construct($val=null,$next=null){
    		$this->val = $val;
    		$this->next = $next;
    	}
    }
    
    class LinkList {
    	public $head;
    	public $size;
    	
    	public function __construct(){
    		$this->head = new Node();
    		$this->size = 0;
    	}
    	
    	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++;
    	}
    	
    	public function addFirst($value){
    		$this->add(0,$value);
    	}
    	
    	public function addLast($value){
    		$this->add($this->size,$value);
    	}
    	
    	public function edit($index,$value){
    		if($index > $this->size-1){
    			throw new Exception("超出链表范围");
    		}
    		
    		$prev = $this->head->next;
    		for($i=0;$i<=$index;$i++){
    			if($i == $index){
    				$prev->val = $value;
    			}
    			$prev=$prev->next;
    		}
    	}
    	
    	public function findByIndex($index){
    		if($index>$this->size-1){
    			throw new Exception("超出链表范围");
    		}
    		$prev = $this->head->next;
    		for($i=0;$i<=$index;$i++){
    			if($i == $index){
    				return $prev->val;
    			}
    			$prev = $prev->next;
    		}
    		return false;
    	}
    	
    	public function findByValue($value){
    		if($index>$this->size-1){
    			throw new Exception("超出链表范围");
    		}
    		$prev = $this->head->next;
    		while($prev){
    			if($prev->val == $value){
    				return true;
    			}
    			$prev = $prev->next;
    		}
    		return false;
    	}
    	
    	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;
    		}
    	}
    }
    
    // $obj = new LinkList();
    // $obj->add(0,10);
    // $obj->add(1,20);
    // var_dump($obj);
    // $obj->add(2,30);
    // var_dump($obj);
    
    // $obj->addFirst(1);
    // var_dump($obj);
    // $obj->addLast(40);
    // var_dump($obj);
    
    // $obj->edit(4,50);
    // var_dump($obj);
    
    // $tmp = $obj->findByIndex(4);
    // var_dump($tmp);
    
    // $tmp = $obj->findByValue(30);
    // var_dump($tmp);
    
    // $obj->delete(4);
    // var_dump($obj);
    
    class LinkListStack extends LinkList {
    	public function push($value){
    		$this->addFirst($value);
    	}
    	
    	public function pop(){
    		$tmp = $this->head->next->val;
    		$this->delete(0);
    		return $tmp;
    	}
    }
    
    // $obj = new LinkListStack();
    // $obj->push(1);
    // $obj->push(2);
    // $obj->push(3);
    // var_dump($obj);
    // $tmp = $obj->pop();
    // var_dump($tmp);
    // var_dump($obj);
    
    class LinkListQueue extends LinkList {
    	public $tail;
    	
    	public function push($value){
    		if( $this->head->val == null ){
    			$this->tail = new Node($value);
    			$this->head = $this->tail;
    		}else{
    			$this->tail->next = new Node($value);
    			$this->tail = $this->tail->next;
    		}
    		$this->size++;
    	}
    	
    	public function pop(){
    		if( $this->size<=0 ){
    			throw new Exception("超出链表范围");
    		}
    		
    		$val = $this->head->val;
    		$this->head = $this->head->next;
    		
    		$this->size--;
    		return $val;
    	}
    }
    
    $obj = new LinkListQueue();
    $obj->push(1);
    $obj->push(2);
    $obj->push(3);
    var_dump($obj);
    $tmp = $obj->pop();
    var_dump($tmp);
    var_dump($obj);