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;
QQ截圖20140706152241
刪除操作示意圖：
if($cur->next!=null)
$cur->next->pre=$cur->pre;
$cur->pre->next=$cur->next;
QQ截圖20140706152857
棧
復制代碼
<?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函數。
