Java双向队列Deque实现栈与队列

Java中实际上提供了java.util.Stack来实现栈结构,但官方目前已不推荐使用,而是使用java.util.Deque双端队列来实现队列与栈的各种需求

ava.util.Deque的实现子类有java.util.linkedList和java.util.ArrayDeque.顾名思义前者是基于链表,后者基于数组实现的双端队列.

Deque总体介绍
要讲栈和队列，首先要讲Deque接口。Deque的含义是“double ended queue”，即双端队列，它既可以当作栈使用，也可以当作队列使用。下表列出了Deque与Stack相对应的接口：
下表列出了Deque与Queue相对应的接口：

上面两个表共定义了Deque的12个接口。添加，删除，取值都有两套接口，它们功能相同，区别是对失败情况的处理不同。一套接口遇到失败就会抛出异常，另一套遇到失败会返回特殊值（false或null）。除非某种实现对容量有限制，大多数情况下，添加操作是不会失败的。虽然Deque的接口有12个之多，但无非就是对容器的两端进行操作，或添加，或删除，或查看。明白了这一点讲解起来就会非常简单。
ArrayDeque和linkedList是Deque的实现子类，他们都能使用Deque的这12个方法，包括isEmpty()判断是否为空方法

ArrayDeque
当需要使用栈和队列是官方推荐的是ArrayDeque（但我刷题的时候感觉linkedList也很常用，甚至可能用的更多一点）

从名字可以看出ArrayDeque底层通过数组实现，为了满足可以同时在数组两端插入或删除元素的需求，该数组还必须是循环的，即循环数组（circular array），也就是说数组的任何一点都可能被看作起点或者终点。ArrayDeque是非线程安全的（not thread-safe），当多个线程同时使用的时候，需要程序员手动同步；另外，该容器不允许放入null元素。

以下linkedList实现栈和队列的等价方法与ArrayDeque相同

linkedList
linkedList实现了Deque接口,因此其具备双端队列的特性,由于其是链表结构,，双向链表，因此不像ArrayDeque要考虑越界问题,容量问题,那么对应操作就很简单了（另外当需要使用栈和队列是官方推荐的是ArrayDeque）

linkedList作为LIFO（后进先出）的栈时，下表的方法等价：

栈方法        等效方法
push(e)      addFirst(e)
pop()        removeFirst()
peek()       peekFirst()

注：同时linkedList本身也有push(e)，pop()，peek() 方法，功能一致

	Deque stack = new linkedList();
	这种情况下别忘了标明泛型

linkedList作为FIFO(先进先出)的队列时，表的方法等价

队列方法       等效方法
add(e)        addLast(e)
remove()      removeFirst()
element()     getFirst()

注：同时linkedList本身也有add(e)，remove()方法，功能一致