Stack(栈)是一种比较典型的数据结构，其元素满足后进先出(LIFO)的特点。
Java中Stack的实现继承自Vector，所以其天然的具有了一些Vector的特点，所以栈也是线程安全的。
class Stack<E> extends Vector<E> {
事实上，除了继承自Vector的那些方法之外，Stack只提供了5个方法：
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;
}
public synchronized int search(Object o) {
int i = lastIndexOf(o);
if (i >= 0) {
return size() - i;
}
return -1;
}
push函数是用来向Stack的顶部压入一个元素，影响其性能的是 addElement的性能：
public synchronized void addElement(E obj) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = obj;
}
可以看出，其方法是在Vector的最后加入一个元素，其时间复杂度是o(1)。
peek函数是从查看栈顶元素，但是不删除。其性能主要是由Vector的elementAt函数决定的：
public synchronized E elementAt(int index) {
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
}
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}
由于Vector的底层是数组实现的，通过下标可以直接进行定位，所以peek的时间复杂度也是o(1)。
pop函数是移除并获取到栈顶元素，在源码中可以看到，这里调用peek获取了栈顶元素，使用removeElementAt来删除栈顶元素，这个函数也正是决定pop性能的关键：
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 */
}
咋一看来，这里删除一个元素之后，都会对数组中的元素进行复制调整，时间复杂度是o(n)，但是考虑到传进来的index值的特殊性：
index = elementCount -1；
这样的话if(j>0)的条件永远都不会成立，因为j永远都是0，中间复制调整元素的操作就避免了，仅仅是在最后把Vector最后的值赋值为null，时间复杂度是o(1)。
search是查找一个元素在Stack中的index，这里起作用的是Vector的lastIndexOf函数，代码如下：
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]))
return i;
}
return -1;
}
可以看出，查找的过程是从后向前，挨个比较，其时间复杂度必然是o(n)。
Stack是Vector的子类，所以Vector的函数这里也适用，这里不再赘述，在Vector相关的介绍文章中会有。
Stack是线程安全的，所以其性能必然受到影响，如果需要使用一个非线程安全的Stack，可以直接使用LinkedList，LinkedList本身提供的方法就包含了Stack的操作。