Vector和stack
Vector：Vector的底层与ArrayList类似.都是以动态数组的方式进行对象的存储
Vector与ArrayList的区别在于Vector是线程同步操作安全的，并发安全保证
Vector很多对外的方法都用Synchronized关键字进行修饰，所以通过vector进行操作性能并不高
Vector是线程安全的，但是性能较差，不推荐使用。
在工作中，我们有可能将集合（ArrayList与LinkedList）转换为线程安全。就要用到Collections工具类
Java Coder为什么不建议使用Stack类来实现栈功能：
当需要用到栈这种数据结构时，在java中，有的人使用LinkedList来实现，还有的人使用Queue或者Deque来实现, Stack 这个类不被推荐使用。
在 Java 语言中，不推荐使用 Stack 类？
一个更加完整，一致的，后进先出的栈相关的操作，应该由 Deque 接口提供。并且，也推荐使用 Deque 这种数据结构（比如 **ArrayDeque**）来实现。
因此，如果你想使用栈这种数据结构，Java 官方推荐的写法是这样的（假设容器中的类型是 Integer）：Deque<Integer> stack= new ArrayDeque<>();
Java 中的 Stack 类到底怎么了？
Java 中的 Stack 类，最大的问题是，继承了 Vector 这个类。根据 Java 官方文档中的类关系，如下所示：
Vector 就是一个动态数组。Stack 这个类继承 Vector，最大的问题在于，继承使得子类继承了父类的所有公有方法。
而 Vector 作为动态数组，是有能力在数组中的任何位置添加或者删除元素的。因此，Stack 继承了 Vector，Stack 也有这样的能力, 对于栈来说，我们不希望，在任何位置添加或者删除元素，破坏了栈这种数据结构的封装！
封装的一大意义，就是向用户屏蔽用户不需要的操作。否则，用户可能会有意无意地调用这些操作，这将成为软件工程中重要的 bug 来源。
问题出在哪里？
Java 中的 Stack 实现，是被业界一直认为非常糟糕的实现。实际上，它犯了面向对象设计领域的一个基本错误：Stack 和 Vector 之间的关系，不应该是继承关系，而应该是组合关系（composition）。
在这个例子中，我们是否可能将栈当做一个动态数组使用？答案是不可能。所以，栈和动态数组之间的关系不应该是继承关系。
多用组合，少用继承
Java 官方不知道这个 Stack 类的实现不好吗？为什么不改？
Java 官方当然知道这个实现不好。但是，因为要保持兼容性（backward compatibility），对于已经正式发布的代码，Java 官方不能做接口设计层面的修改。否则，使用老版本 Java 的程序，将在新的 Java 环境下无法执行，这是 Java 官方不愿意看到的。
Java 官方可以做到的是，将这个类标志成“弃用”（deprecated），以让新版本的开发者不再允许使用这个类，但老版本的程序，还能继续执行。
但是，这么多年了，Java 官方也并没有将 Stack 标为“弃用”，只是在文档上注明“不建议使用”。
为什么使用接口？
下面，我们再来看一下 Java 官方推荐的写法：使用 Deque 接口：
Deque<Integer> stack= new ArrayDeque<>();
接口最大的意义之一，就是做了更高层次的抽象：只定义了一个类应该满足哪些方法，而对具体的实现方式不做限制。
比如，我们都知道，在 Java 语言中，Queue 就是一个接口。我们想实现一个队列，可以这么写：
在上述实现中，q1 和 q2 的底层具体实现不同，一个是 LinkedList，一个是 ArrayDeque。但是，从用户的角度看，q1 和 q2 是一致的：都是一个队列，只能执行队列规定的方法。
这样做，将“队列”这样一个概念，和底层数据结构的具体实现——LinkedList 或者 ArrayDeque 解耦了：
底层开发人员可以随意维护自己的 LinkedList 类或者 ArrayDeque 类，只要他们满足 Queue 接口规定的规范；
开发者可以选择合适的数据结构来定义 Queue；
而 Queue 的更上层使用者，无需知道 q1 或者 q2 的实现细节，从他们的角度看，只要能调用 Queue 的相关方法：peek, poll, offer 等等，来满足上层的业务需求，就好了。
而且这样做，完美解决了之前说的，继承关系把父类的所有方法都拿过来的问题。接口的设计相当于做了访问限制。LinkedList 中有很多方法，但是，当我们使用 LinkedList 实现 Queue 接口的时候，用户只能调用 Queue 中定义的方法。
从这个角度，我们也能看出 Stack 设计的另一个不合理之处：Stack 和 Queue 同样作为一种特殊的线性数据结构，都应该只是规定一系列操作的接口而已，具体的底层实现，由开发者再做选择。
但因为 Stack 做成了一个类，继承了 Vector，也就只能基于 Vector 这一种固定的数据结构了。
为了修正这个问题，Java 官方推出了 Deque 接口，作为实现栈的接口。
什么是 Deque 接口？
Deque 是双端队列的意思。所谓的双端队列，就是能在线性数据结构的两段，进行插入和删除操作。
大家可以想象，由于 Stack 的定义是在同一端进，同一端出。所以，如果 Deque 可以满足在两段进行插入和删除，自然也能在同一端进行插入和删除，也就是可以以此为基础，做成一个 stack。
很多同学应该能马上反应过来了。这里有问题！
因为我们根据 Java 官方推荐的方法声明的这个 stack，虽然变量名称是 stack，但它实际上是一个 deque。这就意味着，这个 stack，可以在两段做插入和删除操作！但是，真正的栈，只能在同一端做插入和删除操作！
这难道不是重蹈了 Stack 这个类的覆辙？毕竟，我们最开始分析，就说 Stack 这个类的一大问题，是继承了 Vector 这个类的若干我们不需要的方法，破坏了封装性，比如在任何一个位置插入一个元素。现在这个基于 Deque 接口的 stack，依然有我们不需要的方法啊！
没错！这就是 Java 的历史遗留问题了。这个问题至此已经无解了。因为 Stack 这个关键字被占据了。Java 官方不想推出一个叫做 RealStack 或者 CorrectStack 一类的接口名称。所以，按照 Java 官方的推荐所建立的这个 stack，依然不完美。
但至今为止，Java 暂时只是做到这个份儿上。
或许，Oracle 少打一些官司，多研究一下如何处理这些历史遗留问题，Java 能更好吧。
所以，在实际的工程应用上，有人也并不建议使用 Deque 做为 stack 的实现，而是自己再做一层封装。所以，在实际的工程应用上，有人也并不建议使用 Deque 做为 stack 的实现，而是自己再做一层封装。
虽然 Java 官方推荐使用 Deque 接口实现 stack，但是这样的 stack 也破坏了封装性，并不安全。怎么办？很简单，自己再封装一层，做一个只限制能从一段做插入删除的，真正的栈。
这个代码其实很简单，因为这本质是一个设计问题，而不是逻辑问题。有兴趣的同学可以看一下这篇文章：http://baddotrobot.com/blog/2013/01/10/stack-vs-deque/
当然了，在实际的算法面试中，可能面试官的关注点并不是这种设计问题，所以使用 Java 官方文档建议的方式来创建栈，并且和面试官讲清楚，我认为就足够了。
链表呢？
Java 官方推荐的创建栈的方式，使用了 Deque 接口。并且，在底层实现上，使用了 ArrayDeque，也就是基于动态数组的实现。为什么？
大家应该都知道，动态数组是可以进行扩容操作的。在触发扩容的时候，时间复杂度是 O(n) 的，但整体平均时间复杂度（Amortized Time）是 O(1)。
但是，基于链表的实现，不会牵扯到扩容问题，因此，每一次添加操作，从时间复杂度的角度，都是 O(1) 的。
虽然如此，可是实际上，当数据量达到一定程度的时候，链表的性能是远远低于动态数组的。
这是因为，对于链表来说，每添加一个元素，都需要重新创建一个 Node 类的对象，也就是都需要进行一次 new 的内存操作。而对内存的操作，是非常慢的。
举个例子，对于队列，假设我们实验使用 ArrayDeque（动态数组）和 LinkedList（链表）作为底层的数据结构，进行 1000 万次入队操作。并且测试他们的性能。代码如下：
在我的计算机上，结果是这样的：
也就是使用 LinkedList，会比使用 ArrayDeque 慢 5 倍以上。
因此，甚至有人建议：在实践中，尤其是面对大规模数据的时候，不应该使用链表！
Vector 呢？
大家可以看到，上面的讨论，我们已经完全扔掉 Java 中的 Vector 这个类了。
实际上，Vector 这个类不仅仅是简单的一个动态数组而已，而更进一步，保证了线程安全。
因为要保证线程安全，所以 Vector 实际上效率也并不高。
Java 官方的 Vector 文档中明确指出了：如果你的应用场景不需要线程安全的特性，那么对于动态数组，应该使用 ArrayList.
即使需要并发编程，自 Java 5 以后，也推荐使用 java.util.concurrent 包。
Stack & Queue概述
Java里有一个叫做Stack的类，却没有叫做Queue的类(它是个接口名字)。当需要使用栈时，Java已不推荐使用Stack，而是推荐使用更高效的ArrayDeque；既然Queue只是一个接口，当需要使用队列时也就首选ArrayDeque了(次选是LinkedList)。
面对大规模数据的时候，，链表的性能是远远低于动态数组的。对于链表来说，每添加一个元素，都需要重新创建一个 Node 类的对象，也就是都需要进行一次 new 的内存操作。而对内存的操作，是非常慢的。
Queue
Queue接口继承自Collection接口，除了最基本的Collection的方法之外，它还支持额外的insertion, extraction和inspection操作。这里有两组格式，共6个方法，一组是抛出异常的实现；另外一组是返回值的实现(没有则返回null)。
Deque
Deque是"double ended queue", 表示双向的队列，英文读作"deck". Deque 继承自 Queue接口，除了支持Queue的方法之外，还支持insert, remove和examine操作，由于Deque是双向的，所以可以对队列的头和尾都进行操作，它同时也支持两组格式，一组是抛出异常的实现；另外一组是返回值的实现(没有则返回null)。共12个方法如下:
当把Deque当做FIFO（先进先出）的queue来使用时，元素是从deque的尾部添加，从头部进行删除的； 所以deque的部分方法是和queue是等同的。具体如下:
Deque的含义是“double ended queue”，即双端队列，它既可以当作栈使用，也可以当作队列使用。下表列出了Deque与Queue相对应的接口:队列先进先出（FIFO）
下表列出了Deque与Stack对应的接口:作为栈后进先出
上面两个表共定义了Deque的12个接口。添加，删除，取值都有两套接口，它们功能相同，区别是对失败情况的处理不同。一套接口遇到失败就会抛出异常，另一套遇到失败会返回特殊值(false或null)。除非某种实现对容量有限制，大多数情况下，添加操作是不会失败的。虽然Deque的接口有12个之多，但无非就是对容器的两端进行操作，或添加，或删除，或查看。明白了这一点讲解起来就会非常简单。ArrayDeque和LinkedList是Deque的两个通用实现，由于官方更推荐使用AarryDeque用作栈和队列
从名字可以看出ArrayDeque底层通过数组实现，为了满足可以同时在数组两端插入或删除元素的需求，该数组还必须是循环的，即循环数组(circular array)，也就是说数组的任何一点都可能被看作起点或者终点。ArrayDeque是非线程安全的(not thread-safe)，当多个线程同时使用的时候，需要程序员手动同步；另外，该容器不允许放入null元素。
上图中我们看到，head指向首端第一个有效元素，tail指向尾端第一个可以插入元素的空位。因为是循环数组，所以head不一定总等于0，tail也不一定总是比head大。
方法剖析
addFirst()
addFirst(E e)的作用是在Deque的首端插入元素，也就是在head的前面插入元素，在空间足够且下标没有越界的情况下，只需要将elements[--head] = e即可。
实际需要考虑: 1.空间是否够用，以及2.下标是否越界的问题。上图中，如果head为0之后接着调用addFirst()，虽然空余空间还够用，但head为-1，下标越界了。下列代码很好的解决了这两个问题。
//addFirst(E e)
public void addFirst(E e) {
if (e == null)//不允许放入null
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;//2.下标是否越界
if (head == tail)//1.空间是否够用
doubleCapacity();//扩容
}
上述代码我们看到，空间问题是在插入之后解决的，因为tail总是指向下一个可插入的空位，也就意味着elements数组至少有一个空位，所以插入元素的时候不用考虑空间问题。
下标越界的处理解决起来非常简单，head = (head - 1) & (elements.length - 1)就可以了，这段代码相当于取余，同时解决了head为负值的情况。因为elements.length必需是2的指数倍，elements - 1就是二进制低位全1，跟head - 1相与之后就起到了取模的作用，如果head - 1为负数(其实只可能是-1)，则相当于对其取相对于elements.length的补码。
下面再说说扩容函数doubleCapacity()，其逻辑是申请一个更大的数组(原数组的两倍)，然后将原数组复制过去。过程如下图所示:
图中我们看到，复制分两次进行，第一次复制head右边的元素，第二次复制head左边的元素。
//doubleCapacity()
private void doubleCapacity() {
assert head == tail;
int p = head;
int n = elements.length;
int r = n - p; // head右边元素的个数
int newCapacity = n << 1;//原空间的2倍
if (newCapacity < 0)
throw new IllegalStateException("Sorry, deque too big");
Object[] a = new Object[newCapacity];
System.arraycopy(elements, p, a, 0, r);//复制右半部分，对应上图中绿色部分
System.arraycopy(elements, 0, a, r, p);//复制左半部分，对应上图中灰色部分
elements = (E[])a;
head = 0;
tail = n;
}
addLast()
addLast(E e)的作用是在Deque的尾端插入元素，也就是在tail的位置插入元素，由于tail总是指向下一个可以插入的空位，因此只需要elements[tail] = e;即可。插入完成后再检查空间，如果空间已经用光，则调用doubleCapacity()进行扩容。
public void addLast(E e) {
if (e == null)//不允许放入null
throw new NullPointerException();
elements[tail] = e;//赋值
if ( (tail = (tail + 1) & (elements.length - 1)) == head)//下标越界处理
doubleCapacity();//扩容
}
下标越界处理方式addFirt()中已经讲过，不再赘述。
pollFirst()
pollFirst()的作用是删除并返回Deque首端元素，也即是head位置处的元素。如果容器不空，只需要直接返回elements[head]即可，当然还需要处理下标的问题。由于ArrayDeque中不允许放入null，当elements[head] == null时，意味着容器为空。
public E pollFirst() {
int h = head;
E result = elements[head];
if (result == null)//null值意味着deque为空
return null;
elements[h] = null;//let GC work
head = (head + 1) & (elements.length - 1);//下标越界处理
return result;
}
pollLast()
pollLast()的作用是删除并返回Deque尾端元素，也即是tail位置前面的那个元素。
public E pollLast() {
int t = (tail - 1) & (elements.length - 1);//tail的上一个位置是最后一个元素
E result = elements[t];
if (result == null)//null值意味着deque为空
return null;
elements[t] = null;//let GC work
tail = t;
return result;
}
peekFirst()
peekFirst()的作用是返回但不删除Deque首端元素，也即是head位置处的元素，直接返回elements[head]即可。
public E peekFirst() {
return elements[head]; // elements[head] is null if deque empty
}
peekLast()
peekLast()的作用是返回但不删除Deque尾端元素，也即是tail位置前面的那个元素。
public E peekLast() {
return elements[(tail - 1) & (elements.length - 1)];
}