June 25th, 2011 | 
问题来源于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 : 一个栈实现队列
» 转载请注明来源及链接：未来代码研究所
Posted in 
Tags: 
wwwyhx同学…
看来我要改昵称了….
@wwwyhx
囧，真不知道你的昵称是啥，暂且称呼为wwwyhx同学吧:)