用两个栈实现队列

题目解释

示例一：

输出"CQueue"： 创立队列（[此时队列[]]），所以没有数字出队列，输入null，
输出"appendTail"： 退出输出中的数3到队尾（此时队列[3]），所以没有数字出队列，输入null
输出"deleteHead"： 删除对头的数即把队伍中3删除（此时队列[]），所以数字3出队列，输入3
输出"deleteHead"： 删除对头的数但队伍为空，输入-1

题目常识

栈 先进后出
队列 先进先出
一个栈没方法实现先进先出，所以须要两个栈
栈A实现入队性能，栈B实现出队性能
栈A的元素1234执行出栈放到栈B变成4321（即绝对倒序入栈了），而后对栈B执行出栈操作，出栈程序1234，相当于正序出栈，比照一开始的入栈12234，就变成了先进先出

  • Deque接口 读作deck
public interface Deque<E> extends Queue<E>

Deque 双端队列

  1. Deque的实现类有LinkedList、ArrayDeque、LinkedBlockingDeque，其中LinkedList是最罕用的。

    Deque反对在两端插入和移除元素、查看元素

  2. LinkedList类

     1、能够索引、能够反复 2、有序：存储和取出的程序统一

  3. 一般队列（一端进另一端出）、双端队列（两端都能够进出）、堆栈的结构都能用以下办法：

    `Deque deque = new LinkedList()`

  • Queue 接口
    Queue接口应用办法
    Deque接口扩大(继承)了 Queue 接口。在将双端队列用作队列时，将失去 FIFO（先进先出）行为。将元素增加到双端队列的开端，从双端队列的结尾移除元素。从 Queue 接口继承的办法齐全等效于 Deque 办法，如下表所示：

    题目解读

  • 退出队尾元素：退出队尾 appendTail()函数，也就是只须要把元素val退出栈A做入栈操作即可

  • 删除队首元素：删除队首deleteHead()函数
    分状况探讨

    • 如果栈B不为空，那就阐明栈B外面曾经有元素做好了出栈（相等于出队列的操作）的筹备，那就能够间接对栈B执行出栈操作，就把队首元素删除了
    • 如果栈B为空，栈A不为空，就阐明还有元素没有进入倒序，那就须要把A元素全副放入B中，实现元素倒序，再执行出栈操作
    • 如果栈A和栈B都为空，那就阐明队列里没有元素，那就是返回-1
  1. 一开始栈A和栈B都为空，返回-1
  2. 而后执行入栈操作入元素5，而后又将元素2入栈
  3. 而后执行delete操作，发现栈B空，A不空，此时对A出栈B入栈（倒序操作）栈B就是25，而后再执行B出栈删除队首元素，返回元素5

  4. 而后继续执行delete操作，发现栈B不空，那间接对B出栈，返回元素2

    题解

    public CQueue()：创建对象，须要把两个栈申明为CQueue类的全局变量。
    public void appendTail(int value)：间接push到栈1
    public int deleteHead()：目前栈1就是所有元素，再pop到栈2，那么栈2再pop就是头元素。（如果栈2没有元素，能力pop到栈2，否则程序不对）

    答案