用两个栈实现队列的POP和PUSH操作

测试步骤

push(1)

push(2)

push(3)

pop()

pop()

push(4)

push(5)

pop()

pop()

pop()

思路

前三次push()

image.png

两次pop()

我们可以使用以下方法把s1的内容移到s2，翻转一下，此时stack2.pop()的值就是队首

while(!stack1.empty()){
    stack2.push(stack1.pop();
}

image.png image.png

两次push()

把要push的值都往stack1里面放，此时你会发现，如果我们要pop队列，只需pop栈2就好了

image.png

三次pop()

第一次pop()掉stack2的内容，当stack2为空时，我们又回到最初的选择，把stack1的元素全部翻转到stack2，然后popStack2

image.png
image.png
image.png
image.png

Java代码

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() {
        //栈2非空
        if(!stack2.empty()){
            return stack2.pop();
        }
        //栈2为空
        if(stack1.size()==1){
            return stack1.pop();
        }
        else{
            while(!stack1.empty()){
                stack2.push(stack1.pop());
            }
            return stack2.pop();
        }
    }
}