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;
}
AI 代码解读
它继承于 Vector 类，这个跟前面讲的 ArrayList 是一样的，只不过 Vector 类方法是同步的，因此 Stack 也是线程安全的。
push
入栈
public E push(E item) {
addElement(item);
return item;
}
AI 代码解读
虽然此方法没有声明 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);
}
AI 代码解读
虽然 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;
}
AI 代码解读
pop 方法被声明为 synchronized ，是线程安全的方法。它通过 peek 方法获取到栈顶元素对象，然后调用父类的 removeElementAt 方法把栈顶元素删除。
peek
查看栈顶元素
public synchronized E peek() {
int len = size();
if (len == 0)
throw new EmptyStackException();
return elementAt(len - 1);
}
AI 代码解读
这个方法也是线程安全的。可以看出如果栈的大小为0时，执行 peek 方法会抛出 EmptyStackException 异常。
search
在栈中搜索元素
public synchronized int search(Object o) {
int i = lastIndexOf(o);
if (i >= 0) {
return size() - i;
}
return -1;
}
AI 代码解读
继续查看父类代码
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;
}
AI 代码解读
在栈中查询一个元素需要遍历，时间复杂度为O(n)。
0x02 总结
栈是一种LIFO的数据结构，它基于 Vector 来实现，所有的方法都是线程安全的。入栈和出栈操作的时间复杂度为O(1)，查找元素的时间复杂度为O(n)。
