用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 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）
链接：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
分析我们先来分析下栈和队列这两种数据结构的特点：
数据结构
常用方法
特点
栈
- 入栈 - push
- 出栈 - pop
- 查看栈顶元素，不会删除 - peek
先进后出
队列
- 入队 - offer
- 出队 - poll
- 查看队列头元素，不会删除 - peek
先进先出
假设我们有1，2，3三个元素，按照顺序进行添加，我们来看看栈和队列获取元素时的顺序：
栈和队列
可以得到：
- 栈 - 先进后出，出栈顺序为3，2，1
- 队列 - 先进先出，出队顺序为1，2，3
可以看出来出栈顺序是出队顺序的倒序，由栈先进后出的特点，其实可以实现元素的倒序输出，两次倒序其实就可以实现顺序不变：
- 入栈1，2，3 -> 出栈3，2，1
- 入栈3，2，1 -> 出栈1，2，3
两个栈组成队列
那么什么时候s0出栈，s1入栈呢？
当s1栈内没有元素，还需要删除头节点时，执行s0出栈，s1入栈
因为如果s1栈内还有元素，这个时候执行s0出栈，s1入栈，那么就会覆盖一些s1已有的元素，不满足队列先进先出的特点
解题步骤：
- 定义两个栈s0，s1，其中s0栈负责添加元素，s1栈负责删除元素
- 尾部添加元素，直接入栈s0
- 头部删除元素
先判断s1栈是否还有元素，如果有则直接将s1栈顶元素出栈
如果s1栈没有元素，则判断s0栈是否还有元素
如果s0栈也没有元素，则说明栈内没有元素，直接返回-1
如果s0栈内有元素，则把s0元素全部出栈，入栈s1，然后将s1栈顶元素出栈
代码
class CQueue { // 声明两个栈，s0负责添加，s1负责删除 private Stack<Integer> s0; private Stack<Integer> s1; public CQueue() { // 初始化栈 s0 = new Stack<>(); s1 = new Stack<>(); } public void appendTail(int value) { // 尾部添加元素，直接入栈s0 s0.push(value); } public int deleteHead() { // 头部删除元素，先判断s1是否有元素 if (s1.size() == 0) { // 若s1栈内没有元素，则判断s0是否有元素 if (s0.size() == 0) { // 如果s0也没有元素，则说明两个栈内都没有元素，直接返回-1 return -1; } // s1没有元素，s0有元素，则把s0元素全部出栈，入栈到s1 while (s0.size() != 0) { s1.push(s0.pop()); } } // s1有元素，直接出栈 return s1.pop(); } } /** * Your CQueue object will be instantiated and called as such: * CQueue obj = new CQueue(); * obj.appendTail(value); * int param_2 = obj.deleteHead(); */复杂度：
,
- 空间复杂度：栈内最多存在的元素为N，所以空间复杂度为O(N)
- 时间复杂度：appendTail的时间复杂度为O(1)；deleteHead方法内，第一次调用会把s0栈内所有元素出栈，然后入栈到s1，元素最多为N，时间复杂度为O(N)
