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

末蓝、 2022-07-19 01:55 123阅读 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>";  
?>