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 '