deque,全名double-ended queue,是一种具有队列和栈的性质的数据结构,双端队列中的元素可以从两端弹出,其限定插入和删除操作在表的两端进行,双向队列(双端队列)就像是一个队列,但是你可以在任何一端添加或移除元素.

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

push(D,X) 将项X 插入到双端队列D的前端

pop(D) 从双端队列D中删除前端项并将其返回

inject(D,X) 将项X插入到双端队列D的尾端

eject(D) 从双端队列D中删除尾端项并将其返回

PHP实现代码如下:

<?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）时间,代码如下:

<?php
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 '<pre>';
print_r($fruit);
echo '</pre>';
/*结果
0 
deque Object 
( 
[queue] => Array 
( 
[0] => Apple 
[1] => Watermelon 
) 
[length] => 2 
)*/
?>

文章链接：http://www.phprm.com/shuzu/fs3240.html

随便收藏，请保留本文地址！