力扣232：用栈实现队列【java语言实现】-Toy模板网

这篇具有很好参考价值的文章主要介绍了力扣232：用栈实现队列【java语言实现】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目链接：力扣232：用栈实现队列

力扣232：用栈实现队列【java语言实现】,算法题【java版】,leetcode,算法,java

根据题目要求：要用栈实现队列中的相关方法，收先要明确栈和队列的相关特性

栈：先进后出

队列：先进先出

先让数字1，2，3，4分别依次进入栈和队列中，观察一下：

力扣232：用栈实现队列【java语言实现】,算法题【java版】,leetcode,算法,java

接下来弹出一个元素：可以看到：队列中弹出的元素是1，栈中弹出的元素是4；不管我们怎么操作用一个栈实现队列的功能是不可能的【首先我们要意识到这个问题】，一个不行，那就用两个栈来实现这个功能，要想弹出元素1，需要依次把栈中的所有元素弹出，放到另一个栈中；如图所示：

力扣232：用栈实现队列【java语言实现】,算法题【java版】,leetcode,算法,java

此时，我们就会发现队列弹出元素1时，栈1也可以弹出元素1，实现了栈和队列的同步

我们先创建两个栈【我们采用力扣给我们提供的模板：在构造方法中创建两个栈】

要添加元素用栈stackIn；

要弹出元素用栈stackOut；

   //全局变量
     Stack<Integer> stackIn;
     Stack<Integer> stackOut;
     public MyQueue() {
        stackIn = new Stack<>(); // 负责进栈
        stackOut = new Stack<>(); // 负责出栈
    }

先补充一下java中Stack中常用的方法：

push(E item)：将元素入栈，即将元素放置在栈顶。

pop()：弹出并返回栈顶的元素。如果栈为空，则抛出EmptyStackException异常。

peek()：返回栈顶的元素，但不弹出它。如果栈为空，则抛出EmptyStackException异常。

empty()：测试栈是否为空。

接下来，只需要写一个函数【move()函数】【逻辑是从stackIn栈中依次弹出元素放进satckOut中】，很简单就是一个循环如下：

  //力扣中提供的int pop() 从队列的开头移除并返回元素
    public int pop() {
        //调用方法
        move();  
        //弹出元素     
        return stackOut.pop();
    }

    public void  move(){
        if(!stackOut.isEmpty()){return;}
        while(!stackIn.isEmpty()){
            stackOut.push(stackIn.pop());
        }  
    }

*重点是while循环上面的判断条件：为什么要添加这个判断条件？我们来考虑一下这种情况：

经过添加，删除元素以后，栈和队列中的元素情况如图所示：

力扣232：用栈实现队列【java语言实现】,算法题【java版】,leetcode,算法,java

此时，我们能直接执行while()循环的逻辑【栈不为空，把栈2中的元素添加到栈1中去】吗？

假设执行上述逻辑后，5进入到栈1；此时，我想弹出一个元素，队列中弹出的是2，而栈中弹出的元素是1，明显是错误的！错误原因就在于：stackOut栈还没有空，就又添加了一个新的元素；因此，要进行逻辑判断：当栈1不为空时，不能添加新元素，逻辑为：

if(!stackOut.isEmpty()){return;}

还有就是判空的逻辑：根据上述逻辑可知，当两个栈都为空时，我们才能说我们构造的这个队列为空。逻辑为：文章来源地址https://www.toymoban.com/news/detail-830241.html

    public boolean empty() {
        return  stackIn.isEmpty() &&  stackOut.isEmpty(); 
    }

完整代码：

class MyQueue {
    Stack<Integer> stackIn;
    Stack<Integer> stackOut;
    public MyQueue() {
        stackIn = new Stack<>();
        stackOut = new Stack<>();
    }
    
    public void push(int x) {
        stackIn.push(x);
    }
    
    public int pop() {
        move();       
        return stackOut.pop();
    }
    
    public int peek() {
       move();
        return stackOut.peek();      
    }
    
    public boolean empty() {
        return  stackIn.isEmpty() &&  stackOut.isEmpty(); 
    }
    public void  move(){
        if(!stackOut.isEmpty()){return;}
        while(!stackIn.isEmpty()){
            stackOut.push(stackIn.pop());
        }  
    }
}

到了这里，关于力扣232：用栈实现队列【java语言实现】的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！