栈

栈：

限定在表尾进行插入和删除操作的线性表。
允许插入和删除的一端为栈顶，另一端为栈底。
栈为后进先出的线性表。
栈的插入操作为入栈，删除操作为出栈。

————————————栈的顺序存储————————————
初始化构造函数：

    /**
     * 数组元素
     */
    private Object[] elementData;

    /**
     * 栈空间大小
     */
    private int stackSize;

    /**
     * 栈顶指针
     */
    private int top;

    private static final Object[] EMPTY_ELEMENT_DATA = {};

    public OrderStack(int initialCapacity) {
        if (initialCapacity == 0) {
            top = -1;
            stackSize = 0;
            elementData = EMPTY_ELEMENT_DATA;
        } else if (initialCapacity > 0) {
            top = -1;
            stackSize = initialCapacity;
            elementData = new Object[initialCapacity];

        } else {
            throw new RuntimeException("初始化数据大小不正确");
        }
    }

入栈：

    public void push(Object o) {

        //判断栈满
        if (top == stackSize - 1) {
            throw new RuntimeException("栈空间已满");
        }
        //先top = top +1 再执行elementData【top+1】;
        elementData[++top] = o;
    }

出栈：

    public Object pop() {

        if (top == -1) {
            throw new RuntimeException("空栈，无数据输出");
        }

        //先输出elementData[top]数据，再top --
        return elementData[top--];
    }

获取栈顶元素：

    public Object peek() {
        if (top == -1) {
            throw new RuntimeException("空栈，无数据输出");
        }

        return elementData[top];
    }

————————————栈的链式存储————————————
结点数据结构：

    private static class LinkedStackNode {

        private Object item;

        //下一结点
        private LinkedStackNode next;

        public LinkedStackNode(Object item, LinkedStackNode next) {
            this.item = item;
            this.next = next;
        }
    }

参数定义：

    //栈顶元素
    private LinkedStackNode top;

    //数据量
    private int size;

入栈：

    public void push(Object o) {

        //栈顶元素为空，则为栈顶元素。不空，则该新结点为栈顶
        LinkedStackNode stackNode = new LinkedStackNode(o, null);
        if (top == null) {
            top = stackNode;
        } else {
            stackNode.next = top;
            top = stackNode;
        }

        size++;

    }

出栈：

    public Object pop() {
        //栈顶元素为空，为空栈
        if (top == null) {
            throw new RuntimeException("栈空");
        }

        Object data = top.item;
        top = top.next;
        size--;

        return data;

    }

获取栈顶元素：

    public Object peek() {
        if (top == null) {
            throw new RuntimeException("栈空");
        }

        return top.item;
    }

————————————栈的应用————————————

后缀表达式：所有的符号都在要运算的数字后面出现

从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将处于栈顶两个数字出栈，进行运算，运算结果进栈，一直到最终或得结果。

中缀表达式转后缀表达式：

从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，则成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级不高于栈顶符号（乘除优先于加减）则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。