查看: 6601|回复: 25
收起左侧

Microsoft : 一个栈实现队列

|只看干货 |刷题
头像被屏蔽

分享帖子到朋友圈
wwwyhx | 显示全部楼层 |阅读模式
提示: 作者被禁止或删除 内容自动屏蔽

上一篇:求杨氏矩阵第k大的值
下一篇:Microsoft : Rearrange an array of positive and negative integers,
nicholasx 2011-6-9 14:13:05 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (12)
 
 
0% (0)    👎
没想出来。。。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();
    }
}
回复

使用道具 举报

头像被屏蔽
 楼主| wwwyhx 2011-6-11 11:56:40 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

bignews 2011-6-11 14:13:09 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (233)
 
 
1% (4)    👎
本帖最后由 暗影吉他手 于 2011-6-11 22:39 编辑
考虑到函数调用本身就是另外一个栈,所以可以利用递归实现

参考你的idea写的伪代码
游客,本帖隐藏的内容需要积分高于 50 才可浏览,您当前积分为 0。
查看如何攒积分解锁阅读权限
回复

使用道具 举报

pocketlion 2011-12-31 06:12:45 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (12)
 
 
0% (0)    👎
回复 4# 暗影吉他手


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

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

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

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

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

谢谢了~~
回复

使用道具 举报

bignews 2011-12-31 10:40:27 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (233)
 
 
1% (4)    👎
回复 5# pocketlion

exactly
回复

使用道具 举报

pocketlion 2011-12-31 11:53:05 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (12)
 
 
0% (0)    👎
本帖最后由 pocketlion 于 2011-12-31 12:15 编辑

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

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

使用道具 举报

mimighost007 2011-12-31 21:58:21 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   96% (200)
 
 
3% (7)    👎
恩,确实必须要两个栈,拿函数当栈的想法很好啊!
回复

使用道具 举报

bignews 2012-1-1 07:00:29 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (233)
 
 
1% (4)    👎
回复 7# pocketlion

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

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

使用道具 举报

pocketlion 2012-1-1 16:25:50 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (12)
 
 
0% (0)    👎
回复 9# 暗影吉他手


    thanks
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://tools.1point3acres.com/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

>
快速回复 返回顶部 返回列表