PHP implements two-way linked list and stack_PHP tutorial

PHP implements two-way linked list and stack

Doubly linked list                                                  

Copy code

//Double linked list

class Hero

{

public $pre=null;//pre pointer

public $no;//ranking

public $name;//name

public $next=null;//Next pointer

                                                                   

/**

*Constructor, declares the head of the linked list

*/

public function __construct($no='',$name='')

           {

$this->no=$no;

$this->name=$name;

      }

/**

*Insert

*/

static public function addHero($head,$hero)

           {

$cur = $head;

$isExist=false;

// Determine whether the current linked list is empty

if($cur->next==null)

              {

$cur->next=$hero;

$hero->pre=$cur;

        }

          else

              {

// If it is not an empty node, arrange the name to add

                                                                                                                                                                                                                                     .

                while($cur->next!=null)

                                                           

                                                                                                                                                                                                                                                                                                  to have

                                                                                                                                                                                                                    {//If it is greater than the ranking, jump out

break;

                }

Else If ($ Cur-& GT; Next-& GT; NO == $ Hero-GT; NO)

// If it is equal to the ranking, it means that this element is

                                $isExist=true;

                                                                                                                                                                                                                                                    echo "
Cannot add the same number";

                }

$cur=$cur->next;

          }

                                                                                                                                                                                   

                                                                                                                                                                                                                         {//If the element does not exist, perform the insertion operation

                                                                                                                                                                                                           

                        {$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 screenshot 20140706152241

Delete operation diagram:

if($cur->next!=null)

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

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

QQ screenshot 20140706152857

Stack                                                                              

Copy code

class myStack

{

private $top=-1;

private $maxSize=5;

private $stack=array();

public function push($val)

{

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

           {

echo "
Already full";

      }

$this->top++;

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

}

public function showStack()

{

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

           {

                  echo "
The stack is empty!";

            return ;

      }

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

           {

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

      }

}

public function pop()

{

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

           {

                  echo "
The stack is empty!";

            return ;

      }

                                                                   

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

$this->top--;

echo "
pop-up".$val;

}

}

$mystack = new myStack;

$mystack->push('111');

$mystack->push('222');

$mystack->showStack();

$mystack->pop();

$mystack->pop();

?>

Copy code

Stack: It is a linear table that limits insertion and deletion operations to one end of the table. Also known as LIFO (Last In First Out) or FILO (First In Last Out) linear table.

There are many ways to implement stacks in computers:

Hard stack: Implemented by utilizing certain register banks in the CPU or similar hardware or using a special area of ​​memory. This type of stack has limited capacity, but is fast;

Soft stack: This type of stack is mainly implemented in memory. Stack capacity can be very large. In terms of implementation methods, there are two types: dynamic method and static method

Top of the stack (Top): The end that allows insertion and deletion operations, also called the tail of the table. Use the stack top pointer (top) to indicate the top element of the stack.

Bottom: It is the fixed end, also called the header.

Empty stack: When there are no elements in the table, it is called an empty stack.

The linked storage structure of the stack is called a linked stack, which is a singly linked list with limited operations. The insertion and deletion operations can only be performed at the header position. Therefore, there is no need to attach a head node to the linked stack like a singly linked list. The top pointer on the stack is the head pointer of the linked list.

Of course, the array API in php has push and pop functions.

http://www.bkjia.com/PHPjc/845432.htmlwww.bkjia.comtruehttp: //www.bkjia.com/PHPjc/845432.htmlTechArticlePHP implements doubly linked list and stack doubly linked list copy code?php //doubly linked list class Hero { public $pre=null ;//Front pointer public $no;//Ranking public $name;//Name public $next=null;//Back pointer...