关于java:09-用两个栈实现队列

09. 用两个栈实现队列

解释题目：

补充常识：

• Deque 接口 读作 deck
  

  public interface Deque<E> extends Queue<E>

  1、Deque 的实现类有 LinkedList、ArrayDeque、LinkedBlockingDeque，其中 LinkedList 是最罕用的。
  2、反对在两端插入和移除元素、查看元素
  3、 一般队列 （一端进另一端出）、 双端队列 （两端都能够进出）、 堆栈 的结构都能用以下办法：

  Deque deque = new LinkedList()

  用 Deque 接口代替 Queue 接口的办法：
  
  用 Deque 接口代替 Stack 类的办法：
  

  摘自 Java 双端队列 Deque 应用详解
  4、Deque 接口也有 push pop 办法。

• LinkedList 类
  1、能够索引、能够反复
  2、有序：存储和取出的程序统一
  List、List 特有办法、并发批改异样、ListIterator 接口、LinkedList

思路：

题目规定了用双栈，且给了 CQueue 的类来实现

class CQueue {public CQueue() { }
    
    public void appendTail(int value) { }
    
    public int deleteHead() {}
}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */

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

public CQueue()的 留神点：

创建对象，且对象是全局的，所以要在全局申明，再在构造函数中创立。

class CQueue {
    private Deque<Integer> sta1;
    private Deque<Integer> sta2;

    public CQueue() {sta1 = new LinkedList<>();
        sta2 = new LinkedList<>();}

public int deleteHead()的 重要思维 一：

如果栈 2 不空，那么栈 2 第一个元素就是头元素
如果栈 2 空，栈 1 空，那么返回 -1
如果栈 2 孔，栈 1 不空，那么遍历栈 1pop 到栈 2，栈 2 第一个元素就是头元素。

public int deleteHead()的 重要思维 二：

如果栈 2 空，栈 1 不空，那么遍历栈 1pop 到栈 2，栈 2 第一个元素就是头元素。如果栈 2 空，栈 1 空，那么返回 -1。栈 2 不空的状况间接 return removeLast(), 与第一种状况合并。

操作:

思维一：更具备逻辑性

用 Deque 和 addLast removeLast 办法须要的运行工夫短，内存小于用 Stack 和 push pop 办法须要的工夫和内存
思维二：