栈-常见考察面试算法题

栈，数据存储受限的线性表——插入和删除的操作只允许在一端进行。

栈的基本特征&操作

允许操作的一端称为栈顶（top），不可操作的一端称为栈底（bottom）；插入元素——入栈（push），删除元素称为出栈（pop）。

基于数组实现栈

PS：top有的地方指向栈顶元素，有的时候指向再往上的一个空单位。

基于链表实现栈

括号匹配问题

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。

2. 左括号必须以正确的顺序闭合。

PS：用哈希表将所有符号先存储，左半边做key,右半边做value。遍历字符串的时候，遇到左半边符号就入栈，遇到右半边符号就与栈顶的符号比较，不匹配就返回false。

boolean isValid(String s) {
    if(s.length()<=1){
        return false;
    }
    Map<Character,Character> smap = new HashMap<>();
    smap.put('(',')');
    smap.put('{','}');
    smap.put('[',']');
    
    Stack<Character> stack = new Stack<>();
    
    for(int i=0;i<s.length();i++){
        char item = s.charAt(i);
        if(smap.containsKey(item)){
            stack.push(item);
        }else{
            if(!stack.isEmpty()){
                Character left = stack.pop();
                char rightchar = smap.get(left);
                if(rightchar != item){
                    return false;
                }
            }else {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

MinStack() 初始化堆栈对象。

void push(int val) 将元素val推入堆栈。

void pop() 删除堆栈顶部的元素。

int top() 获取堆栈顶部的元素。

int getMin() 获取堆栈中的最小元素。

最大栈

设计一个最大栈数据结构，既支持栈操作，又支持查找栈中最大元素。

计算器问题

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

逆波兰表达式

根据 逆波兰表示法，求表达式的值。说明：

1. 有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

2. 注意 两个整数之间的除法只保留整数部分。

3. 可以保证给定的逆波兰表达式总是有效的。也即表达式总会得出有效数值且不存在除数为 0 的情况。

前缀表达式的运算符位于两个相应操作数之前，前缀表达式又被称为前缀记法或波兰式。而后缀式就是逆波兰式，知道这些就行了。

观察后缀表达式可以发现，其特点就是数字先保存下来，然后遇到符号就计算，例如”1 2 3 +“，遇到 +号就将2+3加起来变成5再继续其他操作，直到最后完成。

如果用栈来解释就是遇见数字即进栈，遇见运算符，则取出栈中最上面的两个元素进行计算，最后将运算结果入栈。

public int evalRPN(String[] tokens) {
    Stack<Integer> stack = new Stack<>();
    for(String token : tokens){
        if(!Character.isDigit(token.charAt(0)) && token.length() == 1){
            /**
                 * 运算符，从栈中取出两个数进行运算！
                 */
            int b = stack.pop();
            int a = stack.pop();
            switch (token){
                    /**
                     * 根据运算符的种类进行计算
                     * 将结果直接入栈！
                     */
                case "+":stack.push(a + b);break;
                case "-":stack.push(a - b);break;
                case "*":stack.push(a * b);break;
                case "/":stack.push(a / b);break;
            }
        }else {
            /**
                 * 整数直接入栈！
                 */
            stack.push(Integer.parseInt(token));
        }
    }
    return stack.pop();
}