剑指offer-07-用两个栈实现队列

题目：

用两个栈实现一个队列，队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead，分别完成在队列尾部插入结点和队列头部删除结点的功能。

栈和队列相信大家都用得很熟了。栈是一种FILO的数据结构，而队列则是一种FIFO的数据结构，这个题目要求使用两个FILO的数据结构来实现FIFO。

思路其实并不难，主要需要实现两个API，一个是入队，一个是出队。主要思路是用栈 A 保存倒序的数据，而栈 B 保存正序的数据。入队时将数据放入栈 A 中，出队时将栈 B 弹栈即可。那么问题就在于如何将倒序的数据转换成正序的数据，其实只需要将栈 A 中的数据不断弹栈并压入栈 B 即可。入队时将数据不断压入栈 A，此时栈 A 存储的是倒序，当碰到出队请求时，先检查栈 B 是否为空，不为空则直接输出栈 B 的栈顶。若为空则将栈 A 里面的数据不断弹栈，然后在压入栈 B，这个时候栈 B 里面的顺序就是正确的了，这个时候只需要将栈 B 的栈顶输出即可，如下图所示。

有了思路之后代码实现就比较简单了。

import java.util.Stack;

public class Queue<T>{
    Stack<T> a;
    Stack<T> b;
    public Queue(){
        a = new Stack<>();
        b = new Stack<>();
    }
    
    // 入队操作
    public void appendTail(T t){
        a.push(t);
    }
    
    // 出队操作
    public T deleteHead(){
        if(b.empty()) {
            // 栈 B 为空，将 A 中的数据都放入 B中
            while(!a.empty()){
                b.push(a.pop());           
            }
        }
        if(b.empty()) {
            // 这个时候如果 B 仍为空，说明队列里没有任何数据，此时出队是错误操作
            throw new IllegalStateException("队列无数据");
        }
        // 返回 B 的栈顶数据
        return b.pop();
    }
}

这道题其实可以拓展延伸，比如如何用两个队列实现栈，思路都差不多，有兴趣可以自己去实现一下。

剑指offer-07-用两个栈实现队列

打赏点饭钱~