用两个栈实现队列

题目描述:

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

思路：

第一种思路

队列的性质是先进先出，栈的性质是先进后出，那么自然而然就会想到，一个进栈，然后出栈后再塞入另一个栈，这样就实现了先进先出；
例如：我们将1，2，3，4，5一次压入栈中，那么里面就是这样的，右侧为出口
|0|1|2|3|4|
|-|-|-|-|-|
|1|2|3|4|5|
那么我们再依次弹出，弹出后压入另一个栈中
|0|1|2|3|4|
|-|-|-|-|-|
|5|4|3|2|1|
那么另一个栈就成了顺序存放，那么就形成了这么一个关系，第二个栈的作用就是将第一个栈的顺序倒过来，然后再依次出栈

代码实现

第一种思路

import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Quene quene = new Quene();
        quene.push(1);
        quene.push(2);
        quene.push(3);
        System.out.println(quene.pop());
        System.out.println(quene.pop());
        quene.push(4);
        System.out.println(quene.pop());
        quene.push(5);
        System.out.println(quene.pop());
        System.out.println(quene.pop());
    }
}
class Quene
{
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

    public void push(int node) {
        while (!stack2.empty())
        {
            stack1.push(stack2.pop());
        }
        stack1.push(node);
        stack2.clear();
        while (!stack1.empty())
        {
            stack2.push(stack1.pop());
        }
    }

    public int pop() {
        return stack2.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) {
        stack1.push(node);
    }
     
    public int pop() {
        if(stack1.empty()&&stack2.empty()){
            throw new RuntimeException("Queue is empty!");
        }
        if(stack2.empty()){
            while(!stack1.empty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}