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