由两个栈组成的队列

【题目】

​ 编写一个类，用两个栈实现队列，支持队列的基本操作（add、poll、peek）。

【思路】

​ 前景知识：栈，先进后出；队列，先进先出

​ 两个栈实现队列，用两个栈就是为了让栈中的数据反转一次，数据如a栈，把a栈的数据都pop出来push到b栈，这样a栈栈底的东西就会到b栈的栈顶了，有两个前提：

• a栈往b栈压数据时，必须把a栈中数据全部压入b栈
• 只有b栈为空，才能往b栈压入数据

【代码】

package keafmd.accumulate.codeinterviewguide.twostacksformaqueue;

import java.util.Stack;

/**
 * Keafmd
 *
 * @ClassName: MyStack1
 * @Description: 两个栈实现的队列 add、poll、peek
 * @author: 牛哄哄的柯南
 * @date: 2022-06-21 17:38
 */
public class TwoStacksQueue {
    Stack<Integer> stackA;
    Stack<Integer> stackB;

    public TwoStacksQueue(){
        stackA = new Stack<>();
        stackB = new Stack<>();
    }

    //转移 a栈的数据全部倒入b栈
    public void transfer(){
        if(stackB.isEmpty()){
            while(!stackA.isEmpty()){
                stackB.push(stackA.pop());
            }
        }
    }

    public void add(Integer val){
        stackA.push(val);
        transfer();
    }

    public Integer poll(){
        if(stackA.isEmpty()&&stackB.isEmpty()){
            throw new RuntimeException("Queue is empty!");
        }
        transfer();
        return stackB.pop();
    }

    public Integer peek(){
        if(stackA.isEmpty()&&stackB.isEmpty()){
            throw new RuntimeException("Queue is empty!");
        }
        transfer();
        return stackB.peek();
    }

}