跬步

Stack

• Java中的Stack是Vector的一个子类。
• 与队列不同的是，Stack是FILO，先进后出。
  
• 添加元素方法使用push()，添加到栈顶。
• 移除栈顶对象的方法pop(),并返回该对象。
• search()方法可以在栈中查找元素。

一个例子

leetcode 20. 有效的括号

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

有效字符串需满足：

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

示例 1:

输入: "()"
输出: true

示例 2:

输入: "()[]{}"
输出: true

示例 3:

输入: "(]"
输出: false

示例 4:

输入: "([)]"
输出: false

示例 5:

输入: "{[]}"
输出: true

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses

解题思路

遍历输入的字符串，如果遇到左括号则push()到栈中，遇到右括号则pop()取出栈顶的值，判断是否于此括号匹配。循环完毕判断栈是否为空栈。

public boolean isValid(String s) {
        Stack<Character> stack = new Stack();
        for (Character a:s.toCharArray()) {
            if (a == '(' || a == '{' || a == '[') {
                stack.push(a);
            }else {
                if (stack.isEmpty()){
                    return false;
                }
                switch (a){
                    case ')':
                        if (stack.pop() != '('){
                            return false;
                        }
                        break;
                    case '}':
                        if (stack.pop() != '{'){
                            return false;
                        }
                        break;
                    case ']':
                        if (stack.pop() != '['){
                            return false;
                        }
                        break;
                        default:
                }
            }
        }
        if (stack.isEmpty()){
            return true;
        }
        return false;
    }