问题来源于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;
}
}
{
push(val);
}
QueueOut()
{
tmp = pop();
if (!IsStackEmpty())
{
rel = QueueOut();
push(tmp);
return rel;
}
else
{
return tmp;
}
}
程序使用C语言验证通过。
参考资料:
[1] [编程题] Microsoft : 一个栈实现队列
» 转载请注明来源及链接:未来代码研究所
wwwyhx同学…
看来我要改昵称了….
@wwwyhx
囧,真不知道你的昵称是啥,暂且称呼为wwwyhx同学吧:)