⚓题目链接

思路

题目要求使用栈数据结构实现队列数据结构的作用。

栈数据结构的特点：先入后出
队列数据结构的特点：先入先出

题目的重点就是如何让两个栈实现出队列的顺序性
例如下面这个操作顺序，入1，入2，入3，出1，出2，入5，出3

栈A→入1→入2→入3
此时栈A结构为 |1|2|3 ，1在底部，3在顶部，栈B为空栈

当操作为出的时候，不能直接从栈A栈顶弹出，但是我们可以把栈A元素弹出放入栈B，放入后的栈B的元素排列为 |3|2|1 ，注意栈的特点，先入栈的元素在下面，因此栈A第一次弹出3，栈B首先入栈3，最后依次入栈，栈顶为1

这里有个规律出现了，通过两栈之间的倒转，可以把逆序存储的元素变为正序，
那么我们就有了简单解决题目的思路。因为题目本身的要求是顺序输出，那么只要输出的元素都是经过一次栈转换就可以保证。

因此最简便的方法就是一个栈作为输入栈↓，另一个栈作为输出栈↑，输出栈↑中的元素都是经过一次栈转换的元素，因此可以保证次序为正序。添加元素的时候全部添加到输入栈↓，输出的时候使用输出栈↑，当输出栈↑为空时，将输入栈↓中的元素倒入输出栈↑

最后注意边界条件，当两个栈元素为空时，删除元素要进行异常处理。

具体实现

class CQueue {

    private Stack<Integer> stack_add = new Stack();
    private Stack<Integer> stack_del = new Stack();

    public CQueue() {

    }
    
    public void appendTail(int value) {
        stack_add.push(value);
    }
    
    public int deleteHead() {
        if (stack_del.size() > 0)
            return stack_del.pop();
        else {
            if (stack_add.size() == 0)
                return -1;
            while(stack_add.size() > 0) {
                stack_del.push(stack_add.pop());
            }
            return stack_del.pop(); 
        }
    }
}

Q.E.D.