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

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

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

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

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

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

PHP实现代码如下:

1. <?php
2. class DoubleQueue
3. {
4. public $queue = array();
5. /**（尾部）入队 **/
6. public function addLast($value)
7. {
8. return array_push($this->queue,$value);
9. }
10. /**（尾部）出队**/
11. public function removeLast()
12. {
13. return array_pop($this->queue);
14. }
15. /**（头部）入队**/
16. public function addFirst($value)
17. {
18. return array_unshift($this->queue,$value);
19. }
20. /**（头部）出队**/
21. public function removeFirst()
22. {
23. return array_shift($this->queue);
24. }
25. /**清空队列**/
26. public function makeEmpty()
27. {
28. unset($this->queue);
29. }
30. /**获取列头**/
31. public function getFirst()
32. {
33. return reset($this->queue);
34. }
35. /** 获取列尾 **/
36. public function getLast()
37. {
38. return end($this->queue);
39. }
40. /** 获取长度 **/
41. public function getLength()
42. {
43. return count($this->queue);
44. }
45. }

例子,编写支持双端队伍的例程,每种操作均花费O（1）时间,代码如下:

1. <?php
2. class deque
3. {
4. public $queue = array();
5. public $length = 0;
6. public function frontAdd($node){
7. array_unshift($this->queue,$node);
8. $this->countqueue();
9. }
10. public function frontRemove(){
11. $node = array_shift($this->queue);
12. $this->countqueue();
13. return $node;
14. }
15. public function rearAdd($node){
16. array_push($this->queue,$node);
17. $this->countqueue();
18. }
19. public function rearRemove(){
20. $node = array_pop($this->queue);
21. $this->countqueue();
22. return $node;
23. }
24. public function countqueue(){
25. $this->length = count($this->queue);
26. }
27. }
28. $fruit = new deque();
29. echo $fruit -> length;
30. $fruit -> frontAdd("Apple");
31. $fruit -> rearAdd("Watermelon");
32. echo '<pre>';
33. print_r($fruit);
34. echo '</pre>';
35. ?>
36. /*结果
37. 0
38. deque Object
39. (
40. [queue] => Array
41. (
42. [0] => Apple
43. [1] => Watermelon
44. )
45. [length] => 2
46. )*/