【基本数据结构】栈

一、后进先出（LIFO）

栈是一种操作受限的线性表，只允许在一端插入和删除数据，这一端叫做栈顶，对应的另一端叫做栈底。向栈中添加元素也叫进栈、入栈、压栈，从栈中删除元素也叫出栈、退栈、弹栈。

适用场景：当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，就应该首选栈。

二、栈的实现

栈可以用数组来实现，叫做顺序栈，也可以用链表来实现，叫做链式栈。

栈支持的操作：

• 入栈（push）
• 出栈（pop）
• 栈空（isEmpty）
• 栈满（isFull）
• 元素数量（size）

2.1 数组实现（顺序栈）

/**
 * 顺序栈
 *
 * @author Luwei
 * @since 2023-03-01 22:05:48
 */
public class ArrayStack<T> {
    private Object[] items;
    private int capacity;
    private int size;
    
    /**
     * 构造方法
     *
     * @param capacity 栈初始容量
     */
    public ArrayStack(int capacity) {
        this.capacity = capacity;
        size = 0;
        items = new Object[capacity];
    }
    
    /**
     * 默认构造方法，默认初始容量为 10
     */
    public ArrayStack() {
        this(10);
    }
    
    /**
     * 入栈，栈满会扩容为原来的 2 倍大小
     *
     * @param element 入栈元素
     * @return 入栈是否成功
     */
    public boolean push(T element) {
        if (size == capacity) { // 栈满，扩容为原来的2倍
            capacity <<= 1;
            items = Arrays.copyOf(items, capacity);
        }
        items[size] = element;
        size++;
        return true;
    }
    
    /**
     * 出栈
     *
     * @return 栈顶元素，栈空返回 null
     */
    public T pop() {
        if (size == 0) { // 栈空
            return null;
        }
        size--;
        return (T) items[size];
    }
}

2.2 链表实现（链式栈）

/**
 * 链式栈
 *
 * @author Luwei
 * @since 2023-03-01 22:34:03
 */
public class LinkedStack<T> {
    private Node<T> top;
    private int size;
    
    /**
     * 构造方法，使用带头双向链表
     */
    public LinkedStack() {
        size = 0;
        top = new Node<>(null, null, null);
    }
    
    /**
     * 入栈
     *
     * @param element 入栈元素
     * @return 入栈是否成功
     */
    public boolean push(T element) {
        Node<T> newNode = new Node<>(top, element, null);
        top.next = newNode;
        top = newNode;
        size++;
        return true;
    }
    
    /**
     * 出栈
     *
     * @return 栈顶元素，栈空返回 null
     */
    public T pop() {
        if (size == 0) { // 栈空
            return null;
        }
        Node<T> tmp = top;
        top = top.prev;
        top.next = null;
        size--;
        return tmp.item;
    }
    
    private static class Node<T> {
        private Node<T> prev;
        private T item;
        private Node<T> next;
        
        public Node(Node<T> prev, T item, Node<T> next) {
            this.prev = prev;
            this.item = item;
            this.next = next;
        }
    }
}

三、栈的应用

3.1 括号匹配

假设表达式中只包含三种括号，圆括号 ()、方括号[]和花括号{}，并且它们可以任意嵌套，但必须成对出现。比如，{[] ()[{}]}或[{()}([])]为合法格式，而{[}()]或[({)]为不合法的格式。现在有一个包含三种括号的表达式字符串，如何检查它是否合法呢？

用栈解决。从左到右依次遍历字符，用栈保存未匹配的左括号。当遇到到左括号时，将其压入栈中；当遇到右括号时，从栈顶取出一个左括号，如果能够匹配，比如“(”跟“)”匹配，“[”跟“]”匹配，“{”跟“}”匹配，则继续扫描剩下的字符串，如果扫描过程中，遇到不能配对的右括号，或者栈中没有数据，为非法格式。当所有的括号都扫描完成之后，如果栈为空，说明字符串格式合法；否则，说明有未匹配的左括号，为非法格式。