Microsoft : 一个栈实现队列

用一个栈实现队列的先进先出特性

没想出来。。。google到的，和大家share一下：

public class SimulatedQueue<E> {
    private java.util.Stack<E> stack = new java.util.Stack<E>();
    public void insert(E elem) {
        if (!stack.empty()) {
            E topElem = stack.pop();
            insert(elem);
            stack.push(topElem);
        }
        else
            stack.push(elem);
    }
    public E remove() {
        return stack.pop();
    }
}

恩，最plan old的方法就是用两个栈实现队列的功能。
由于题目要求只能用一个栈，但是考虑到函数调用本身就是另外一个栈，所以可以利用递归实现

考虑到函数调用本身就是另外一个栈，所以可以利用递归实现

参考你的idea写的伪代码

您好！
本帖隐藏的内容需要积分高于 50 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 50 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

回复 4# 暗影吉他手


   整个算法我看了下，感觉自己理解不知对不对，想向大神们请教下是不是如下过程：

   入队QueueIn(val)的话直接入栈 push(val);

   出队QueueOut是不是相当于利用函数递归从栈顶开始多次调用QueueOut()让顶元素出栈，放到tmp，直到到达栈底，将栈底输出，其他放在tmp的元素依次push进去。不知我理解对吗？

开始
      栈底{a1,a2,a3,a4,a5} 栈顶

最后
     栈底{a2,a3,a4,a5} 栈顶     a1输出

谢谢了～～

回复 5# pocketlion

exactly

回复 6# 暗影吉他手
thanks a lot     
还有2个问题想请教下:
执行过程中由于递归多次调用到queueout（）
其中每次用tmp变量来存放取出的栈顶元素   这是不是意味着在递归的过程中计算机需要分配多个空间（多个不同的tmp）来存放每次调用queueout取的栈顶元素？

对于每一个被调用的queueout()来说，只有当其调用的下一层queueout()返回所需rel值 ，然后执行push（tmp）后才能将tmp所占空间释放？

恩，确实必须要两个栈，拿函数当栈的想法很好啊！

回复 7# pocketlion

每次递归相当于执行了新的函数，局部变量都是新的

不过函数栈空间不需要分配和释放，在线程建立初期栈空间就已经分配好了。或者可以理解为，当函数返回的时候本函数所占用的全部栈空间都被释放了。

回复 9# 暗影吉他手


    thanks