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 "
不能添加相同的编号";

                        }

                        $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 "
编号：".$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 "
没有找到目标";}            

            }

        }

        $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;

 

 

QQ截图20140706152241

 

删除操作示意图：

 

if($cur->next!=null)

    $cur->next->pre=$cur->pre;

$cur->pre->next=$cur->next;

 

 

QQ截图20140706152857

 

栈                                                                                              

 

复制代码

 

    class myStack

    {

        private $top=-1;

        private $maxSize=5;

        private $stack=array();

        public function push($val)

        {

            if($this->top == $this->maxSize)

            {

                echo "
已经满了";

            }

            $this->top++;

            $this->stack[$this->top]=$val;

        }

        

        public function showStack()

        {

            if($this->top==-1)

            {

                echo "
栈为空！";

                return ;

            }

            for($i=$this->top;$i>-1;$i--)

            {

                echo "
stack[".$i."]=".$this->stack[$i];

            }

        }

        

        public function pop()

        {

            if($this->top==-1)

            {

                echo "
栈为空！";

                return ;

            }

            

            $val=$this->stack[$this->top];

            $this->top--;

            echo "
弹出".$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函数。