[数据结构与算法]集合—List接口的使用

	ArrayList是最常用的List实现类，内部是通过数组实现的，它允许对元素进行快速随机访问。数组的缺点是每个元素之间不能有间隔，当数组大小不满足时需要增加存储能力，就要讲已经有数组的数据复制到新的存储空间中。当从ArrayList的中间位置插入或者删除元素时，需要对数组进行复制、移动、代价比较高。因此，它适合随机查找和遍历，不适合插入和删除。

/**
 * ArrayList底层是用数组实现的
 */
public class ArrayListDemo01 {
	public static void main(String[] args) {
		//实例化ArrayList
		List<String> list = new ArrayList<>();
		//添加元素,返回一个boolean值
		boolean flag = list.add("ArrayList");
		System.out.println(flag);
		boolean flag2 = list.add("collection");
		//在指定位置插入一个元素，下标不能大于当前元素个数
		list.add(1, "charuyigeshuju");
		list.add("我又加了一个元素");
		
		System.out.println(list.get(0));
		System.out.println(list.get(1));
		System.out.println(list.get(2));
		System.out.println("----------------");
		//使用循环输出，size()方法 返回元素的个数
		for(int i = 0;i<list.size();i++) {
			System.out.println(list.get(i));
		}
		System.out.println("------------------");
		//删除元素,返回被删除的元素,后面的元素位置会前移
		String value = list.remove(1);
		System.out.println(value);
		for(int i = 0;i<list.size();i++) {
			System.out.println(list.get(i));
		}
		System.out.println("--------------------");
		//删除指定元素，返回布尔值.如果给定的元素不存在，则返回false，不会报错
		boolean value2 = list.remove("ArrayList");
		System.out.println(value2);
		for(int i = 0;i<list.size();i++) {
			System.out.println(list.get(i));
		}
		System.out.println("---------------------");
		
		
		//元素替换,返回被替换的元素
		String valString = list.set(0, "替换元素");
		System.out.println(valString);
		for(int i = 0;i<list.size();i++) {
			System.out.println(list.get(i));
		}
		System.out.println("---------------------");

		//清空容器
		list.clear();
		System.out.println(list.size());
		System.out.println("---------------------");

		//判断容器是否为空返回布尔值，如果容器为空返回true，否则返回false
		list.add("我又加了一个元素，容器不为空");
		boolean val = list.isEmpty();
		System.out.println(val);
		System.out.println("---------------------");
		
		//判断容器中是否包含指定元素,如果包含返回true，否则false
		list.add("zzuli");
		boolean val2 = list.contains("zzuli");
		System.out.println(val2);
		System.out.println("---------------------");

		//查找元素的位置,返回索引位置,如果不存在返回-1
		//查找第一次出现的位置（）
		list.add("afdfiufkdj");
		list.add("zzuli");
		list.add("48565489745");
		list.add("zzuli");
		for(int i = 0;i<list.size();i++) {
			System.out.println(list.get(i));
		}
		System.out.println(list.indexOf("zzuli"));
		//查找元素最后一次出现的位置
		System.out.println(list.lastIndexOf("zzuli"));
		
		//讲一个单例集合转换为数组
		System.out.println("---------------------");
		Object[] arr = list.toArray();//转换为Object[]类型的数组，但是不能在这里进行强转
		for (int i = 0; i < arr.length; i++) {
			String string = (String)arr[i];
			System.out.println(string);
			//System.out.println(arr[i]);
		}
		System.out.println("---------------------");
		//转换泛型类型数组（将单例集合转换为指定类型的数组，但是类型需要参考泛型中的类型）
		String[] arr2 = list.toArray(new String[list.size()]);
		for (int i = 0; i < arr2.length; i++) {
			System.out.println(arr2[i]);
		}
		System.out.println("---------------------");
		
		//容器的并集操作
		List<String> a = new ArrayList<String>();
		a.add("a");
		a.add("b");
		a.add("c");
		
		List<String> b = new ArrayList<String>();
		b.add("b");
		b.add("c");
		b.add("d");
		//用a并b，并集返回布尔值,结果在a,如果b为空则返回值为false
		System.out.println(a.addAll(b));
		for(String str:a) {
			System.out.println(str);
		}
		System.out.println("---------------------");
		//容器的交集操作
		List<String> a1 = new ArrayList<String>();
		a1.add("a");
		a1.add("b");
		a1.add("c");
		
		List<String> b1 = new ArrayList<String>();
		b1.add("b");
		b1.add("c");
		b1.add("d");
		//a交b
		boolean vb = a1.retainAll(b1);
		System.out.println(vb);
		for(String str:a1) {
			System.out.println(str);
		}
		System.out.println("---------------------");
		//容器的差集的操作
		
		List<String> a2 = new ArrayList<String>();
		a2.add("a");
		a2.add("b");
		a2.add("c");
		
		List<String> b2 = new ArrayList<String>();
		b2.add("b");
		b2.add("c");
		b2.add("d");
		
		boolean vb2 = a2.removeAll(b2);
		System.out.println(val2);
		for(String str:a2){
			System.out.println(str);
		}
	}
}

