Queue和LinkLink的关系

转载https://blog.csdn.net/qq_33608638/article/details/79600657
https://cloud.tencent.com/developer/article/1350852

Queue接口不属于Java并发包下面的类，它是java.util下面的一个接口，虽然这个接口跟并发没有直接关系，但是它抽象和定义了在Java里面队列的通用方法，最重要的是这个类也是Java并发大神Doug Lea设计的，所以学习和了解这个接口是非常有必要的。
Queue队列接口在实现上又继承了Collection接口，而Collection接口又继承了 Iterable接口，所以继承了这两个接口的定义的方法功能，另外Queue接口拥有的直接子类如下:

AbstractQueue
ArrayBlockingQueue
ArrayDeque
ConcurrentLinkedDeque
ConcurrentLinkedQueue
DelayQueue
LinkedBlockingDeque
LinkedBlockingQueue
LinkedList
LinkedTransferQueue
PriorityBlockingQueue
PriorityQueue
SynchronousQueue

Java 队列 queue的一些操作，
    add        增加一个元索                     如果队列已满，则抛出一个IIIegaISlabEepeplian异常
　　remove   移除并返回队列头部的元素    如果队列为空，则抛出一个NoSuchElementException异常
　　element  返回队列头部的元素             如果队列为空，则抛出一个NoSuchElementException异常
　　offer       添加一个元素并返回true       如果队列已满，则返回false
　　poll         移除并返问队列头部的元素    如果队列为空，则返回null
　　peek       返回队列头部的元素             如果队列为空，则返回null
　　put         添加一个元素                      如果队列满，则阻塞
　　take        移除并返回队列头部的元素     如果队列为空，则阻塞

Queue接口中定义了几种方法

void add(Object e);　　   //将指定元素加入此队列的尾部。
Object element();　　     //获取队列头部的元素，但是不删除该元素。
boolean offer(Object e); //将指定元素加入此队列的尾部。当使用有容量限制的队列时，此方法通常比add(Object e)方法更好。
Object peek(); 　　        //获取队列头部的元素，但是不删除该元素，如果此队列为空，则返回null。
Object poll();                //获取队列头部的元素，并删除该元素，如果此队列为空，则返回null。
Object remove();　　    //获取队列头部的元素，并删除该元素

最后，关于Queue队列的设计，还有两个注意点：

（1）队列的实现通常不允许插入null值，尽管一些队列实现了，如LinkedList就没有禁止，即使LinkedList可以插入null值，但我们在实际使用的时候也不应该向队列插入null值，因为null值通常用于poll方法表示当前队列没有元素了，但如果允许插入null值，这个方法就有歧义，所以我们在使用时候应该避免在队列中插入null值。

（2）队列的实现通常不需要重写该类的equasl和hashCode方法，代替使用Object类默认的定义，因为在队列里面一样的元素可能拥有不同的排序属性。

poll：Queue(队列)的一个方法，获取并移除此队列的头，如果此队列为空，则返回null
pop：Stack(栈)的方法，移除堆栈顶部的对象，并作为此函数的值返回该对象
peek 不改变栈的值(不删除栈顶的值)，pop会把栈顶的值删除。

1.LinkedList ：（链表）这是一个多功能实现的类，

import java.util.Queue;//先进先出的辅助队列
import java.util.LinkedList;

Queue<TreeNode> queue = new LinkedList<TreeNode>();

是List接口的集合，可以根据索引值随意访问list中的元素。还实现了Deque接口（Queue的子接口，代表双向队列），Deque中也定义了一些双向操作队列的方法。还可以用作栈，因为有 pop（）和 push（）两个方法。

如果需要遍历List集合元素，对于ArrayList、Vector集合，则应该使用随机访问方法(get)来遍历集合元素，这样性能更好，对于LinkedList集合，则应该采用迭代器(Iterater)来遍历集合元素。
如果需要经常执行插入、删除操作来改变List集合大小，则应该使用LinkedList集合，而不是ArrayList。使用ArrayList、Vector集合将需要经常重新分配内存数组的大小，其时间开销往往是使用LinkedList时时间开销的几十倍，效果很差。
如果有多条线程需要同时访问List集合中的元素，可以考虑使用Vector这个同步实现

2.PriorityQueue
是标准的队列实现类（但并不标准），PriorityQueue保存队列元素的顺序并不是按加入队列的顺序，而是按队列元素的大小进行重新排序。当调用peek方法或者poll方法来取出队列中的元素时，并不是取出最先进入队列的元素，而是取出队列中最小的元素。

事实上，PriorityQueue类已经违反了队列，先入先出的基本原则。PriorityQueue不允许插入null元素，它还需要对队列元素进行排序，队列元素有两种排序方式：自然排序、定制排序；

List接口

ArrayList， LinkedList ，Vector是List接口实现的一个类。接口不可以被构造（不可实例化），但是可以为接口创建一个指向自己的对象引用。

List是继承于Collection接口，除了Collection通用的方法以外，扩展了部分只属于List的方法。
在这里插入图片描述

1.ArrayList是List接口的一个实现类，是动态数组的类，可以灵活设置数组的大小。查询快，中间插入、删除元素很慢。

import java.util.ArrayList;

ArrayList<TreeNode> List = new ArrayList<TreeNode>();

List<String> list=new ArrayList<String>();
    list.add("保护环境");     //向列表中添加数据

ArrayList<String> a;ArrayList<String> b;a.addAll(b); //将两个Array<String>合并到一个；
ArrayList<String> res  = new ArrayList<String>() ;
        HashSet<String> set = new HashSet<String>();
        {......}
        res.addAll(set);
        Collections.sort(res);

addAll（）方法用于将指定 collection 中的所有元素添加到列表。跟上面的Collections.sort(res);保持一致了

ArrayList的一些操作（类中固有定义的几种方法）

set(index，element);//会先做index检查，然后将index位置替换为element,并返回原来index出的对象。
get(index); //先做index是否越界检查，然后返回index处的对象。
remove(index); //去掉index 位置的对象，在方法中还有 后面对象前移的过程，所以说效率会打折扣

(无法确定数组大小时，才用这个，因为数组扩容会大大影响此类的效率)

每当执行Add、AddRange、Insert、InsertRange等添加元素的方法，都会检查内部数组的容量是否不够了，如果是，它就会以当前容量的两倍来重新构建一个数组，将旧元素Copy到新数组中，然后丢弃旧数组，在这个临界点的扩容操作，应该来说是比较影响效率的。

ArrayList 的初始化

执行new 关键字时，在堆内存开辟了一块空间。【常量池位于方法区，方法区位于堆内存】

构造函数的底层是Object[] 数组，该数组可以存放任何对象