今天刷leetcode印象比较深刻的题目：用两个栈实现一个队列
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 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]
一、题目解读
直接看例子——> 输入： ["CQueue","appendTail","deleteHead","deleteHead"] 这里是要执行的方法，从左到右执行
[[],[3],[],[]]对应上面的方法，是上面方法的参数。CQueue（创建）和deleteHead（删除）方法不需要指定数字，故参数为空，只有appendTail（添加）方法才需要指定数字
1."CQueue"创建队列，返回值为null
2."appendTail"将3压入队列，返回值为null
3."deleteHead"将队列头部的元素删除，也就是消息队列中先进来的元素，所以是deleteHead，返回该元素的数值，所以为3
4."deleteHead"继续删除队列头部的元素，但是没有元素了，所以返回-1
所以就有了下面的输出 输出：[null,null,3,-1]
示例 2： 输入： ["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
1.创建队列，返回值为null
2.删除队列头部的元素，但是没有元素，所以返回-1
3.把5压入队列，返回null
4.把2压入队列，返回null
5.删除队列头部的一个元素，也就是消息队列中先进来的元素，所以是deleteHead，就是最先进来的5，返回值为5，
6.删除队列头部的一个元素，就是后进来的2，返回值为2，
所以就有了下面的输出
输出：[null,-1,null,null,5,2]
有没有发现先进来的数字，首先显示出来了，但是题目中说要使用栈，栈是先进后出的，使用栈来实现先进先出，在这里使用两个栈就好了，从一个进来再到另一个栈，这样顺序就是
先进先出了。题目的主旨写在第一句，就是，使用两个栈实现一个队列。
二、解决思路
——双栈法
维护两个栈，第一个栈支持插入操作，第二个栈支持删除操作。
根据栈先进后出的特性，我们每次往第一个栈里插入元素后，第一个栈的底部元素是最后插入的元素，第一个栈的顶部元素是下一个待删除的元素。为了维护队列先进先出的特性，我
们引入第二个栈，用第二个栈维护待删除的元素，在执行删除操作的时候我们首先看下第二个栈是否为空。如果为空，我们将第一个栈里的元素一个个弹出插入到第二个栈里，这样第
二个栈里元素的顺序就是待删除的元素的顺序，要执行删除操作的时候我们直接弹出第二个栈的元素返回即可。
成员变量：维护两个栈 stack1 和 stack2，其中 stack1 支持插入操作，stack2 支持删除操作。
构造方法：初始化 stack1 和 stack2 为空。
插入元素：插入元素对应方法 appendTail，stack1 直接插入元素。
删除元素：删除元素对应方法 deleteHead
如果 stack2 为空，则将 stack1 里的所有元素弹出插入到 stack2 里
如果 stack2 仍为空，则返回 -1，否则从 stack2 弹出一个元素并返回
三、代码实现
class CQueue {
Deque<Integer> deque1;
Deque<Integer> deque2;
public CQueue() {
deque1 = new LinkedList<>();
deque2 = new LinkedList<>();
}
public void appendTail(int value) {
deque1.push(value);
}
public int deleteHead() {
if (deque2.isEmpty()) {
while (!deque1.isEmpty()) {
deque2.push(deque1.pop());
}
}
return deque2.isEmpty() ? -1 : deque2.pop();
}
}
四、拓展——QUEUE与DEQUE的区别
平常在写leetcode经常用LinkedList向上转型Deque作为栈或者队列使用，但是一直都不知道它与Queue的区别，于是就查阅官方文档：
从上图可以看出，Queue以及Deque都是继承于collection，Deque是Queue的子接口。
从Deque的解释中，我们可以得知：Deque是double ended queue，我将其理解成双端结束的队列，双端队列，可以在首尾插入或删除元素。而Queue的解释中，Queue就是简单的FIFO队列。
所以在概念上来说，Queue是FIFO的单端队列，Deque是双端队列。
而在使用上，又有什么差别呢？从上图我们可以得知，Queue有一个直接子类PriorityQueue，而Deque中直接子类有两个：LinkedList以及ArrayDeque。
PriorityQueue：无边界的，优先级的堆（官方文档截图）
查看源码后，明显看到PriorityQueue的底层数据结构是数组，而无边界的形容，那么指明了PriorityQueue是自带扩容机制的，具体请看PriorityQueue的grow方法。
而插入元素的时候是需要经过compareTo的处理，那么最常用就是一些范围极值的输出，类似于堆排序的用法。
LinkedList以及ArrayDeque：（官方文档截图）
从官方解释来看，ArrayDeque是无初始容量的双端队列，LinkedList则是双向链表。ArrayDeque作为队列时的效率比LinkedList要高，而在栈的使用场景下，无疑具有尾结点不需判空的LinkedList较高效。
其实ArrayDeque和LinkedList都可以作为栈以及队列使用，但是从执行效率来说，ArrayDeque作为队列以及LinkedList作为栈使用会是更好的选择
小结：
PriorityQueue可以作为堆使用，而且可以根据传入的Comparator实现大小的调整，会是一个很好的选择。
ArrayDeque通常作为栈或队列使用，但是栈的效率不如LinkedList高。
LinkedList通常作为栈或队列使用，但是队列的效率不如ArrayQueue高。
总结
在java中，Queue被定义成单端队列使用，Deque被定义成双端队列使用。
而由于双端队列的定义，Deque可以作为栈或者队列使用，而Queue只能作为队列或者依赖于子类的实现作为堆使用。