¶剑指 Offer 09. 用两个栈实现队列
Difficulty: 用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 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 次调用
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 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 次调用
¶Solution
Language: java
class CQueue {
private Deque <Integer> A,B;
public CQueue() {
A = new ArrayDeque();
B = new ArrayDeque();
}
public void appendTail(int value) {
A.addLast(value);
}
public int deleteHead() {
if(!B.isEmpty()) return B.removeLast();
if(A.isEmpty()) return -1;
while(!A.isEmpty())
B.addLast(A.removeLast());
return B.removeLast();
}
}¶总结
当我使用以上代码提交时，时空效率都比较好，官方文档提示说当需要使用Stack时，可以使用Deque<Integer> stack = new ArrayDeque<>();来代替栈， 原因的话是Stack继承了Vector接口，而Vector底层是一个Object[]数组，那么就要考虑空间扩容和移位的问题了。
Queue是一个接口，通常使用LinkedList实现，Queue 实现通常不允许插入 null 元素，尽管某些实现（如LinkedList）并不禁止插入 null。即使在允许 null 的实现中，也不应该将 null 插入到 Queue 中，因为 null 也用作 poll 方法的一个特殊返回值，表明队列不包含元素。建议使用offer(e)和poll()插入和删除元素
