PHP数据结构之五 栈的PHP的实现和栈的基本操作

it2022-05-06  0

栈和队列是两种应用非常广泛的数据结构,它们都来自线性表数据结构,都是“操作受限”的线性表。  栈 栈在计算机的实现有多种方式: 硬堆栈:利用CPU中的某些寄存器组或类似的硬件或使用内存的特殊区域来实现。这类堆栈容量有限,但速度很快; 软堆栈:这类堆栈主要在内存中实现。堆栈容量可以达到很大。在实现方式上,又有动态方式和静态方式两种 1.定义: 栈(Stack):是限制在表的一端进行插入和删除操作的线性表。又称为后进先出LIFO (Last In First Out)或先进后出FILO (First In Last Out)线性表。 栈顶(Top):允许进行插入、删除操作的一端,又称为表尾。用栈顶指针(top)来指示栈顶元素。 栈底(Bottom):是固定端,又称为表头。 空栈:当表中没有元素时称为空栈。 2.栈的顺序存储表示 3.栈的链式存储表示 栈的链式存储结构称为链栈,是运算受限的单链表。其插入和删除操作只能在表头位置上进行。因此,链栈没有必要像单链表那样附加头结点,栈顶指针top就是链表的头指针。 下面是PHP实现的栈的基本操作,仅为本人个人创作,仅供参考! <?php /** *栈的链式储存表示和栈的基本操作 * *1.初始化栈 __construct() *2.判断栈是否空栈 getIsEmpty() *3.将所有元素出栈 getAllPopStack() *4.返回栈内元素个数 getLength() *5.元素进栈 getPushStack() *6.元素出栈 getPopStack() *7.仅返回栈内所有元素 getAllElem() *8.返回栈内某个元素的个数 getCountForElem() */ header("content-type:text/html;charset=gb2312"); class LNode{ public $mElem; public $mNext; public function __construct(){ $this->mElem=null; $this->mNext=null; } } class StackLinked{ //头“指针”,指向栈顶元素 public $mNext; public static $mLength; /** *初始化栈 * *@return void */ 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()){ }else{ 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 void **/ public function getPushStack($e){ $newLn=new LNode(); $newLn->mElem=$e; $newLn->mNext=$this->mNext; $this->mNext=&$newLn; self::$mLength++; } /** *元素出栈 * *@param LNode $e 保存出栈的元素的变量 *@return boolean 出栈成功返回true,否则返回false **/ public function getPopStack(&$e){ if($this->getIsEmpty()){ return false; } $p=$this->mNext; $e=$p->mElem; $this->mNext=$p->mNext; self::$mLength--; } /** *仅返回栈内所有元素 * *@return array 栈内所有元素组成的一个数组 */ public function getAllElem(){ $sldata=array(); if($this->getIsEmpty()){ }else{ $p=$this->mNext; while($p!=null){ $sldata[]=$p->mElem; $p=$p->mNext; } return $sldata; } /** * 返回栈内某个元素的个数 * * @param mixed $e 待查找的元素的值 * @return int * */ public function getCountForElem($e){ $allelem=$this->getAllElem(); $count=0; foreach($allelem as $value){ if($e === $value){ $count++; } } return $count; } } echo "<pre>"; $sl=new StackLinked(); var_dump($sl->getIsEmpty()); $sl->getPushStack(12); $sl->getPushStack(255); var_dump($sl->getIsEmpty()); var_dump($sl->getAllElem()); echo $sl->getLength(); $e=0; echo "\r\n"; var_dump($sl->getIsEmpty()); echo "\r\n"; $sl->getPopStack($e); echo $e; echo "\r\n"; echo $sl->getLength(); echo "\r\n"; var_dump($sl->getAllElem()); var_dump($sl->getAllPopStack()); var_dump($sl->getIsEmpty()); var_dump($sl->getLength()); echo "</pre>"; ?>

 

 

转载于:https://www.cnblogs.com/crystaltu/p/6408528.html


最新回复(0)