📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 7937| 回复: 25
跳转到指定楼层
上一主题 下一主题
收起左侧

Microsoft : 一个栈实现队列

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

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

上一篇:求杨氏矩阵第k大的值
下一篇:Microsoft : Rearrange an array of positive and negative integers,
🔗
nicholasx 2011-6-9 14:13:05 | 只看该作者
全局:
没想出来。。。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 | 只看该作者
全局:
恩,最plan old的方法就是用两个栈实现队列的功能。
由于题目要求只能用一个栈,但是考虑到函数调用本身就是另外一个栈,所以可以利用递归实现
回复

使用道具 举报

🔗
bignews 2011-6-11 14:13:09 | 只看该作者
全局:
本帖最后由 暗影吉他手 于 2011-6-11 22:39 编辑
考虑到函数调用本身就是另外一个栈,所以可以利用递归实现

参考你的idea写的伪代码
您好!
本帖隐藏的内容需要积分高于 50 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 50 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
pocketlion 2011-12-31 06:12:45 | 只看该作者
全局:
回复 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 | 只看该作者
全局:
回复 5# pocketlion

exactly
回复

使用道具 举报

🔗
pocketlion 2011-12-31 11:53:05 | 只看该作者
全局:
本帖最后由 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 | 只看该作者
全局:
恩,确实必须要两个栈,拿函数当栈的想法很好啊!
回复

使用道具 举报

🔗
bignews 2012-1-1 07:00:29 | 只看该作者
全局:
回复 7# pocketlion

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

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

使用道具 举报

🔗
pocketlion 2012-1-1 16:25:50 | 只看该作者
全局:
回复 9# 暗影吉他手


    thanks
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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