前期写过一个PHP实现单向链表、实现排序单向链表的一篇文章，传送门：http://www.cnblogs.com/yydcdut/p/3777760.html。双向链表写过了，再拿出来提一提：http://www.cnblogs.com/yydcdut/p/3782661.html。

这次再来分享一下实现双向链表和栈的实现。代码虽然是以前写的了，但是发现PHP写的这些代码很容易看懂！

双向链表

<?php        //双向链表        class Hero        {            public $PRe=null;//前指针            public $no;//排名            public $name;//名字            public $next=null;//后指针                        /**            *构造函数，申明链表头            */            public function __construct($no='',$name='')            {                $this->no=$no;                $this->name=$name;            }            /**            *插入            */            static public function addHero($head,$hero)            {                $cur = $head;                $isExist=false;                //判断目前这个链表是否为空                if($cur->next==null)                {                    $cur->next=$hero;                    $hero->pre=$cur;                }                else                {                    //如果不是空节点，则安排名来添加                    //找到添加的位置                                while($cur->next!=null)                    {                        if($cur->next->no > $hero->no)                        {//如果大于了排名，跳出                            break;                        }                        else if($cur->next->no == $hero->no)                        {//如果等于排名，则代表有这个元素了                            $isExist=true;                            echo "<br>不能添加相同的编号";                        }                        $cur=$cur->next;                    }                    if(!$isExist)                    {//如果元素不存在，执行插入操作                        if($cur->next!=null)                        {$hero->next=$cur->next;}                        $hero->pre=$cur;                        if($cur->next!=null)                        {$hero->next->pre=$hero;}                        $cur->next=$hero;                                }                }            }            //遍历            static public function showHero($head)            {                $cur=$head;                while($cur->next!=null)                {                    echo "<br>编号：".$cur->next->no."名字：".$cur->next->name;                    $cur=$cur->next;                }            }                    static public function delHero($head,$herono)            {                $cur=$head;                $isFind=false;                while($cur!=null)                {                    if($cur->no==$herono)                    {                        $isFind=true;                        break;                    }                    //继续找                    $cur=$cur->next;                }                if($isFind)                {                    if($cur->next!=null)                    {$cur->next_pre=$cur->pre;}                    $cur->pre->next=$cur->next;                }                else                {echo "<br>没有找到目标";}                        }        }        $head = new Hero();        $hero1 = new Hero(1,'1111');        $hero3 = new Hero(3,'3333');        $hero2 = new Hero(2,'2222');        Hero::addHero($head,$hero1);        Hero::addHero($head,$hero3);        Hero::addHero($head,$hero2);        Hero::showHero($head);        Hero::delHero($head,2);        Hero::showHero($head);?>

双向链表的插入操作示意图：

if($cur->next!=null)    $hero->next=$cur->next;$hero->pre=$cur; if($cur->next!=null)    $hero->next->pre=$hero;$cur->next=$hero;

删除操作示意图：

if($cur->next!=null)    $cur->next->pre=$cur->pre;$cur->pre->next=$cur->next;

栈

<?php    class myStack    {        private $top=-1;        private $maxSize=5;        private $stack=array();        public function push($val)        {            if($this->top == $this->maxSize)            {                echo "<br>已经满了";            }            $this->top++;            $this->stack[$this->top]=$val;        }                public function showStack()        {            if($this->top==-1)            {                echo "<br>栈为空！";                return ;            }            for($i=$this->top;$i>-1;$i--)            {                echo "<br>stack[".$i."]=".$this->stack[$i];            }        }                public function pop()        {            if($this->top==-1)            {                echo "<br>栈为空！";                return ;            }                        $val=$this->stack[$this->top];            $this->top--;            echo "<br>弹出".$val;        }    }    $mystack = new myStack;    $mystack->push('111');    $mystack->push('222');    $mystack->showStack();    $mystack->pop();    $mystack->pop();?>

栈(Stack)：是限制在表的一端进行插入和删除操作的线性表。又称为后进先出LIFO (Last In First Out)或先进后出FILO (First In Last Out)线性表。

栈在计算机的实现有多种方式：

• 硬堆栈：利用CPU中的某些寄存器组或类似的硬件或使用内存的特殊区域来实现。这类堆栈容量有限，但速度很快；
• 软堆栈：这类堆栈主要在内存中实现。堆栈容量可以达到很大。在实现方式上，又有动态方式和静态方式两种

栈顶(Top)：允许进行插入、删除操作的一端，又称为表尾。用栈顶指针(top)来指示栈顶元素。

栈底(Bottom)：是固定端，又称为表头。

空栈：当表中没有元素时称为空栈。

栈的链式存储结构称为链栈，是运算受限的单链表。其插入和删除操作只能在表头位置上进行。因此，链栈没有必要像单链表那样附加头结点，栈顶指针top就是链表的头指针。

当然，php中的数组API里面带的有push和pop函数。

我是天王盖地虎的分割线

《PHP实现链表》传送门：http://www.cnblogs.com/yydcdut/p/3777760.html

转载请注明出处：转载请注明出处：http://www.cnblogs.com/yydcdut