用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 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
解题思路
挺有意思的一道题，说这个题有意思不是因为这个题的思路难，而是写了半天，发现忽略了好多小细节。因为队列是先进先出，而栈是先进后出，如果要用栈来实现队列，很容易就想到了用两个栈来回倒，入队就是向栈里压入元素，出队就是将整个栈压入另外一个栈，将栈底元素变成栈顶元素，再出栈。
实现如下：
class CQueue {
Stack stackA;
Stack stackB;
boolean deleteHead;
boolean appendTail;
public CQueue() {
stackA = new Stack();
stackB = new Stack();
appendTail = false;
deleteHead = false;
}
public void appendTail(int value) {
if(deleteHead){
switchStack(stackA,stackB);
}
if(!stackB.empty())
stackB.push(value);
else
stackA.push(value);
appendTail = true;
deleteHead = false;
}
public int deleteHead() {
if(appendTail){
switchStack(stackA,stackB);
}
appendTail = false;
deleteHead = true;
if(stackA.empty() && !stackB.empty())
return (Integer)stackB.pop();
if(stackB.empty() && !stackA.empty())
return (Integer)stackA.pop();
return -1;
}
private void switchStack(Stack a, Stack b){
if(!a.empty()){
while(!a.empty()){
Integer value = (Integer) a.pop();
b.push(value);
}
} else if(!b.empty()){
while(!b.empty()){
Integer value = (Integer) b.pop();
a.push(value);
}
}
}
}
提交没问题，但是感觉写的很繁琐，是因为没有想清楚几个问题就动手了。
- Stack A 和Stack B 可以为固定的栈，即A永远用于进队，B用于出队而不是两个栈来回颠倒，所以appendTail 和 deleteHead 完全用不上。
- Stack 直接使用了java 类包 java.util.Stack， 可以显式给定数据类型，不需要后面再casting
- 提交后发现执行时间较慢，原因是使用的Stack是基于Vector的，有些人直接利用了LinkedList，时间效率一下子就提高了。
- 最后理解了一下Stack.pop() 和 peek()的区别，一个是栈顶元素出栈，后者是保留。
改后的代码为
class CQueue {
Stack<Integer> in;
Stack<Integer> out;
public CQueue() {
in = new Stack<>();
out = new Stack<>();
}
public void appendTail(int value) {
if(!out.empty())
switchStack(out,in);
in.push(value);
}
public int deleteHead() {
if(!in.empty())
switchStack(in,out);
if(!out.empty())
return out.pop();
return -1;
}
private void switchStack(Stack a, Stack b){
while(!a.empty()){
Integer value = (Integer) a.pop();
b.push(value);
}
}
}
其中switchStack 可以继续化简为
b.push(a.pop());
