如何用两个栈实现一个队列？

Java基础教程栏目介绍如何用两个栈实现一个队列。

实现代码

接下来我们就用代码来实现一下以上思路：

class CQueue {
    Stack inputStack; // 入栈的容器（添加时操作)
    Stack outputStack; // 出栈和查询的栈容器

    public CQueue() {
        inputStack = new Stack();
        outputStack = new Stack();
    }    // 添加操作
    public void appendTail(int value) {
        inputStack.push(value);
    }    // 删除操作
    public int deleteHead() {        if (!outputStack.isEmpty()) {            // 出栈容器不为空
            return outputStack.pop();
        } else if (!inputStack.isEmpty()) {            // 入栈 stack 全部转移到出栈 stack
            while (!inputStack.isEmpty()) {
                outputStack.push(inputStack.pop());
            }
        }        return outputStack.isEmpty() ? -1 : outputStack.pop();
    }
}

我们在 LeetCode 中提交以上测试代码，执行结果如下：

注意事项

在整个实现过程中有两个小细节需要特别注意一下：

1. 第 1 个栈只负责入栈（暂存数据），第 2 个栈只负责出栈（最终的队列执行顺序）；
2. 每次栈 2 出栈时都要把所有的元素都出完之后，才能从栈 1 中追加（添加）新数据，当栈 2 的数据没有全部出栈完成时，不能将栈 1 的元素入栈到栈 2，这样会导致元素的执行顺序混乱。

总结

本文我们通过两个先进后出的栈，通过“负负得正”的思路实现了队列先进先出的特性，但需要特别注意的是当第 2 个栈也就是出栈容器，在非空（栈）时不能将第 1 个栈中的元素添加到第 2 个栈中，以免造成程序执行顺序混乱。

相关免费学习推荐：java基础教程

以上就是如何用两个栈实现一个队列？的详细内容，更多请关注其它相关文章！