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

来源

lintcode-用栈实现队列

描述

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

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

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

样例

比如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.

举例:

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.上代码!

实现代码

暴躁版本

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;
  }
}

机制版本

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

更多学习笔记见个人博客——>呼延十