java基础教程栏目介绍如何用两个栈实现一个队列。
队列和栈是计算机中两个非常重要的数据结构，经过前面的学习（《队列》、《栈》）我们知道了它们各自的特点，队列是先进先出（fifo）的，而栈是先进后出（filo）的，那如何用栈来实现队列呢？这可是一道经典的面试题，所以本文我们就来实现一下。
在正式开始之前，我们先来回顾一下栈和队列的常用方法。
栈（stack）的常用方法包含以下这些：
push()：入栈方法，向栈顶添加元素；pop()：出栈方法，将栈顶的元素移除并返回元素；peek()：查询栈顶元素，并不会移除元素。
队列（queue）的常用方法包含以下这些：
offer()：入队方法，向队尾添加元素；poll()：出队方法，从队头移除并返回元素；peek()：查询队头元素，并不会移除元素。有了这些前置知识，接下来我们来看今天的题目。
题目描述用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendtail 和 deletehead，分别完成在队列尾部插入整数和在队列头部删除整数的功能，若队列中没有元素，deletehead 操作返回 -1。
示例 1：
输入：
[cqueue,appendtail,deletehead,deletehead]
[[],[3],[],[]]
输出：[null,null,3,-1]
示例 2：
输入：
[cqueue,deletehead,appendtail,appendtail,deletehead,deletehead]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]
提示：
1 <= values <= 10000
最多会对 appendtail、deletehead 进行 10000 次调用
leetcode：leetcode-cn.com/problems/yo…
解题思路这道题目的意思其实很好理解，就是要将先进后出的栈改为先进先出的队列，其实问题中也给出了一些提示，“用两个栈来实现一个队列”。这道题实现的核心思想就是「负负得正」，我们先用一个栈来存入元素（这时最先进入的元素在栈底），然后再将第一个栈中的元素移动到新栈中，此时最先进入的元素就在栈顶了，然后在用第二个栈出栈时，整个执行的顺序就变成了先进先出。
接下来，我们用图解的方式来实现一下整个流程。
步骤一先将元素入栈到第一个栈中，如下图所示：
步骤二将第一个栈中的元素都移动到第二个栈中，如下图所示：
步骤三所有元素从第二个栈中出栈，如下图所示：
小结从上述图片可以看出，元素添加顺序是 1、2、3，最终经过两个栈之后的出栈顺序也是 1、2、3，这样我们就通过两个栈实现了队列（先进先出）。
实现代码接下来我们就用代码来实现一下以上思路：
class cqueue { stack<integer> inputstack; // 入栈的容器（添加时操作) stack<integer> 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 个栈只负责入栈（暂存数据），第 2 个栈只负责出栈（最终的队列执行顺序）；每次栈 2 出栈时都要把所有的元素都出完之后，才能从栈 1 中追加（添加）新数据，当栈 2 的数据没有全部出栈完成时，不能将栈 1 的元素入栈到栈 2，这样会导致元素的执行顺序混乱。总结本文我们通过两个先进后出的栈，通过“负负得正”的思路实现了队列先进先出的特性，但需要特别注意的是当第 2 个栈也就是出栈容器，在非空（栈）时不能将第 1 个栈中的元素添加到第 2 个栈中，以免造成程序执行顺序混乱。
相关免费学习推荐：java基础教程
以上就是如何用两个栈实现一个队列？的详细内容。