关于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办法须要的工夫和内存
思维二：