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

用两个栈实现队列

题目解释

示例一：

输出 ”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，否则程序不对）
   

   答案