用队列实现栈

使用队列实现栈的下列操作：

• push（x） - 元素x入栈
• pop（） - 移除栈顶元素
• top（） - 获取栈顶元素
• empty（） - 返回栈是否为空

注意：

• 你只能使用队列的基本操作-也就是 push to back，peek/pop from front，size，状语从句： is empty 这些操作的英文合法的。
• 你所使用的语言也许不支持队列。你可以使用list或者deque（双端队列）来模拟一个队列，只要是标准的队列操作即可。
• 你可以假设所有操作都是有效的（例如，对一个空的栈不会调用pop或者顶操作）。

知识点

Stack

继承Vector类，后进先出的值的排列，Stack类是同步的，效率不高。官方一般建议使用ArrayDeque代替Stack

常用方法：

• empty：判断stack是否为空
• peek：返回栈顶端的元素
• pop：弹出栈顶的元素，出栈操作只是删除栈顶元素，并不返回该元素，内部执行了peek()方法
• push：将元素压入栈
• size：返回栈中的元素个数
• search：返回最靠近顶端的目标元素到顶端的距离

Queue

java.util.Queue接口，用以支持队列的常见操作，该接口扩展了java.util.Collection接口。
public interface Queue extends Collection { }

除了基本的 Collection 操作外，队列还提供其他的插入、提取和检查操作。每个方法都存在两种形式：

1. 抛出异常（操作失败时）类型: 一般为Collection方法 :
   • add(e)：插入，将指定的元素插入队列，成功返回true，如果当前无可用空间，则抛出IllegalStateException
   • remove()：移出，获取并移除队列的头
   • element()：检查，获取但不移除队列的头
2. 返回特殊值（null 或 false，取决于操作）类型:
   • offer(e)：插入，将指定的元素插入此队列，如果当前无可用空间，则返回 null
   • poll()：移出，获取并移除队列的头，如果此队列为空，则返回null
   • peek()：检查，获取但不移除队列的头，如果此队列为空，则返回null

注意：Queue尽量避免使用抛出异常的add()、remove()、element()方法，而是要使用返回特殊值的offer()、poll()、peek()方法，
它们的优点是通过返回值可以判断成功与否

Queue 实现通常不允许插入 null 元素，尽管某些实现（如 LinkedList）并不禁止插入null。
即使在允许null的实现中，也不应该将null插入到Queue中，因为null也用作poll方法的一个特殊返回值，表明队列不包含元素。

Deque

public interface Deque extends Queue { ... }
一个线性 collection，支持在两端插入和移除元素。
Deque(double ended queue —双端队列)，通常读为“deck”。

Deque既支持有容量限制的双端队列，也支持没有固定大小限制的双端队列。
Deque是Queue的子接口。

Deque有两个比较重要的类：ArrayDeque和LinkedList
使用栈时: 用ArrayDeque的push和pop方法；
使用队列时: 使用ArrayDeque的add和remove方法。

接口定义在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。因为此接口继承了队列接口Queue，
所以其每种方法也存在两种形式：
一种形式在操作失败时抛出异常，
对头：
插入：addFirst(e)
移出：removeFirst()
检查：getFrist()
队尾：
插入：addLast(e)
移出：removeLast()
检查：getLast()

另一种形式返回一个特殊值（null 或 false，具体取决于操作）。
对头：
插入：offerFirst(e)
移出：pollFirst()
检查：peekFrist()
队尾：
插入：offerLast(e)
移出：pollLast()
检查：peekLast()

删除指定元素：
boolean removeFirstOccurrence(e); 删除队列中第一个出现的
boolean removeLastOccurrence(e); 删除队列中最后一个出现的e, 如果不存在或者空或其它返回false，成功删除（即改变了队列）则返回true

Deque迭代器:
正向迭代器: dq.iterator
反向迭代器：Iterator descendingIterator(); // 得到Iterator类型的反向迭代器

1. 在将双端队列用作队列时，将得到 FIFO（先进先出）行为。

   将元素添加到双端队列的末尾，从双端队列的开头移除元素。从Queue接口继承的方法完全等效于Deque方法：
   Queue方法 / Dequeue方法
   插入：
   add(e) / addLast(e) – 插入元素，抛异常
   offer(e) / offerLast(e) – 插入元素，如果当前无可用空间，返回null
   移出：
   remove() / removeFirst() – 获取并移除队列头
   poll() / pollFirst() – 获取并移除队列头，如果此队列为空，则返回null
   检查：
   element() / getFirst() – 获取但不移除队列头
   peek() / peekFirst() – 获取但不移除队列头，如果此队列为空，则返回null

2. 用作 LIFO（后进先出）堆栈。应优先使用此接口而不是Stack类。

   在将双端队列用作堆栈时，元素被推入双端队列的开头并从双端队列开头弹出。堆栈方法完全等效于Deque方法：
   堆栈方法 / Dequeue方法
   push(e) / addFirst(e) — 插入元素
   pop() / removeFirst() — 获取并移除队列头
   peek() / peekFirst() — 获取但不移除队列头

ArrayDeque

数组实现的Deque,可以指定其capacity，但不过由于双端队列本身数据结构的限制，要求只能在初始化的时候指定capacity，没有像ArrayList那样随时都可以调整的ensureCapacity方法，
构造器中指定其初始的capacity：ArrayDeque(int numElements); // 初始元素个数，默认长度是16
ArrayDeque的使用方法就是上面的Deque的使用方法，基本没有对Deque拓展什么方法；

ArrayDeque是Deque 接口的一种具体实现，是依赖于可变数组来实现的。ArrayDeque 没有容量限制，可根据需求自动进行扩容。ArrayDeque 可以作为栈来使用，效率要高于Stack；ArrayDeque 也可以作为队列来使用，效率相较于基于双向链表的LinkedList也要更好一些

代码

使用ArrayDeque实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class MyStack {
    private ArrayDeque<Integer> arrayDeque;
    //Initialize your data structure here.
    public MyStack() {
        this.arrayDeque = new ArrayDeque<>();
    }
    //Push element x onto stack.
    public void push(int x) {
        arrayDeque.offerFirst(x);
    }
    //Removes the element on top of the stack and returns that element.
    public int pop() {
        return arrayDeque.pollFirst();
    }
    //Get the top element.
    public int top() {
        return arrayDeque.peekFirst();
    }
    //Returns whether the stack is empty.
    public boolean empty() {
        return arrayDeque.peekFirst() == null;
    }
}