问题来源于wwwyhx同学在一亩三分地论坛编程技术版上提供的一道Microsoft面试题,大意是如何仅使用一个栈来实现队列的数据结构,满足FIFO特性。在网上类似的问题一般是用两个栈来实现,当然就很简单了。那么如果要求只用一个栈来实现该怎么做呢?

wwwyhx同学给出了解题思路[1],即“考虑到函数调用本身就是另外一个栈,所以可以利用递归实现”。确实是个不错的想法,虽然加上function call本身使用的栈也算是用了两个栈,但是毕竟那个是隐性的,我们在程序中只需要建立一个stack即可,很有技巧性。

于是我根据wwwyhx同学的思路,给出了伪代码实现:

QueueIn(val)
{
    push(val);
}

QueueOut()
{
    tmp = pop();
    if (!IsStackEmpty())
    {
        rel = QueueOut();
        push(tmp);
        return rel;
    }
    else
    {
        return tmp;
    }
}

程序使用C语言验证通过。

参考资料:
[1] [编程题] Microsoft : 一个栈实现队列

» 转载请注明来源及链接:未来代码研究所

Related Posts:

2 Responses to “用一个栈实现队列”

Leave a Reply

World Line
Time Machine
Online Tools