PHP数据结构之七_队列的链式存储和队列的基本操作-蒲公英云

PHP数据结构之七_队列的链式存储和队列的基本操作

PHP数据结构之七队列的链式存储和队列的基本操作

队列
1.定义：队列(Queue)：也是运算受限的线性表。是一种先进先出(First In First Out ，简称FIFO)的线性表。只允许在表的一端进行插入，而在另一端进行删除。
2.队首(front) ：允许进行删除的一端称为队首。
3.队尾(rear) ：允许进行插入的一端称为队尾。
4.队列的顺序存储表示
5.队列的链式存储表示
队列的链式存储结构简称为链队列，它是限制仅在表头进行删除操作和表尾进行插入操作的单链表。
队列的链式存储和队列的基本操作
<?php
/**
*队列的链式存储和队列的基本操作
*1.初始化队列
*2.链队列的入队操作
*3.链队列的出队操作
*4.仅返回队列中的全部元素
*5.返回队列元素个数
*6.判断队列是否为空
*7.将所有元素出队列
*
*@author xudianyang<>
*@version $Id:QueueLinked.class.php,v 1.0 2011/02/12 13:05:00 uw Exp
*@copyright ©2011,xudianyang
**/
header(“content-type:text/html;charset=gb2312”);
class QLNode{
public $mElem=null;
public $mNext=null;
}
class QueueLinked{
//队列“队首指针”
public $mFront=null;
//队列“队尾指针”
public $mRear=null;
//队列长度
public static $mLength=0;
public $mNext=null;
/**
*初始化队列
*
*@return void
*/
public function __construct(){
$this->mFront=$this;
$this->mRear=$this;
self::$mLength=0;
$this->mNext=null;
}
/**
*链队列的入队操作
*
*@param mixed $e 入队新元素值
*@return void
*/
public function getInsertElem($e){
$newLn=new QLNode();
$newLn->mElem=$e;
$newLn->mNext=null;
$this->mRear->mNext=$newLn;
$this->mRear=$newLn;
self::$mLength++;
}
/**
*链队列的出队操作
*
*@param mixed $e 出队的元素的值保存在此变量中
*@return boolean 成功返回true,否则返回false
*/
public function getDeleteElem(&$e){
if($this->mFront == $this->mRear){
return false;
}
$p=$this->mFront->mNext;
$e=$p->mElem;
$this->mFront->mNext=$p->mNext;
if($p==$this->mRear){
$this->mRear=$this->mFront;
}
self::$mLength—;
return true;
}
/**
*仅返回队列中的全部元素
*
*@return array 队列全部元素所组成的一个数组
*/
public function getAllElem(){
$qldata=array();
if($this->mFront==$this->mRear){
return $qldata;
}
$p=$this->mFront->mNext;
while($p!=null){
$qldata[]=$p->mElem;
$p=$p->mNext;
}
return $qldata;
}
/**
*返回队列元素个数
*
*@return int
*/
public function getLength(){
return self::$mLength;
}
/**
*判断队列是否为空
*
*@return boolean 为空返回true,否则返回false
*/
public function getIsEmpty(){
if($this->mFront == $this->mRear){
return true;
}else{
return false;
}
}
/**
*将所有元素出队列
*
*@return array 所有出队列的元素所组成的一个数组
*/
public function getDeleteAllElem(){
$qldata=array();
if($this->mFront == $this->mRear){
return $qldata;
}
while($this->mFront->mNext!=null){
$qldata[]=$this->mFront->mNext->mElem;
$this->mFront->mNext=$this->mFront->mNext->mNext;
self::$mLength—;
}
$this->mFront->mNext=null;
$this->mRear=$this->mFront;
return $qldata;
}
}
?>