栈：从简单栈到解决经典栈问题

Java学习手册+面试指南：https://javaxiaobear.cn

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

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

1、栈的API设计

public class Stack<T> implements Iterable<T>{
    /**
     *   栈长度
     */
    private int size;

    /**
     * 头结点
     */
    private Node head;

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

    public boolean isEmpty(){
        return size == 0;
    }

    public int size(){
        return size;
    }

    /**
     * 数据入栈
     * @param t
     */
    public void push(T t){
        Node next = head.next;
        //新节点
        Node newNode = new Node(t, next);
        //重新赋值
        head.next = newNode;
        size++;
    }

    /**
     * 数据出栈
     * @return
     */
    public T pop(){
        Node next = head.next;
        if(null == next){
            return null;
        }
        head.next = head.next.next;
        size--;
        return next.item;
    }

    @Override
    public Iterator<T> iterator() {
        return new SIterator();
    }

    private class SIterator implements Iterator<T>{
        private Node n = head;
        @Override
        public boolean hasNext() {
            return n.next!=null;
        }
        @Override
        public T next() {
            Node node = n.next;
            n = n.next;
            return node.item;
        }
    }

    private class Node{
        public T item;
        public Node next;
        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }
}

2、括号匹配问题

给定一个字符串，里边可能包含"()"小括号和其他字符，请编写程序检查该字符串的中的小括号是否成对出现。
例如：
“(上海)(长安)”：正确匹配
“上海((长安))”：正确匹配
“上海(长安(北京)(深圳)南京)”:正确匹配
“上海(长安))”：错误匹配
“((上海)长安”：错误匹配

步骤：

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

/**
     * 左括号入栈，右括号出栈
     * @param str
     * @return
     */
public boolean isMatch(String str){
    //创建一个栈存储左括号
    Stack<String> stack = new Stack<>();
    for (int i = 0; i < str.length(); i++) {
        
        if(s.equals("(")){
            stack.push(s);
        }else if(s.equals(")")){
            String pop = stack.pop();
            if (pop == null) {
                return false;
            }
        }
    }
    //栈中元素是否为空
    if(stack.size == 0){
        return true;
    }
    return false;
}

3、逆波兰表达式

中缀表达式就是我们平常生活中使用的表达式，例如：1+32,2-(1+3)等等*

中缀表达式的特点是：二元运算符总是置于两个操作数中间

逆波兰表达式(后缀表达式)：

逆波兰表达式是波兰逻辑学家J?卢卡西维兹(J? Lukasewicz)于19 29年首先提出的一种表达式的表示方法，后缀表达式的特点：运算符总是放在跟它相关的操作数之后。

给定一个只包含加减乘除四种运算的逆波兰表达式的数组表示方式，求出该逆波兰表达式的结果

/**
     * 求逆波兰表达式
     * @param number
     * @return
     */
public int caculate(String[] number){
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < number.length; i++) {
        String s = number[i];
        Integer pop;
        Integer pop1;
        Integer temp;
        if("+".equals(s)){
            pop = stack.pop();
            pop1 = stack.pop();
            temp = pop + pop1;
            stack.push(temp);
        }else if("-".equals(s)){
            pop = stack.pop();
            pop1 = stack.pop();
            temp = pop1 - pop;
            stack.push(temp);
        }else if("*".equals(s)){
            pop = stack.pop();
            pop1 = stack.pop();
            temp = pop1 * pop;
            stack.push(temp);
        }else if("/".equals(s)){
            pop = stack.pop();
            pop1 = stack.pop();
            temp = pop1 / pop;
            stack.push(temp);
        }else {
            stack.push(Integer.parseInt(s));
        }
    }
    return stack.pop();
}