推荐

完整《剑指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();
    }
}

 

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

这里是猿兄，为你分享程序员的世界。

非常感谢各位大佬们能看到这里，如果觉得文章还不错的话， 求点赞👍 求关注💗 求分享👬求评论📝 这些对猿兄来说真的 非常有用！！！

注： 如果猿兄这篇博客有任何错误和建议，欢迎大家留言，不胜感激！