在创建链表的时候经常采用一种从头结点插入新结点的方法,可以采用这种方法来实现栈,最好使用带头结点的链表,这样可以保证对每个结点的操作都是相同的,实现思路如下图所示。
在上图中,在进行压栈操作的时候,首先需要创建新的结点,把待压栈的元素放到新结点的数据域中,然后只需要①和②两步就实现了压栈操作(把新结点加到了链表首部)。同理,在弹栈的时候,只需要进行③的操作就可以删除链表的第一个元素,从而实现弹栈操作(被删除的结点所占的存储空间需要被释放)。实现代码如下:
<?php
class LNode{
public $mElem;
public $mNext;
public function__Construct(){
$this->mElem=NULL;
$this->mNext=NULL;
}
}
class StackLinked{
//头“指针”,指向栈顶元素
public $mNext;
public static $mLength;
//初始化栈
public function__construct(){
$this->mNext=NULL;
self::$mLength=0;
}
/**
*判断栈是否空栈
*@return boolean如果为空栈返回true,否则返回false
*/
public function getIsEmpty(){
if($this->mNext==NULL){
return true;
}else{
return false;
}
}
/**
*将所有元素出栈
*@return array返回所有栈内元素
*/
public function getAllPopStack(){
$e=array();
if(!$this->getIsEmpty()){
while($this->mNext!=NULL){
$e[]=$this->mNext->mElem;
$this->mNext=$this->mNext->mNext;
}
}
self::$mLength=0;
return $e;
}
/**
*返回栈内元素个数
*@return int
*/
public static function getLength(){
return self::$mLength;
}
/**
*元素进栈
*@param mixed $e进栈元素值
*@return boolean进栈成功返回true
**/
public function push($e){
$newLn=new LNode();
$newLn->mElem=$e;
$newLn->mNext=$this->mNext;
$this->mNext=&$newLn;
self::$mLength++;
return true;
}
/**
*元素出栈
*@return boolean出栈成功返回true
**/
public function pop(){
if($this->getlsEmpty()){
return false;
}
$p=$this->mNext;
$e=$p->mElem;
$this->mNext=$p->mNext;
self::$mLength--;
return true;
}
/**
*返回栈内所有元素
*@return array栈内所有元素组成的一个数组
*/
public function getAllElem(){
$sldata=array();
if(!$this->getIsEmpty()){
$p=$this->mNext;
while($p!=NULL){
$sldata[]=$p->mElem;
$p=$p->mNext;
}
return $sldata;
}
}
/*
*返回栈顶元素
*@return $element返回栈顶元素
*/
public function top()
{
if($this->getIsEmpty()){
return false;
}
$list=$this->getAllElem();
$element=$list[0];
return $element;
}
}
$stack=new StackLinked();
$stack->push('1');
$stack->push('2');
$list=$stack->getAllElem();
echo $stack->top()."<br>";
$stack->pop();
echo $stack->top();
?>
程序的运行结果为
2
1