CPU缓存对数组友好而对链表不友好

原因:CPU读取内存的时候，会把一片连续的内存块读取出来，然后放到缓存中。数组简单易用，在实现上使用的是连续的内存空间，可以借助CPU的缓存机制，预读数组中的数据，所以访问效率越高。而链表在内存中并不是连续存储，所以对CPU缓存不友好，没有办法预读。

栈应用

检查符号是否成对出现

  1. /**
  2.  * 1、括号间的对应规则存放在 Map 中；
  3.  * 2、创建一个栈。遍历字符串，如果字符是左括号就将对应的右括号直接加入stack中，否则将stack 的栈顶元素与这个括号做比较，如果不相等就直接返回 false。遍历结束，如果stack为空，返回 true。
  4.  */
  5. public static boolean stackdemo(String s){
  6.         //创建栈
  7.         Stack<String> stack = new Stack<>();
  8.         //括号直接的对应规则
  9.         Map<Character,Character> map = new HashMap<>();
  10.         map.put('(',')');
  11.         map.put('{','}');
  12.         map.put('[',']');
  13.         //假设修正法,假设是匹配的
  14.         boolean flag = true;
  15.         //遍历字符串，拆解字符串获取字符
  16.         for (int i =0;i<s.length();i++){
  17.             //获取当前字符
  18.             char c = s.charAt(i);
  19.             //如果是左括号，把对应的右括号放入栈中
  20.             if (map.containsKey(c)){
  21.                 stack.push((map.get(c).toString()));
  22.             }
  23.             //如果是有括号,与栈顶元素进行匹配
  24.             //c==')'|c==']'|c=='}'
  25.             if (map.containsValue(c)){
  26.                 //字符串开头为右括号，则不对称
  27.                 if (stack.empty()){
  28.                     flag=false;
  29.                     break;
  30.                 }
  31.                 //弹出栈顶元素，看是否对称
  32.                 String pop = stack.pop();
  33.                 if (pop.charAt(0)!=c){
  34.                     flag=false;
  35.                 }
  36.             }
  37.         }
  39.         //如果字符串最后为左括号，则不对称
  40.         if (!stack.empty()){
  41.             flag=false;
  42.         }
  44.         //返回flag
  45.         return flag;
  46.     }