概述

栈是一种基于先进后出（FILO）的数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底（压栈/入栈），最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（弹栈/出栈）（最后一 个数据被第一个读出来）。

我们称数据进入到栈的动作为压栈，数据从栈中出去的动作为弹栈。

栈的实现

API设计

类名：Stack
构造方法 Stack()：创建Stack对象
成员方法
	public boolean isEmpty()：判断栈是否为空，是返回true，否返回false
	public int size()：获取栈中元素的个数
	public E pop()：弹出栈顶元素
	public void push(E e)：向栈中压入元素e
成员变量
	private Node head：记录首结点
	private int n：当前栈的元素个数

代码实现

//栈
public class Stack<E> {
    //记录首结点
    private Node<E> head;
    //当前栈的元素个数
    private int n;

    public Stack() {
        head = new Node(null, null);
        n = 0;
    }

    //判断栈是否为空，是返回true，否返回false
    public boolean isEmpty() {
        return n == 0;
    }

    //获取栈中元素的个数
    public int size() {
        return n;
    }

    //弹出栈顶元素
    public E pop() {
        //记录栈顶元素
        Node oldFirst = head.next;
        if (oldFirst == null) {
            return null;
        }
        //删除首个元素
        head.next = head.next.next;
        //个数-1
        n--;
        return (E) oldFirst.item;
    }

    //向栈中压入元素e
    public void push(E e) {
        // 记录旧的下一个节点，栈顶元素
        Node oldNext = head.next;
        // 创建新的节点
        Node node = new Node(e, oldNext);
        // 个数+1
        n++;
        // 新的节点连接到head的下一个节点
        head.next = node;
    }

    private class Node<E> {
        E item;
        Node next;

        public Node(E item, Node<E> next) {
            this.item = item;
            this.next = next;
        }
    }
}

括号匹配案例

给定一个字符串，里边可能包含"()"小括号和其他字符，请编写程序检查该字符串的中的小括号是否成对出现。 （左括号数量与右括号数量相同）

分析
1. 创建一个栈用来存储左括号
2. 从左往右遍历字符串，拿到每一个字符
3. 判断该字符是不是左括号，如果是，放入栈中存储
4. 判断该字符是不是右括号，如果不是，继续下一次循环
5. 如果该字符是右括号，则从栈中弹出一个元素t；
6. 判断元素t是否为null，如果不是null，则证明有对应的左括号，如果是null，则证明没有对应的左括号
7. 循环结束后，判断栈中还有没有剩余的左括号，如果有，则不匹配，如果没有，则匹配

/**
 * 判断str中左右括号是否匹配
 * @param str 待匹配的字符串
 * @return
 */
private static boolean matchBrackets(String str) {
    // 1. 创建一个栈来存储左括号
    Stack<String> stack = new Stack();
    // 2. 从右往右遍历字符串，拿到每一个字符
    for (int i = 0; i < str.length(); i++) {
        // 拿到每一个字符串
        String currentChar = str.charAt(i) + "";
        // 3.判断该字符串是不是左括号，如果是，则放入栈中
        if (currentChar.equals("(")) {
            stack.push(currentChar);
            // 4. 判断该字符串是否是右括号，如果是，从栈中弹出一个元素t
        } else if (currentChar.equals(")")) {
            String t = stack.pop();
            // 判断t是否为null。如果为null说明没有左括号匹配，否则有左括号匹配
            if (t == null) {
                return false;
            }
            // 如果不是，继续下一个循环
        }
    }
    // 循环完毕之后，判断栈中是否还有剩余的左括号，如果有，说明不匹配，如果没有，则匹配
    if (stack.size() == 0) {
        return true;
    } else {
        return false;
    }
}