由两个栈组成的队列

【题目】

​ 编写一个类，用两个栈实现队列，支持队列的基本操作（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();    }}