爱站程序员基地前言
集合源码分析系列：Java集合源码分析
前面已经把
Vector
,
ArrayList
,
LinkedList
分析完了，本来是想开始
Map
这一块，但是看了下面这个接口设计框架图：整个接口框架关系如下（来自百度百科）：
原来还有一个漏网之鱼，
Stack
栈的是挂在
Vector
下，前面我们已经分析过
Vector
了，那么顺便把
Stack
分析一遍。再不写就2022年了：
Stack介绍
栈是一种数据结构，并不是
Java
特有的，在
Java
里面体现是
Stack
类。它的本质是先进后出，就像是一个桶，只能不断的放在上面，取出来的时候，也只能不断的取出最上面的数据。要想取出底层的数据，只有等到上面的数据都取出来，才能做到。当然，如果有这种需求，我们一般会使用双向队列。
以下是栈的特性演示：
Stack
在
Java
中是继承于
Vector
，这里说的是
1.8
版本，共用了
Vector
底层的数据结构，底层都是使用数组实现的，具有以下的特点：
- 先进后出（“FILO`）
- 继承于
Vector
,同样基于数组实现
- 由于使用的几乎都是
Vector
，
Vector
的操作都是线程安全的，那么
Stack
操作也是线程安全的。
类定义源码：
publicclass Stack<E> extends Vector<E> {}
成员变量只有一个序列化的变量：
private static final long serialVersionUID = 1224463164541339165L;
方法解读
Stack
没有太多自己的方法，几乎都是继承于
Vector
，我们可以看看它自己拓展的 5 个方法：
-
E push(E item)
: 压栈
-
synchronized E pop()
: 出栈
-
synchronized E peek()
:获取栈顶元素
-
boolean empty()
:判断栈是不是为空
-
int search(Object o)
: 搜索某个对象在栈中的索引位置
push 方法
在底层实际上调用的是
addElement()
方法，这是
Vector
的方法：
public E push(E item) {addElement(item);return item;}
在前面我们已经分析过
Vecor
的源码，感兴趣可以参考：http://aphysia.cn/archives/java-ji-he-11vector-chao-ji-xiang-xi-yuan-ma-jie-xi
addElement
是线程安全的，在底层实际上就是往数组后面添加了一个元素，但是它帮我们保障了容量，如果容量不足，会触发自动扩容机制。
public synchronized void addElement(E obj) {modCount++;ensureCapacityHelper(elementCount + 1);elementData[elementCount++] = obj;}
pop 方法
底层是先调用
peek()
方法，获取到栈顶元素，再调用
removeElementAt（）
方法移除掉栈顶元素，实现出栈效果。
public synchronized E pop() {E obj;int len = size();obj = peek();removeElementAt(len - 1);return obj;}
removeElementAt(int index)
也是
Vector
的方法，
synchronized
修饰，也是线程安全的，由于移除的是数组最后的元素，所以在这里不会触发元素复制，也就是
System.arraycopy(elementData, index + 1, elementData, index, j);
:
public synchronized void removeElementAt(int index) {modCount++;if (index >= elementCount) {throw new ArrayIndexOutOfBoundsException(index + " >= " +elementCount);}else if (index < 0) {throw new ArrayIndexOutOfBoundsException(index);}int j = elementCount - index - 1;if (j > 0) {System.arraycopy(elementData, index + 1, elementData, index, j);}elementCount--;elementData[elementCount] = null; /* to let gc do its work */}
peek 方法
获取栈顶元素，先获取数组的大小，然后再调用
Vector
的
E elementAt(int index)
获取该索引的元素：
public synchronized E peek() {int len = size();if (len == 0)throw new EmptyStackException();return elementAt(len - 1);}
E elementAt(int index)
的源码如下,里面逻辑比较简单，只有数组越界的判断：
public synchronized E elementAt(int index) {if (index >= elementCount) {throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);}return elementData(index);}
empty 方法
主要是用来判空，判断元素栈里面有没有元素，主要调用的是
size()
方法：
public boolean empty() {return size() == 0;}
这个
size()
方法其实也是
Vector
的方法，返回的其实也是一个类变量，元素的个数：
public synchronized int size() {return elementCount;}
search方法
这个方法主要用来查询某个元素的索引，如果里面存在多个，那么将会返回最后一个元素的索引：
public synchronized int search(Object o) {int i = lastIndexOf(o);if (i >= 0) {return size() - i;}return -1;}
使用
synchronized
修饰，也是线程安全的，为什么需要这个方法呢？
我们知道栈是先进先出的，如果需要查找一个元素在其中的位置，那么需要一个个取出来再判断，那就太麻烦了，而底层使用数组进行存储，可以直接利用这个特性，就可以快速查找到该元素的索引位置。
至此，回头一看，你是否会感到疑惑，“Stack
里面没有任何的数据，但是却不断的在操作数据，这得益于
Vector`的数据结构：
// 底层数组protected Object[] elementData;// 元素数量protected int elementCount;
底层使用数组，保存了元素的个数，那么操作元素其实只是不断往数组中插入元素，或者取出最后一个元素即可。
总结
stack
由于继承了
Vector
，因此也是线程安全的，底层是使用数组保存数据，大多数
API
都是使用
Vector
来保存。它最重要的属性是先进先出。至于数组扩容，沿用了
Vector
中的扩容逻辑。
如果让我们自己实现，底层不一定使用数组，使用链表也是能实现相同的功能的，只是在整个集合源码体系中，共有相同的部分，是不错的选择。
【作者简介】：
秦怀，公众号【秦怀杂货店】作者，个人网站：http://aphysia.cn，技术之路不在一时，山高水长，纵使缓慢，驰而不息。
剑指Offer全部题解PDF
开源编程笔记