Vector类也是List接口的之类，它和ArrayList的区别是：Vector与ArrayList一样，也是通过数组实现的，不同的是它支持线程的同步，即某一时刻只有一个线程能够写Vector，避免多线程同时写而引起的不一致性，但实现同步需要很高的花费，因此，访问它比访问ArrayList慢。

public class VectorDemo {
	public static void main(String[] args) {
		
		List<String> v =new Vector<>();
		v.add("a");
		v.add("b");
		v.add("c");
		for(String str : v) {
			System.out.println(str);
		}
	}
}

stack([st?k] )堆栈是一种容器适配器，专门设计用于在LIFO（last-in first-out）环境（后进先出）中操作，在该环境中，仅从容器的一端插入和提取元素。
堆栈被实现为容器适配器，它们是使用特定容器类的封装对象作为其基础容器的类，提供了一组特定的成员函数来访问其元素。 元素从特定容器的“后部”被推入/弹出，这被称为堆栈的顶部。

public class StackDemo {
	public static void main(String[] args) {
		//实例化栈容器
		Stack<String> stack = new Stack<String>();
		//将元素添加到栈容器中
		stack.push("a");
		stack.push("b");
		stack.push("c");
		//查看栈顶元素，不取出
		System.out.println("-----查看栈顶元素-----");
		System.out.println(stack.peek());
		//返回元素在栈容器中的位置，从栈顶开始数，所以a先进为3
		System.out.println("-----查看元素在栈容器的位置-----");
		System.out.println(stack.search("a"));
		//获取栈容器的元素,从栈顶开始取，c,b,a
		System.out.println("-----获取栈容器的元素-----");
		String p1 = stack.pop();
		System.out.println(p1);
		String p2 = stack.pop();
		System.out.println(p2);
		String p3 = stack.pop();
		System.out.println(p3);
		//判断容器是否为空,空为true，否则为false
		System.out.println("-----判断栈容器是否为空-----");
		System.out.println(stack.empty());
		//
		System.out.println("------案列--------");
		StackDemo stackDemo = new StackDemo();
		stackDemo.symmentry();

	}
	
	//匹配对称性
	public void symmentry() {
		String string = "...{...[...(...)...]...}.[..";
		Stack<String> stack = new Stack<String>();
		//假设修正
		boolean flag = true;
		//拆分字符串取字符
		for (int i = 0; i < string.length(); i++) {
			char c = string.charAt(i);
			if(c == '{') {
				stack.push("}");
			}
			if(c == '[') {
				stack.push("]");
			}
			if(c == '(') {
				stack.push(")");
			}
			//判断符号是否匹配
			if(c == '}' || c == ']' || c == ')') {
				if(stack.empty()) {
					flag = false;
					break;
				}
				String xString = stack.pop();
				if( xString.charAt(0) != c) {
					flag = false;
					break;
				}			
			}		
		}
		if(!stack.empty()) {
			flag = false;
		}
		System.out.println(flag);
	}
}

LinkedList是用链表结构存储数据的，很适合数据的动态插入和删除，随机访问和遍历速度比较慢。另外，他还提供了List接口中没有定义的方法（非List标准），专门用于操作表头和表尾元素，可以当作堆栈、队列和双向队列使用。

/**
 * LinkedList底层是双向链表
 * @author 64120
 *
 */
public class LinkedListDemo {
	public static void main(String[] args) {
		List<String> linList = new LinkedList<String>();
		linList.add("a");
		linList.add("b");
		linList.add("c");
		linList.add("d");
		for(String string:linList) {
			System.out.println(string);
		}
		//其他方法和ArrayList相同
		System.out.println("------非List标准--------");
		//非List标准
		//只能用LinkedList，因为不是List接口中的方法
		LinkedList<String> linkedList = new LinkedList<String>();
		linkedList.addFirst("a");
		linkedList.addFirst("b");;
		linkedList.addFirst("c");
		for(String string:linkedList) {
			System.out.println(string);
		}
		System.out.println("-------添加到栈尾----------");
		LinkedList<String> linkedList1 = new LinkedList<String>();
		linkedList1.addLast("a");
		linkedList1.addLast("b");;
		linkedList1.addLast("c");
		for(String string:linkedList1) {
			System.out.println(string);
		}
		System.out.println("--------获取栈头、栈尾----------");
		System.out.println(linkedList1.getFirst());
		System.out.println(linkedList1.getLast());
		System.out.println("---------移除栈头、栈尾-------");
		System.out.println(linkedList1.removeFirst());
		System.out.println(linkedList1.removeLast());
		for(String string:linkedList1) {
			System.out.println(string);
		}
		System.out.println("-------出栈----------");
		linkedList1.addLast("e");
		//栈头出栈
		linkedList1.pop();
		for(String string:linkedList1) {
			System.out.println(string);
		}
		System.out.println("--------入栈----------");
		linkedList1.push("h");
		for(String string:linkedList1) {
			System.out.println(string);
		}
		System.out.println(linkedList1.isEmpty());
	}
}