算法题6.用两个栈实现队列

题目描述:

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

核心思想就是利用栈的性质，栈的数据是先进后出，而队列是先进先出。只要明白这两点，实现起来就不难，首先是本人的暴力破解，使用了两个stack对象，stack1用来存储数据，stack2用来辅助取数据：

import java.util.EmptyStackException;
import java.util.Stack;

/**
 * Created by HY
 * 2019/7/29 20:21
 * <p>
 * 用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
 */
public class Solution{

    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

    public void push(int node) {
        stack1.push(node);
    }

    public int pop() {

        //先将数据翻转并转移到statck2中
        while (!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }

        //栈为空时抛出异常
        if (stack2.isEmpty())
            throw  new EmptyStackException();

        //取出第一个数
        int result = stack2.pop();

        //还原
        while (!stack2.isEmpty()) {
            stack1.push(stack2.pop());
        }
        return result;
    }
 
}

完美通过，但是这种办法效率上肯定是有问题的，于是去评论区逛了逛，发现了一种优化方案，就是当push操作的时候再将stack2还原回去，否则直接从stack2中取顶部元素就可以了：

//push的时候再把stack2还原回stack1
public void push(int node) {
    //先还原
    while (!stack2.isEmpty()) {
        stack1.push(stack2.pop());
    }
    stack1.push(node);
}

public int pop() {
    //将数据翻转转移到stack2
    while (!stack1.isEmpty()) {
        stack2.push(stack1.pop());
    }

    if (stack2.isEmpty()) {
        throw new EmptyStackException();
    }

    //返回第一个数
    return stack2.pop();
}