java中的集合框架基础-2

一.泛型的基础编程
        类型的在编写代码时不确定---引入类型参数
        在类上使用泛型
        泛型个数没有约束，一般使用全大写的单个字母表示，不同泛型使用逗号分割

 泛型类的用法
        class 类型名称<泛型名称>{   形参
            泛型名称  属性名称;
          public 泛型名称 pp1(){}
          public 泛型名称 pp2(泛型名称 bb){}
          public void pp3(泛型名称 bb1, 其他类型参数){}
  }

  注意：不能在静态方法中使用泛型
         public static void bb(T id){}语法报错
         正确的写法为public static void bb(T id){}
         使用静态方法的泛型时和类上的泛型无关
 泛型方法的用法
 泛型实例方法
       public int pp1(TA num){}
 泛型静态方法
        public static TB pp2(TB bb){}
 泛型上限 extends
             泛型上限中所使用的类只能有一个，接口无数多个
         public class A {} 
通配符 ?
 ``上限通配符，用来限制类型的上限
        public void pp(List list){}//表示list中元素的类型必须是
T类型或者T类型的子类或者T接口的实现类
 ``下限通配符，用来限制类型的下限
         public void pp(List list){}//表示list中元素的类型必须是T类
 型或者T类父类或者T接口的实现类或者T的父接口实现类

二.两个特殊的数据结构
   栈Stack：FILO
            定义栈
              对栈的基本操作只有push进栈和pop出栈两种，栈的实现可以有数组实现的顺序栈和链表结构的链式栈
        java提供的具体实现类Stack
            public class Stack extends Vector 
                E push(E item)  将数据存储到数组中，如果集合已经满了，则添加新数据时增容
                E pop() 弹出栈顶数据
                E peek() 查看栈顶数据，并不会执行弹出操作
             search(Object o) 查找o对象的下标值
          1、定义接口

public interface Stack {
			   //栈是否为空  记得在方法上添加注释
			   boolean isEmpty();
			   // data元素入栈
			   void push(T data);
			   //返回栈顶元素,未出栈
			   T peek();
			   //出栈,返回栈顶元素,同时从栈中移除该元素
			   T pop();
			}

           2、实现类，这里忽略了抽象类
            //顺序栈

public class SeqStack implements Stack {
				// 栈顶指针,-1代表空栈
				private int top = -1;
				// 容量大小默认为10
				private static final int capacity = 10;
				// 存放元素的数组
				private T[] array;
				//当前栈中存储的元素个数
				private int size;
			
				public SeqStack() {
					this(capacity);
				}
			
				@SuppressWarnings("unchecked")
				public SeqStack(int capacity) {
					array = (T[]) new Object[capacity];
				}
			
				public int size() {
					return size;
				}
			
				public boolean isEmpty() {
					return this.top == -1;
				}
			
				// 添加元素,从栈顶(数组尾部)插入
				public void push(T data) {
					// 判断容量是否充足
					if (array.length == size)
						ensureCapacity(size * 2 + 1);// 扩容
					// 从栈顶添加元素
					array[++top] = data;
					size++;
				}
			
				private void ensureCapacity(int capacity) {
					// 如果需要拓展的容量比现在数组的容量还小,则无需扩容
					if (capacity < size)
						return;
					T[] old = array;
					array = (T[]) new Object[capacity];
					System.arraycopy(old, 0, array, 0, size);
				}

                // 获取栈顶元素的值,不删除
          

public T peek() {
					if (isEmpty())
						throw new EmptyStackException();
					return array[top];
				}

   // 从栈顶(顺序表尾部)删除

public T pop() {
					if (isEmpty())
						throw new EmptyStackException();
					size--;
					return array[top--];
				}
			}

    队列Queue：FIFO
        根据实现方式不同分为顺序队列和链式队列。
            enqueue(String item) 入队操作
            dequeue() 出队操作
           
            循环队列：基于数组的队列实现中，当tail=items.length时需要搬移大量的数据，就会导致
            入队操作的性能降低，可以使用循环队列解决
            
            典型算法：约瑟夫环
     
            队列接口 Queue

public interface Queue extends Collection {
    			boolean add(E e);向队列中添加数据，阈值为64，Double size if small; else grow by 50%
    			boolean offer(E e);
    			E remove();  删除队列头部的数据
    			E poll();
    			E element();获取队列中的数据
    			E peek();
			}

        Deque 双向队列
            ### 优先队列
            
            PriorityQueue是AbstractQueue的实现类，优先级队列的元素根据自然排序或者在构造函数时期提供
            Comparator来排序，具体根据构造器判断。PriorityQueue不允许null元素
            
            - 队列的头在某种意义上是指定顺序的最后一个元素。队列查找操作poll、remove、peek和element访
            问队列头部元素
            
            - 优先级队列是无限制的，但是具有内部capacity，用于控制在队列中存储元素的数组大小
            
        - 该类以及迭代器实现了Collection、Iterator接口的所有可选方法，这个迭代器提供了iterator()方法不能保证以任何特定顺序遍历优先级队列的元素。

如果需要有序遍历使Arrays.sort(queue.toArray())
        
        - 注意这个实现不是线程安全的，多线程不应该并发访问PriorityQueue实例，如果有某个线程修改了队列的话，使用线程安全的类PriorityBlockingQueue
        
        PriorityQueue是优先队列，作用是保证每次取出的元素都是队列中权值最小的，这里涉及到了大小关系，元素大小的评判可以通过元素自身的自然顺序（使用默认的比较器），也可以通过构造时传入的比较器。
        Java中PriorityQueue实现了Queue接口，不允许放入null元素；其通过堆实现，具体说是通过完全二叉树complete 
        binary tree）实现的小顶堆（任意一个非叶子节点的权值，都不大于其左右子节点的权值），也就意味着可以
        通过数组来作为PriorityQueue的底层实现。
        
阻塞队列就是在队列的基础上添加了阻塞特性。在队列为空时，从队头获取数据会被阻塞，直到队列中有数据才返回；在队列已满时，插入数据的操作会被阻塞，直到队列中空闲位置后才插入数据，然后返回。基于阻塞队列的生产者-消费者模式可以有效地协调生产和消费的速度。

#### BlockingQueue接口

方法    抛出异常    返回特殊值    一直阻塞    超时退出
插入    add(e)    offer(e)    put(e)    offer(e, tiime, unit)
移除    remove()    poll()    take()    poll(tiime, unit)
查看    element()    peek()

java针对阻塞队列提供了7种常见的实现，分别是
    ArrayBlockingQueue由数组结构组成的有界阻塞队列、
    LinkedBlockingQueue由链表结构组成的有界阻塞队列，默认长度为Integer.MAX_VALUE，如果指定长度则有上限、
    PriorityBlockingQueue支持优先级排序的无界阻塞队列、
    DelayQueue使用优先级队列实现的无界阻塞队列、
    SynchronousQueue不存储元素的阻塞队列,只起到一个同步器的作用、
    LinkedTransferQueue由链表结构组成的无界阻塞队列、
    LinkedBlockingDeque由链表结构组成的双向阻塞队列。