栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

栈的示意图：

java中的Stack

　　Stack 类表示后进先出（LIFO）的对象堆栈。它通过五个操作对类 Vector 进行了扩展 ，允许将向量视为堆栈。它提供了通常的 push 和 pop 操作，以及取堆栈顶点的 peek 方法、测试堆栈是否为空的 empty 方法、在堆栈中查找项并确定到堆栈顶距离的 search 方法。首次创建堆栈时，它不包含项。

Deque 接口及其实现提供了 LIFO 堆栈操作的更完整和更一致的 set，应该优先使用此 set，而非此类。例如：


Deque<Integer> stack = new ArrayDeque<Integer>(); 
　

成员方法：

E push(E item) 
把项压入堆栈顶部。 　

E pop() 
移除堆栈顶部的对象，并作为此函数的值返回该对象。 　

E peek() 
查看堆栈顶部的对象，但不从堆栈中移除它。 　

boolean empty() 
测试堆栈是否为空。 　

int search(Object o) 
返回对象在堆栈中的位置，以 1 为基数。　

Stack继承于Vector，Vector本身是一个可增长的对象数组。 
Stack并不要求其中保存数据的唯一性，当Stack中有多个相同的item时，调用search方法，只返回与查找对象equal并且离栈顶最近的item与栈顶间距离。

empty（）

　　判断stack是否为空，就需要有一个变量来计算当前栈的长度，如果该变量为0，则表示该栈为空。

源码：

public boolean empty() {
    return size() == 0;
}

 
 

size()方法在父类Vector中实现了，在Vector里面有一个变量elementCount来表示容器里元素的个数。如果为0，则表示容器空。

public synchronized int size() {  
    return elementCount;  
}  

  
  

peek（）

　　返回栈顶端的元素，如果栈为空的话，则要抛出异常。

public synchronized E peek() {  
    int     len = size();  

    if (len == 0)  
        throw new EmptyStackException();  
    return elementAt(len - 1);  
}  

 
 

elementAt方法也是在Vector里面实现的，实际上是用一个elementData的Object数组来存储元素的。

public synchronized E elementAt(int index) {  
    if (index >= elementCount) {  
        throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);  
    }  

    return elementData(index);  
}  

@SuppressWarnings("unchecked")  
E elementData(int index) {  
    return (E) elementData[index];  
} 

 
 

peek（）

　　将栈顶的元素弹出来，如果栈里有元素，就取最顶端的那个，否则就要抛出异常。

public synchronized E pop() {  
　    E   obj;  
  　  int  len = size();  

   　 obj = peek();  
   　 removeElementAt(len - 1);  

   　 return obj;  
} 

 
 

　　通过peek()取到顶端的元素之后，我们需要用removeElementAt()方法将最顶端的元素移除。 
removeElementAt()方法定义在vector中。

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 */  
}  

 
 

　　这里用待删除元素的后面元素依次覆盖前面一个元素。这样，就相当于将数组的实际元素长度给缩短了。

push（）

　　将数据入栈

public E push(E item) {  
    addElement(item);  

    return item;  
}

 
 

　　将要入栈的元素放到数组的末尾，再将数组长度加1就可以了。addElement（）方法也在vector中（好父亲啊）。

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);  
}  

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);  
}  

private static int hugeCapacity(int minCapacity) {  
    if (minCapacity < 0) // overflow  
        throw new OutOfMemoryError();  
    return (minCapacity > MAX_ARRAY_SIZE) ?  
        Integer.MAX_VALUE :  
        MAX_ARRAY_SIZE;  
} 

 
 

search（）

　　找到一个最靠近栈顶端的匹配元素，然后返回这个元素到栈顶的距离

public synchronized int search(Object o) {  
    int i = lastIndexOf(o);  

    if (i >= 0) {  
        return size() - i;  
    }  
    return -1;  
} 

 
 

对应在vector里面的实现也相对容易理解：

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;  
}