用PHP实现一个双向队列-貌似是腾讯的一道笔试题

Filed under: PHP/WEB — Tags: , , — 花太香齐 @ 2009年08月13日 8:48 pm
本blog文章如没特殊声明均为原创文章，转载请注明出处，谢谢！

用PHP实现一个双向队列-腾讯笔试题？

队列只能对头尾两个元素操作
单向队列只能从头进，从尾出
双向队列则头尾均可push,pop

baidu和google上没有查到PHP双向队列的资料，搜索到java的双向队列定义如下：双向队列（双端队列）就像是一个队列，但是你可以在任何一端添加或移除元素。
而双端队列是一种数据结构，定义如下：
A deque is a data structure consisting of a list of items, on which the following operations are possible.
* push(D,X) — insert item X on the rear end of deque D.
* pop(D) — remove the front item from the deque D and return it.
* inject(D,X) — insert item X on the front end of deque D.
* eject(D) — remove the rear item from the deque D and return it.
Write routines to support the deque that take O(1) time per operation.

翻译：双端队列（deque）是由一些项的表组成的数据结构，对该数据结构可以进行下列操作：
push(D,X) 将项X 插入到双端队列D的前端
pop(D) 从双端队列D中删除前端项并将其返回
inject(D,X) 将项X插入到双端队列D的尾端
eject(D) 从双端队列D中删除尾端项并将其返回
编写支持双端队伍的例程，每种操作均花费O（1）时间

百度百科：（deque，全名double-ended queue）是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。

附我的解答程序：

<?php
 
class DoubleQueue 
{
    public $queue = array();
    
    /**（尾部）入队  **/
    public function push($value) 
    {
        return array_push($this->queue,$value);
    }
    /**（尾部）出队**/
    public function pop() 
    {
        return array_pop($this->queue);
    }
    /**（头部）入队**/
    public function enq($value) 
    {
        return array_unshift($this->queue,$value);
    }
    /**（头部）出队**/
    public function deq() 
    {
        return array_shift($this->queue);
    }
    /**清空队列**/
    public function makeEmpty() 
    {
        return unset($this->queue);
    }
 
}
 
class DoubleDueue 
{
    public $queue = array();
 
    public function push($value) 
    {
        return $this->queue[] = $value;
    }
 
    public function pop() 
    {
        $count = $this->count();
        if($count >= 1) 
        {
            $value = $this->queue[$count-1];
            unset($this->queue[$count-1]);
            return $value;
        }
        else
        {
            return false;
        }
    }
 
    public function enq($value) 
    {
        /*不好做*/
    }
    public function deq() 
    {
        /*不好做*/
    }
 
    public function count() 
    {
        return count($this->queue);
    }
    public function makeEmpty() 
    {
        return unset($this->queue);
    }
}
 
 
?>

貌似可以用php的四个函数解决：

array_push — 将一个或多个单元压入数组的末尾（入栈）
array_unshift — 在数组开头插入一个或多个单元
array_pop — 将数组最后一个单元弹出（出栈）
array_shift — 将数组开头的单元移出数组

参考资料：

http://www.hiahia.org/datastructure/zhanhuoduilie/zhanhuoduilie3.2.1.htm

http://phpcup.cn/viewthread.php?tid=366

评论

发表新评论