教你如何用两个栈实现一个队列

一,实现思路

1,首先准备两个栈,栈A与栈B
2,栈A专门用来完成入队列操作,栈B专门用来出队列与取队首元素操作
3,每次入队列操作时,首先得判断B栈是否为空,不空则将B栈元素全都依次入A栈,最后继续入新元素(即将要入栈元素添加到栈A)
4,每次出队列与取队首元素操作时,将A栈中的元素依次入B栈,出队列即取出B栈中的元素,取队首元素即取B栈栈顶元素即可
注意:如果不够清楚思路,也可阅读代码,清晰的注释总会让你理解

二,实现代码

import java.util.Stack;

public class MyQueueByStack {
    //先创建两个栈
    private Stack<Integer> A = new Stack<>();  //用来入队列
    private Stack<Integer> B = new Stack<>();  //用来出队列
    public void push(int val){  //入队列
        // 如果栈B不为空，先将B中的元素倒腾到栈A
        while(!B.isEmpty()){
            int tmp = B.pop();
            A.push(tmp);
        }
        //接着入栈只需将元素放入栈A
        A.push(val);
    }
    public Integer pop(){  //出队列
        if(empty()){
            return null; //如果队列为空（即AB栈都为空）直接返回null
        }
        while(!A.isEmpty()){  //当A栈不为空，将A中的元素倒腾到B
            int tmp = A.pop();
            B.push(tmp);
        }
        return B.pop(); //直接返回B的出栈元素，即为出队列的元素
    }
    public Integer peek(){  //取队首元素
        if(empty()){
            return null; //如果队列为空（即AB栈都为空）直接返回null
        }
        while(!A.isEmpty()){  //当A栈不为空，将A中的元素倒腾到B
            int tmp = A.pop();
            B.push(tmp);
        }
        return B.peek(); //直接返回B的栈顶元素，即为出队列的栈顶元素
    }
    public boolean empty(){
        return A.isEmpty() && B.isEmpty();  //如果AB栈都为空则表示队列为空
    }

    public static void main(String[] args) {
        MyQueueByStack queue = new MyQueueByStack();
        queue.push(1);
        queue.push(2);
        queue.push(3);
        queue.push(4);
        System.out.println(queue.peek());
        System.out.println(queue.pop());
        System.out.println(queue.pop());
        System.out.println(queue.pop());
        System.out.println(queue.pop());
    }
}

测试结果: