《剑指offer》—— 5. 用两个栈实现队列（Java）

推荐

完整《剑指Offer》算法题解析系列请点击 👉 《剑指Offer》全解析 Java 版

题目描述

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

import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    public void push(int node) {
        
    }
    
    public int pop() {
    
    }
}

题目分析：

先了解几个方法

push(x) ——将 x 插到队尾
pop() ——将队首的元素弹出，并返回该元素
empty() ——返回队列是否为空

还要知道栈是 “先进后出”，队列是 "先进先出" 。

现在我们有两个栈 stack1 和 stack2，我们插入三个数啊 a,b,c ，假设插入的是 stack1，此时情况如图：

如果此时执行 push(x) 方法的话，我们直接将 x 插入栈 stack1 即可。

如果此时执行 pop() 方法话，怎么将 a 直接弹出来呢？
我没可以先将 stack1 中数依次拿出来放到 stack2 中，此时情况如图：

那么此时，就可以直接将 a 弹出了。

我们也就模拟成了队列。

理下思路：

执行 push(x) 时，直接将 x 插入到 stack1

执行pop时，判断一下 stack 是否为空，不为空，直接弹出 stack2 栈顶的数；
如果为空，则先将stack1中的数依次插入到 stack2 中，然后再弹出 stack2 栈顶的元素。

实现（有问题）：

import java.util.Stack;

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() {
        if(stack2.empty()){
            while(!stack1.empty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

这里更新一下，虽然上面这个实现可以过牛客网的AC。

但是 push() 有问题。

当我们执行过一次pop之后，数据全在stack2了。

这个时候，如果push，会直接push进stack1；

当我们下一次pop的时候，就会有问题了。

实现：

import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    public void push(int node) {
        if (stack1.empty()){
            while (!stack2.empty()){
                stack1.push(stack2.pop());
            }
        }
        stack1.push(node);
    }
    
    public int pop() {
    if (stack2.empty()){
        while (!stack1.empty()){
            stack2.push(stack1.pop());
        }
    }
       return  stack2.pop();
    }
}

看完之后，如果还有什么不懂的，可以在评论区留言，会及时回答更新。