栈是一种只能在表尾进行插入或者删除操作的线性表。 允许插入和删除的一端叫栈顶，另一端叫栈底，无任何元素叫空栈（空表），是一种先入后出的线性表。
栈的插入操作叫进栈，也有叫压栈、入栈。（如图）
栈的删除操作叫出栈，也有叫弹栈。（如图）
栈的顺序存储结构也是线性表的存储结构，可以用数组实现。
public class ArrayStack<T> { private int DEFAULT_SIZE = 5;//默认大小 private Object[] objs; private int topIndex = 0;//用来纪录当前栈顶的下标 public ArrayStack(int DEFAULT_SIZE) { this.DEFAULT_SIZE = DEFAULT_SIZE; objs = new Object[DEFAULT_SIZE]; } public ArrayStack() { objs = new Object[DEFAULT_SIZE]; } /** * 进栈 * @param t 进栈元素 */ public void push(T t) { //表示当前数组已经没有多余空间(要扩容) if (topIndex > DEFAULT_SIZE - 1) { objs = AddSize(objs, DEFAULT_SIZE / 2); } objs[topIndex] = t; topIndex++; } /** * 出栈 * @return true 表示出栈成功，false表示栈为空，出栈失败 */ public boolean pop() { if (topIndex < 0) { return false; } //清空栈顶 objs[topIndex--] = null; return true; } /** * @param objs 表示要扩容的数组 * @param size 表示要数组要增加多大 * @return 返回扩容后的新数组 */ private Object[] AddSize(Object[] objs, int size) { int newSize = objs.length + size; Object[] newObj = new Object[newSize]; System.arraycopy(objs, 0, newObj, 0, objs.length); return newObj; } } 优点缺点存取定位方便需要提前分配空间，当空间不足时则需要扩容，影响性能，如果不扩容就会造成溢出栈的链式存储结构可以用线性表的链式存储结构来实现。
public class LinkStack<T> { //表示栈的大小 private int size; //栈顶元素 private Node top; private class Node<T> { private Node next;//存放后继节点 private T data;//数据域 public Node(T data, Node next) { this.next = next; this.data = data; } public Node() { } } /** * 入栈 * @param data */ public void push(T data) { top = new Node<>(data, top); size++; } /** * 出栈 * @return */ public T pop() { if (top == null) { return null; } Node<T> node = top; top = top.next; node.next = null; size--; return node.data; } } 优点缺点不用提前申请空间，动态分配存储空间因为多了存放指针的操作，会额外增加内存总结：如果栈的元素数量固定，建议用链式存储结构，而元素数量变化不定，则建议用链式存储结构。
JDK封装了Stack的类。位于java.util的包名下。
package java.util; public class Stack<E> extends Vector<E> { /** * 无参的构造函数 */ public Stack() { } /* * 压栈 */ public E push() { //压栈 addElement(item); //返回压入栈中的元素 return item; } /** * 出栈 */ public synchronized E pop() { E obj; int len = size(); //获取栈顶的元素 obj = peek(); //把栈顶元素置为空，并把可用数组长度减一 removeElementAt(len - 1); return obj; } }主要看压栈的方法 addElement：
//这是个线程安全的方法 public synchronized void addElement(E obj) { modCount++; //扩容 ensureCapacityHelper(elementCount + 1); //压栈给栈顶赋值 lementData为vector的object[]数组 elementData[elementCount++] = obj; }比较复杂的是扩容的方法ensureCapacityHelper：
private void ensureCapacityHelper(int minCapacity) { // 如果当前栈中的元素再加一比elementData的数组长度大，则需要扩容 if (minCapacity - elementData.length > 0) grow(minCapacity); } //传入实际栈的数量 private void grow(int minCapacity) { // 先把旧的数组长度赋值给oldCapacity int oldCapacity = elementData.length; //capacityIncrement 为自定义要增加的长度（扩容因子），没有设置则默认为0，stack没有设置这个变量，这里数组的长度为newCapacity =oldCapacity +oldCapacity . int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity); //如果新产生的数组长度小于实际需要的数组长度，则使用实际长度。 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; //如果新产生的数组长度大于 Integer.MAX_VALUE - 8 则等于Integer.MAX_VALUE 或 者Integer.MAX_VALUE - 8 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); //真正在这里扩容 elementData = Arrays.copyOf(elementData, newCapacity); }Arrays.copyOf方法：
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) { //拿到数组类型，并新建newLength长度的数组。 @SuppressWarnings("unchecked") T[] copy = ((Object)newType == (Object)Object[].class) ? (T[]) new Object[newLength] : (T[]) Array.newInstance(newType.getComponentType(), newLength); //把original的数组从0开始，复制到名为copy，下标为0开始的新数组上，到original数组长度跟newLength的最小值的地方（一般都是original.length）。 System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); //返回带有元数据的新数组 return copy; }出栈方法 pop()调用了peek()与removeElementAt()
先看peek()
public synchronized E peek() { //获取栈中元素数量 int len = size(); if (len == 0) throw new EmptyStackException(); return elementAt(len - 1); } //直接返回数组下标为index的元素 public synchronized E elementAt(int index) { if (index >= elementCount) { throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount); } return elementData(index); }再看出栈的主要方法removeElementAt：
public synchronized void removeElementAt(int index) { //计数器加1 modCount++; //如果下标大于数组总长度抛异常 if (index >= elementCount) { throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount); } //如果下标为负数抛异常 else if (index < 0) { throw new ArrayIndexOutOfBoundsException(index); } //获取需要复制数组元素的个数（用可用的数组减去栈顶的下标再减一，减一是因为下标是从0开始） int j = elementCount - index - 1; if (j > 0) { //重新构造数组，这里主要是移除非栈顶的元素，栈没有用到。 System.arraycopy(elementData, index + 1, elementData, index, j); } //有效数量键1 elementCount--; //清空数组中最后一个元素清空 elementData[elementCount] = null; /* to let gc do its work */ }可以看到java提供的栈stack用了线性表的顺序存储结构。
java提供的stack可以直接使用，不用关心栈溢出问题，调用stack的push()、pop(),就可以进行入栈出栈操作。
但有一个缺点是当Stack快速入栈多个元素后再恢复回来，在元素不变的前提下，其实elementCount数组的长度会增加，这个数组会一直占有着内存，造成内存浪费。
参考：大话数据结构
下一节 数据结构：队列
