PHP实现一个双向队列例子

作者:袖梨 2022-06-24

双端队列(deque)是由一些项的表组成的数据结构,对该数据结构可以进行下列操作:

    push(D,X) 将项X 插入到双端队列D的前端
    pop(D) 从双端队列D中删除前端项并将其返回
    inject(D,X) 将项X插入到双端队列D的尾端
    eject(D) 从双端队列D中删除尾端项并将其返回

PHP实现代码

 代码如下 复制代码
class DoubleQueue 
{
    public $queue = array();
    
    /**(尾部)入队  **/
    public function addLast($value) 
    {
        return array_push($this->queue,$value);
    }
    /**(尾部)出队**/
    public function removeLast() 
    {
        return array_pop($this->queue);
    }
    /**(头部)入队**/
    public function addFirst($value) 
    {
        return array_unshift($this->queue,$value);
    }
    /**(头部)出队**/
    public function removeFirst() 
    {
        return array_shift($this->queue);
    }
    /**清空队列**/
    public function makeEmpty() 
    {
        unset($this->queue);
    }
    
    /**获取列头**/
    public function getFirst() 
    {
        return reset($this->queue);
    }
 
    /** 获取列尾 **/
    public function getLast() 
    {
        return end($this->queue);
    }
 
    /** 获取长度 **/
    public function getLength() 
    {
        return count($this->queue);
    }
    
}

例子

编写支持双端队伍的例程,每种操作均花费O(1)时间

 代码如下 复制代码

class deque
{
 public $queue  = array();
 public $length = 0;
  
 public function frontAdd($node){
  array_unshift($this->queue,$node);
  $this->countqueue();
 }
 public function frontRemove(){
  $node = array_shift($this->queue);
  $this->countqueue();
  return $node;
 }
  
 public function rearAdd($node){
  array_push($this->queue,$node);
  $this->countqueue();
 }
 
 public function rearRemove(){
  $node = array_pop($this->queue);
  $this->countqueue();
  return $node;
 }
 
 public function countqueue(){
  $this->length = count($this->queue);   
 }
}
$fruit = new deque();
echo $fruit -> length;
$fruit -> frontAdd("Apple");
$fruit -> rearAdd("Watermelon");
echo '

';
print_r($fruit);
echo '
';
?>

结果

0
deque Object
(
    [queue] => Array
        (
            [0] => Apple
            [1] => Watermelon
        )
    [length] => 2
)

相关文章

精彩推荐