[Java知识库]详解java用队列实现栈，原理＋代码

栈的特点：先进后出
队列的特点：先进先出
显然，单个队列我们是无法实现栈的操作的，我们这里采用两个队列来实现。

1.入栈、出栈的原理

比如我们现在有一个栈和两个队列，两队列用于模拟实现栈，现有数据12，23，34

我们现在入栈12，23，34，先将数据按顺序放入queue1里面

那我们现在要栈里面出一个34怎么办？因为队列里面必须是队头先出，那我们就把queue1里面的size-1（也就是2）个元素全部放入queue2里面，剩下一个元素就是我们栈中要出的元素

这时34出栈了，我们再要出23怎么办？

同样的道理，把queue2中size-1（也就是1）个元素出到queue1中，剩下最后一个就是要出的

总结如下：
1.入栈的时候，入到不为空的队列（我们这里刚开始两个队列都为空时默认是queue1）
2.出栈的时候，找到不为空的队列，出size-1个元素到另一个队列，剩下的这个元素就是出栈的元素

2.代码实现：

import java.util.LinkedList;
import java.util.Queue;
public class MyStack {
    //用队列实现栈
    private Queue<Integer> queue1;
    private Queue<Integer> queue2;

    public MyStack(){
        queue1=new LinkedList<>();
        queue2=new LinkedList<>();
    }

    public void push(int x){//入栈
        if (!queue1.isEmpty()){
            queue1.offer(x);
        }else if(!queue2.isEmpty()){
            queue2.offer(x);
        }else{//两个都为空，我们默认放到queue1里面
            queue1.offer(x);
        }
    }

    public int pop(){//出栈
        if(empty()){//两队列全为空的情况——也就是栈里没有元素了
            return -1;
        }
        if (!queue1.isEmpty()){
            int size=queue1.size();//这里不能直接把queue1.size()放到for循环里面
            //因为你for循环里面每次都要出一个元素，size会越来越小
            //比如原先size=4，里面4个元素，i=0
            //出一个元素，size=3，里面3个元素,i=1
            //出一个元素，size=2，里面2个元素,i=2
            //这时显然我们需要的循环还没有结束，但是如果直接把queue1.size()放到for循环里面它已经结束了
            for(int i=0;i<size-1;i++){
                    //把queue1里面的元素出到queue2里面
                    //一共出size-1个——queue1最后一个也就是我们要pop的元素
                    int val=queue1.poll();
                    queue2.offer(val);
                }
                return queue1.poll();
            }
        if (!queue2.isEmpty()){
            int size=queue2.size();
            for(int i=0;i<size-1;i++){
                    //把queue2里面的元素出到queue1里面
                    //一共出size-1个——queue2最后一个也就是我们要pop的元素
                    int val=queue2.poll();
                    queue1.offer(val);
                }
                return queue2.poll();
            }
        return -1;//这里是为了编译不报错，因为上面都是用的if，这句代码实际用不到，仅仅是为了编译通过

    }

    public int top(){//得到队头元素
        if(empty()){
            return -1;
        }

        if(!queue1.isEmpty()){
            int val=0;
            int size=queue1.size();
            for (int i=0;i<size;i++){
                val=queue1.poll();
                queue2.offer(val);
            }
            return val;
        }

        if ((!queue2.isEmpty())){
            int val=0;
            int size=queue2.size();
            for(int i=0;i<size;i++){
                val=queue2.poll();
                queue1.offer(val);
            }
            return val;
        }
        return -1;
    }

    public boolean empty(){//判断栈是否为空
        return queue1.isEmpty()&&queue2.isEmpty();
    }

    public static void main(String[] args) {
        MyStack myStack=new MyStack();
        //入栈
        myStack.push(1);
        myStack.push(2);
        myStack.push(3);
        myStack.push(4);
        System.out.println(myStack.top());//打印栈顶元素4

        //出栈
        myStack.pop();//删除栈顶元素4
        System.out.println(myStack.top());//打印栈顶元素3
    }
}

运行结果如下：