数据结构之栈——链式存储结构（php代码实现）

<?php
/**
    1. DestroyStack(): 栈的销毁
    2. ClearStack(): 将栈置为空栈
    3. StackEmpty(): 判断栈是否为空
    4. StackLength(): 返回栈的长度
    5. GetTop(): 取得栈顶的元素
    6. Push(): 插入新的栈顶元素
    7. Pop(): 删除栈顶元素
    8. StackTraverse(): 遍历栈元素
 */
class LNode{
    public $data;
    public $next;
    public function __construct($data=null){
        $this->data=$data;
        $this->next=null;
    }
}
class LinkStack{
    private  $top;
    //用于指向栈顶结点，也就是第一个结点。相对于头指针.此时或许有人有疑问了，你之前不是说this代表头指针吗？为什么现在有变成top为头指针了呢？
// 答：
//   之所以之前this代表头指针，是因为它指向了一个和其它结点一样的结点——头结点（实例化后的对象即为头结点，因为其初始化的数据域自始至终都为null）。而此处的this并没有指向和其它结点一样的结点（即头结点），也不指向第一个结点，另外，因为对没有头结点的链表的操作(比如清空链表)，需要判断当前的指针是否为空，而此时若是this指向第一个结点，那么这个链表将永远不会为空（因为this代表两个一个实例化的对象，始终是一个内存地址）。所以此处的this不是且不能是头指针。因而需要单独指定一个成员属性top，用于指向第一个结点，因为其可以为null，所以top就是我们定义的头指针。此处的关键点在于，是否在类中要声明和结点类（即LNode）一样的成员属性，若一样则就是包含头结点的链式结构，若是仅包含一个指针域的属性则就是不包含头结点的链式结构。由此，我们可以知道，关于一些边界判断的条件，是由我们编程者自己来决定的，不需要拘泥于形式，只要满足操作要求即可。


    private $length;//用于指定链栈的长度
    public function __construct(){
        $this->top=null;
        $this->length=0;
    }
    //销毁链栈
    public function DestroyStack(){
        while($this->top){
            $p=$this->top->next;
            unset($this->top);
            $this->top=$p;
        }
        $this->length=0;
    }

    //清空链栈
    public function ClearStack(){
        $p=$this->top;
        while($p){
            $q=$p->next;
            unset($p);
            $p=$q;
        }
        $this->top=null;
        $this->length=0;
    }

    //链栈是否为空
    public function StackEmpty(){
        if($this->top==null){
            return 'Null';
        }else{
            return 'NO Null';
        }
    }

    //链栈的长度
    public function StackLength(){
        return $this->length;
    }

    //取得栈顶的元素
    public function GetTop(){
        if($this->top!=null){
            return $this->top->data;
        }
    }

    //插入新的栈顶结点
    public function Push(){
        $node=new LNode(mt_rand(10,20));
        $node->next=$this->top;
        $this->top=$node;
        $this->length++;
    }

    //删除栈顶元素
    public function Pop(){
        if($this->top!=null){
            $p=$this->top->next;
            unset($this->top);
            $this->top=$p;
            $this->length--;
        }
    }

    //遍历栈元素
    public function StackTraverse(){
        $arr=array();
        if($this->top !=null){
            $p=$this->top;
            while($p){
                $arr[]=$p->data;
                $p=$p->next;
            }
        }
        return $arr;
    }
}