源码阅读之Java栈的实现
0x00 栈 栈是 Last-In-First-Out （后进先出）的线性表。对栈的操作主要有两个：入栈(push)和出栈(pop)。因此它也是一种操作受限的线性表。尽管如此，它在计算机中应用非常广泛，是一种非常基础的数据结构。 0x01 源码 从源码中可以看出栈也是一种非常简单的数据结构。栈的源码非常简洁，只有100多行代码。 public class Stack<E> extends Vector<E> { public Stack() { } //入栈操作 public E push(E item) { addElement(item); return item; } //出栈操作 public synchronized E pop() { E obj; int len = size(); obj = peek(); removeElementAt(len - 1); return obj; } //查看栈元素，不会删除 public synchronized E peek() { int len = size(); if (len == 0) throw new EmptyStackException(); return elementAt(len - 1); } //检查是否为空栈 public boolean empty() { return size() == 0; } //查找元素，如果找到则返回从栈顶开始计数的位置，否则返回-1 public synchronized int search(Object o) { int i = lastIndexOf(o); if (i >= 0) { return size() - i; } return -1; } /** use serialVersionUID from JDK 1.0.2 for interoperability */ private static final long serialVersionUID = 1224463164541339165L; } 它继承于 Vector 类，这个跟前面讲的 ArrayList 是一样的，只不过 Vector 类方法是同步的，因此 Stack 也是线程安全的。 push 入栈 public E push(E item) { addElement(item); return item; } 虽然此方法没有声明 synchronized，但内部调用一个 addElement 来实现入栈操作。这个操作方法是在父类中实现的，它被声明为线程安全的，因此它也是线程安全的。 public synchronized void addElement(E obj) { modCount++; ensureCapacityHelper(elementCount + 1); elementData[elementCount++] = obj; } private void ensureCapacityHelper(int minCapacity) { // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); } //扩容方法 //这里跟 ArrayList 扩容算法有点不一样，ArrayList 一次是扩容为原来的1.5倍，Vector 默认扩容为原来的1倍 private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); elementData = Arrays.copyOf(elementData, newCapacity); } 虽然 push 方法没有声明 synchronized 但 addElement 方法中有。在这个方法里 首先把 modCount 加 1，记录一次对数据结构的操作。 然后检查数组容量是否足够，不够则扩容。 最后把元素对象添加到数组末尾。 需要注意的是Vector的扩容策略是默认一次扩容为原来的1倍，这与ArrayList 一次扩容原来的1.5倍不同。 pop 出栈 public synchronized E pop() { E obj; int len = size(); obj = peek(); removeElementAt(len - 1); return obj; } pop 方法被声明为 synchronized ，是线程安全的方法。它通过 peek 方法获取到栈顶元素对象，然后调用父类的 removeElementAt 方法把栈顶元素删除。 peek 查看栈顶元素 public synchronized E peek() { int len = size(); if (len == 0) throw new EmptyStackException(); return elementAt(len - 1); } 这个方法也是线程安全的。可以看出如果栈的大小为0时，执行 peek 方法会抛出 EmptyStackException 异常。 search 在栈中搜索元素 public synchronized int search(Object o) { int i = lastIndexOf(o); if (i >= 0) { return size() - i; } return -1; } 继续查看父类代码 public synchronized int lastIndexOf(Object o) { return lastIndexOf(o, elementCount-1); } public synchronized int lastIndexOf(Object o, int index) { if (index >= elementCount) throw new IndexOutOfBoundsException(index + " >= "+ elementCount); if (o == null) {//如果查找的元素是空的则遍历找到最接近栈的空元素 for (int i = index; i >= 0; i--) if (elementData[i]==null) return i; } else { for (int i = index; i >= 0; i--) if (o.equals(elementData[i]))//通过equals方法来判断两个元素是否相同 return i; } return -1; } 在栈中查询一个元素需要遍历，时间复杂度为O(n)。 0x02 总结 栈是一种LIFO的数据结构，它基于 Vector 来实现，所有的方法都是线程安全的。入栈和出栈操作的时间复杂度为O(1)，查找元素的时间复杂度为O(n)。
