Java版数据结构与算法读书笔记（一）

数据结构是数据之间相互存在的一种或多种特定关系元素的集合。 按逻辑结构来划分 集合机构 线性结构 树形结构 图形结构 物理结构 从内存和存储顺序来划分 1.顺序存储结构 2.链式存储结构

根据上面的结构，Java抽象出来对应的类

线性表（List） Java里面最基本的线性顺序结构就是数组。 对于添加和删除消耗会大一些，因为需要维护index。 Java里面典型的实现类是ArrayList。底层实现是数组。 使用Iterator迭代器删除是安全的，因为他使用了数组复制的方法。

使用链式存储结构存储线性表 底层不是数组，而是一个个node类，里面制定了元素的顺序（上一个，下一个）。 用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。 删除和插入效率高，查询效率低。双向链表LRU用的比较多。

Vector Vector继承自AbstractList。所以他也是线性的，也是用数组来实现的。线程安全版本的ArrayList。

栈（Stack） Stack继承自Vector，Vector继承自AbstractList。所以他也是线性的表，也是用数组来实现的。栈相当于对数组进行了一层封装。栈顶就是数组最后一个元素。出栈入栈其实就是对数组的操作。 有一些比较好用但是大家不熟悉关于栈的函数， search，搜索，找对应的元素，第一次出现的元素的下标，从栈顶开始搜。

栈的经典案例：波兰表达式，将标准的中缀表达式转换为计算机采用的后缀表达式，计算结果也是用的栈。 中转后的规则：数字输出，运算符进栈，括号匹配出栈，栈顶优先级高出栈。

private static String cs = "9+(3-1)*3+10/2";
	private static Stack<Character> s = new Stack<Character>();
	
	public static void main(String[] args){
		StringBuilder sb = new StringBuilder("");
		char[] n = cs.toCharArray();
	    for(int i = 0;i < n.length;i++){
	    	if(n[i] >= 0 && n[i] <= 9){
	    		sb.append(n[i]);
	    	}else if(n[i] == + || n[i] == -||n[i] == (){
		    	s.push(n[i]);
		    }else if(n[i] == )){
		    	while(s.peek()!=(){
		    		sb.append(s.peek());
		    		s.pop();
		    	}
		    	s.pop();
		    }else if(n[i] == * || n[i] == /){
		    	if(s.peek() == + || s.peek() == -){
		    		sb.append(n[i+1]);
		    		sb.append(n[i]);
		    		sb.append(s.peek());
		    		s.pop();
		    		i = i +1;
		    	}
		    }
	    	
	    }
	    
	    while(!s.isEmpty()){
	    	sb.append(s.peek());
	    	s.pop();
	    }
		System.out.println(sb.toString());
	}