1、定义

栈是一种限定仅在表尾进行插入和删除操作的遵循后进先出原则的线性表。

1.1、栈顶

增删操作的一端称为栈顶。是栈的一个指针。

1.2、栈底

相对栈顶的另一端称为栈底。是栈的另一个指针。

1.3、压栈(或入栈或进栈)

向栈插入新元素，使其成为新的栈顶元素的过程。

1.4、出栈(或退栈)

从栈顶删除元素，使其相邻元素成为新的栈顶元素的过程。

1.5、空栈

栈内没有数据，栈顶即栈底。

栈.png

2、特点：后进先出

栈的数据增删操作只允许在栈顶进行。

3、栈结构的必要性。

从功能上看，数组或链表可以替代栈，但是数组或链表过多暴露了数据操作的接口，当数据量大的时候会有隐患；栈在处理数据仅在一端操作的场景时效率比数组和链表更高。

4、适用场景

4.1、浏览器前进与后退功能。

4.2、校验字符串中括号匹配顺序是否合法。

5、类型

5.1、顺序栈

利用动态长度的对象数组实现，数组尾部为栈顶，栈顶元素增删查效率最高。每次创建数组对象都需要开辟一段连续且固定大小的内存空间，不仅容易造成内存浪费，而且频繁对数组扩容产生的内存垃圾也会越来越多，JVM GC的频率可能会加快，每次GC都会有额外的开销，影响性能。不推荐通过数组实现栈。

实现代码：

package com.zy.demo.util;

import java.util.Arrays;

/**
 * 通过数组实现顺序栈
 * @param <E> 元素类型
 * @author zhangyoung93
 */
public class StackUtil<E> {

    //声明对象数组
    private Object[] objects;

    //栈的默认初始化结果
    private static final Object[] DEFAULT_OBJECTS = {};

    //栈的默认容量
    private static final int DEFAULT_CAPACITY = 10;

    //栈的元素个数
    private int size;

    //无参构造函数
    public StackUtil(){
        this.objects = DEFAULT_OBJECTS;
    }

    /**
     * 指定初始容量的构造函数
     * @param capacity 初始容量
     */
    public StackUtil(int capacity){
        if(capacity > 0){
            this.objects = new Object[capacity];
        }else if(capacity == 0){
            this.objects = DEFAULT_OBJECTS;
        }else{
            throw new IllegalArgumentException("Illegal Capacity:" + capacity);
        }
    }

    /**
     * 获取栈内的元素个数
     * @return 栈内的元素个数
     */
    public int size(){
        return this.size;
    }

    /**
     * 校验规则
     * @param index 数组索引
     */
    private void valid(int index){
        //数组越界校验
        if(index < 0 || this.size > 0 && index > this.size - 1){
            throw new IndexOutOfBoundsException("Index:" + index);
        }
    }

    /**
     * 打印栈内元素
     */
    @Override
    public String toString() {
        return Arrays.toString(this.objects);
    }

    /**
     * 压栈
     * 时间复杂度：O(1) --数组尾部添加元素，直接通过索引赋值。
     * 空间复杂度：O(n) --新建数组对象，数组大小与输入数据量n线性相关。
     * @param e 元素
     * @return 添加元素成功返回true；否则返回false。
     */
    public boolean push(E e){
        //原数组中无元素，则新建默认容量的数组
        if(this.objects == DEFAULT_OBJECTS){
            this.objects = new Object[DEFAULT_CAPACITY];
        }else{
            //添加元素后数组长度大于数组容量，则扩容。
            if(this.size + 1 > this.objects.length){
                //先校验容量是否超过Integer的最大值，控制JVM内存使用量。
                if(this.size + 1 >= Integer.MAX_VALUE){
                    throw new OutOfMemoryError("The size of stack is too large!");
                }
                //扩容值规定：如果原数组长度小于默认容量，则扩容到默认容量；否则扩容到原数组长度的1.5倍。
                int newLength = this.objects.length < DEFAULT_CAPACITY ? DEFAULT_CAPACITY : (int) (1.5 * this.objects.length);
                //重新实例化扩容后的数组
                this.objects = Arrays.copyOf(this.objects, newLength);
            }
        }
        //新添加的元素赋值到原数组尾部，不需要考虑索引的重排列。
        this.objects[this.size++] = e;
        return true;
    }

    /**
     * 出栈
     * 时间复杂度：O(1) --数组根据索引取值。
     * 空间复杂度：O(1) --使用有限的变量资源。
     * @return 出栈的元素
     */
    public E pop(){
        //获取栈顶元素
        E popElement = get(this.size-1);
        //栈顶元素置为null
        this.objects[--this.size] = null;
        //size--可能会导致数组越界
        return popElement;
    }

    /**
     * 在栈中从栈底到栈顶查找指定索引处的元素
     * 时间复杂度：O(1) --数组根据索引查找元素。
     * 空间复杂度：O(1) --使用有限的变量资源。
     * @param index 索引
     * @return 元素
     */
    @SuppressWarnings("unchecked")
    public E get(int index){
        valid(index);
        return (E)this.objects[index];
    }

    /**
     * 修改栈顶元素
     * 时间复杂度：O(1) --数组根据索引查找元素。
     * 空间复杂度：O(1) --使用有限的变量资源。
     * @param e 修改后的元素
     * @return 修改成功返回true；否则返回false。
     */
    public boolean modPop(E e){
        //注意不能对size做赋值。
        this.objects[this.size-1] = e;
        return true;
    }
}

5.2、链式栈

利用单向链表实现，链表头结点为栈顶，栈顶元素增删查效率最高。链表对内存的利用率高，性能较好。