数据结构之「栈」

什么是栈？

栈 是一种抽象的数据结构，只允许在有序线性数据集合的一段进行入栈和出栈操作，因此是按照后进先出（LIFO, Last In First Out）的原理操作元素。允许进行入栈和出栈的一端称为栈顶（TOP），另一端称为栈底（BOTTOM）。栈顶会随出栈入栈浮动的，当栈中元素个数为零时称为空栈。
栈常用一维数组或链表来实现。
栈的特点：
先进后出，后入先出。
除头尾节点外，每个元素有一个前驱节点，一个后继节点。

栈

栈有什么作用？

由于栈结构是后进先出原则，常用于程序里的递归，函数调用，局部变量临时存储，浏览器里的前进后。在大话数据结构和算法一书中举例特形象，手枪的弹夹就是栈的典型使用，装弹其实就是入栈操作，开枪其实就是出栈操作。

栈该怎么使用？

我用一维数组来简单实现入栈出栈。
栈的存储结构

public class Stack {
    //存储元素
    Object[] elementData;
    //元素个数
    int elementCount;
}

入栈

public E push(E item) {
    //需要的最小容量是当前元素总数 + 1
    int minCapacity = elementCount + 1;
    //假如最小需要元素总数大于数组长度，这扩容一倍
    if (minCapacity - elementData.length > 0) {
        int newCapacity = minCapacity * 2;
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    //给元素总数加一并把元素赋值给数组
    elementData[elementCount++] = item;
}

出栈

public E pop() {
    //获取元素总数
    int len = elementCount;
    //获取栈顶元素
    E obj = (E) elementData[len - 1];
    //元素减一
    elementCount--;
    //置空
    elementData[elementCount] = null;
}

总结

栈 在计算机的世界里是一个非常常用的数据结构，函数调用的存储和函数里分配的局部变量都用栈结构来存储的。浏览器里的前进和后退也就是一个入栈和出栈的操作。这里是用数组的方式来作为栈的存储结构，有兴趣的朋友可以用链表的方式来实现栈结构。