前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >[随缘一题]用栈实现队列

[随缘一题]用栈实现队列

作者头像
呼延十
发布2019-07-01 16:52:59
4240
发布2019-07-01 16:52:59
举报
文章被收录于专栏:呼延

来源

lintcode-用栈实现队列

描述

正如标题所述,你需要使用两个栈来实现队列的一些操作。

队列应支持push(element),pop() 和 top(),其中pop是弹出队列中的第一个(最前面的)元素。

pop和top方法都应该返回第一个元素的值。

样例

代码语言:javascript
复制
比如push(1), pop(), push(2), push(3), top(), pop(),你应该返回1,2和2

挑战

仅使用两个栈来实现它,不使用任何其他数据结构,push,pop 和 top的复杂度都应该是均摊O(1)的

解题思路

暴躁版本

这道题首先很容易想到暴躁版本.

首先有两个栈,主栈main和辅助栈helper.

  1. push()的时候直接向main中添加.
  2. pop()/top()的时候,将当前所有元素从main出栈,然后helper入栈.然后弹出栈顶元素.
  3. 将弹出后的所有元素从helper出栈,main入栈,恢复原来的次序,方便后续继续push.

举例:

代码语言:javascript
复制
1. push(1) -----> main=1,helper=empty
2. push(2) -----> main=2,1.helper=empty
3. pop(1)  -----> main=empty,helper=1,2 -> main=empty,helper=2 -> main=2,helper=empty.

这种方式简单粗暴,但是在pop()/top()的过程中,要先将元素从main全部转移至helper,出栈后有全部转移回来.这样转来转去的好麻烦.

有没有机智点的方案?

机制版本

还是有两个栈.

push操作也一样.

但是pop操作呢?首先也全部将main的元素转移至helper.然后出栈,出栈之后保留helper的元素.

为什么可以保留呢?

因为此时helper中的元素就是队列的FIFO顺序,我们只要按照顺序出栈,就等于出队.

只要在此期间的push操作的元素,全部保存至main,且不向helper添加.

当helper为空时,将main中的元素全部转移过来.

这样操作就可以满足题目中的push()和pop()时间复杂度都为O(1)的要求了.

好了不BB.上代码!

实现代码

暴躁版本

代码语言:javascript
复制
import java.util.Stack;

public class MyQueue {

  //新建两个栈
  private Stack<Integer> main = new Stack<>();
  private Stack<Integer> helper = new Stack<>();

  public MyQueue() {
    // do intialization if necessary
  }

  /*
   * @param element: An integer
   * @return: nothing
   */
  public void push(int element) {
    // write your code here
    //入队直接入main栈
    main.push(element);
  }

  /*
   * @return: An integer
   */
  public int pop() {
    // write your code here
    //将main的元素全部转移到helper
    while (!main.empty()) {
      helper.push(main.pop());
    }
    //获取结果,调用栈的pop()
    int result = helper.pop();
    //将数据恢复至main,保持次序
    while (!helper.empty()) {
      main.push(helper.pop());
    }
    //返回结果
    return result;
  }

  /*
   * 和pop()一样的原理,只是调用栈的peek(),不弹出元素
   * @return: An integer
   */
  public int top() {
    // write your code here
    while (!main.empty()) {
      helper.push(main.pop());
    }
    int result = helper.peek();
    while (!helper.empty()) {
      main.push(helper.pop());
    }
    return result;
  }
}

机制版本

代码语言:javascript
复制
import java.util.Stack;

public class MyQueue {

  //初始化两个栈
  private Stack<Integer> main = new Stack<>();
  private Stack<Integer> helper = new Stack<>();

  public MyQueue() {
    // do intialization if necessary
  }

  /*
   * @param element: An integer
   * @return: nothing
   */
  public void push(int element) {
    // write your code here
    //入队直接入main栈
    main.push(element);
  }

  /*
   * @return: An integer
   */
  public int pop() {
    // write your code here
    //如果helper为空,则将main的元素全部转移至helper
    if (helper.empty()) {
      while (!main.empty()) {
        helper.push(main.pop());
      }
    }
    //不为空或者转移之后,直接弹出helper的栈顶元素,用pop()
    return helper.pop();
  }

  /*
   * @return: An integer
   */
  public int top() {
    // write your code here
    //如果helper为空,则将main的元素全部转移至helper
    if (helper.empty()) {
      while (!main.empty()) {
        helper.push(main.pop());
      }
    }
    //不为空或者转移之后,直接获取helper的栈顶元素,用peek()
    return helper.peek();
  }
}

完。

ChangeLog

2019-01-02 完成

以上皆为个人所思所得,如有错误欢迎评论区指正。

欢迎转载,烦请署名并保留原文链接。

联系邮箱:huyanshi2580@gmail.com


本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 来源
  • 描述
  • 样例
  • 挑战
  • 解题思路
    • 暴躁版本
      • 机制版本
      • 实现代码
        • 暴躁版本
          • 机制版本
            • ChangeLog
        领券
        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档