deque,全名double-ended queue,是一种具有队列和栈的性质的数据结构,双端队列中的元素可以从两端弹出,其限定插入和删除操作在表的两端进行,双向队列(双端队列)就像是一个队列,但是你可以在任何一端添加或移除元素.
双端队列(deque)是由一些项的表组成的数据结构,对该数据结构可以进行下列操作:
push(d,x) 将项x 插入到双端队列d的前端
pop(d) 从双端队列d中删除前端项并将其返回
inject(d,x) 将项x插入到双端队列d的尾端
eject(d) 从双端队列d中删除尾端项并将其返回
php实现代码如下:
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）时间,代码如下:
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 )*/ 文章链接：
随便收藏，请保留本文地址！