算法-栈 *** 作

栈的概念

一种特殊的线性表，其只允许在固定的一端进行插入和删除元素 *** 作。进行数据插入和删除 *** 作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则

压栈

栈的插入 *** 作叫做进栈/压栈/入栈，入数据在栈顶。

出栈

栈的删除 *** 作叫做出栈。出数据在栈顶。

JAVA集合类对应的栈（Stack）

向栈中存放元素：stack.push()；
获取栈顶元素：stack.peek()；
删除栈顶元素（返回值为删除的元素）：stack.pop()；

Stack<Integer> stack = new Stack<>();//创建一个栈
       //向栈中存放1，2，3个元素
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println(stack.peek());//获取栈顶元素 但是不删除 结果为3
        System.out.println(stack.pop());//d出栈顶元素 删除  结果为3
        System.out.println(stack.peek());//获取栈顶元素 但是不删除 结果为2
        System.out.println(stack.empty());//判断栈中元素是否为空
        System.out.println(stack.isEmpty());//判断是否为空 

最长有效括号

leetcode题号：32

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

对于遇到的每个 ‘(’，我们将它的下标放入栈中
对于遇到的每个 ‘)’ ，我们先d出栈顶元素表示匹配了当前右括号：
如果栈为空，说明当前的右括号为没有被匹配的右括号，我们将其下标放入栈中来更新我们之前提到的「最后一个没有被匹配的右括号的下标」
如果栈不为空，当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」

class Solution {
    public int longestValidParentheses(String s) {
        int maxans = 0;
        Deque<Integer> stack = new LinkedList<Integer>();
        stack.push(-1);
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    maxans = Math.max(maxans, i - stack.peek());
                }
            }
        }
        return maxans;
    }
}

基本计算器II

leetcode题号：227

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。整数除法仅保留整数部分。

输入：s = "3+2*2"
输出：7

Character.isDigit() 方法,判断字符是否为数字

加号：将数字压入栈；
减号：将数字的相反数压入栈；
乘除号：计算数字与栈顶元素，并将栈顶元素替换为计算结果。

class Solution {
    public int calculate(String s) {
        Deque<Integer> stack = new LinkedList<Integer>();
        char preSign = '+';
        int num = 0;
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            if (Character.isDigit(s.charAt(i))) {
                num = num * 10 + s.charAt(i) - '0';
            }
            if (!Character.isDigit(s.charAt(i)) && s.charAt(i) != ' ' || i == n - 1) {
                switch (preSign) {
                    case '+':
                        stack.push(num);
                        break;
                    case '-':
                        stack.push(-num);
                        break;
                    case '*':
                        stack.push(stack.pop() * num);
                        break;
                    default:
                        stack.push(stack.pop() / num);
                }
                preSign = s.charAt(i);
                num = 0;
            }
        }
        int ans = 0;
        while (!stack.isEmpty()) {
            ans += stack.pop();
        }
        return ans;
    }
}