栈

栈是一种特殊的线性表,只能在一端操作

往栈中添加元素的操作，一般叫做push，入栈

从栈中移除元素的操作，一般叫做pop，出栈（只能移除栈顶元素，也叫做弹出栈顶元素）

后进先出的原则，Last In First Out, LIFO

练习题

20. 有效的括号

给定一个只包括 ‘('，')'，'{'，'}'，'['，']’ 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。

示例 1:

输入: “()” 输出: true

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/valid-parentheses 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

这道题使用栈数据结构。

1，左括号时，入栈，

2，右括号时，如果栈顶是与其对应的左括号， 则出栈。如果不对应，则返回false。

3，最终返回结果是栈是否为空

代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

private static HashMap<Character,Character> map = new HashMap<>();
    static {
        map.put('(',')');
        map.put('[',']');
        map.put('{','}');
    }
    public boolean isValid(String s) {
        Stack stack = new Stack();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)){
                stack.push(c);
            }else {
                if (stack.isEmpty() || map.get(stack.peek()) != c) return false;
                stack.pop();
            }
        }
        return stack.isEmpty();
    }