数据结构-栈_栈是一种存取什么数据结构

栈

  栈是一种简单的数据结构。是一种先进后出的结构，类似于羽毛球桶里存放羽毛球，先放进去的羽毛球只能最后才能取出来。栈是一种线性数据结构，我们可以使用数组、链表等实现栈。利用栈的先进后出的特性可以实现很多功能。例如：文本中的括号匹配校验；浏览器访问记录的回退等功能。

括号的匹配校验

class Solution {
    public boolean isValid(String s) {
        if(s==null||s.length()<2){
            return false;
        }
        Stack<Character> stack = new Stack<>();
        Map<Character,Character> map = new HashMap(3);
        map.put(')','(');
        map.put(']','[');
        map.put('}','{');
        for(int i=0;i<s.length();i++){
            char ch = s.charAt(i);
            if(ch-'('==0||ch-'{'==0||ch-'['==0){
                stack.push(ch);
            }else if(ch-')'==0||ch-'}'==0||ch-']'==0){
                if(stack.isEmpty()){
                    return false;
                }
                char c = stack.pop();
                if(map.get(ch)-c!=0){
                    return false;
                }
            }
        }
        if(!stack.isEmpty()){
            return false;
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30