一、Java集合中实现队列Queue的两种形式
- ArrayDeque:基于数组实现的队列
- LinkedList:基于链表实现的队列
二、ArrayDeque的使用及实现
- ArrayDeque是一个双端队列，即它可以在两端插入或删除，也普通的队列有所区别
1.ArrayDeque与其他集合接口的关系
2.ArrayQueue的使用及实现解读
(1)属性
- elements : 存放元素的对象数组
- head : 存放队列首元素的索引(未必是指向数组elements索引为0的元素，因为默认还有其他空的数组项)
- tail : 存放队列尾元素的索引
(2)实例化方法
I.用法说明
- new ArrayDeque(); //不指定初始化容量，按默认容量
- new ArrayDeque(int elementCount); //指定初始化容量大小
Queue<String> defaultQueue = new ArrayDeque<String>();Queue<String> queue = new ArrayDeque<String>(5);
II.实现化方法实现原理解读：
public ArrayDeque() {//默认有16个元素的数组空间elements = new Object[16];}public ArrayDeque(int numElements) {/*---------------------------------------------------------------//计算数组的申请的空间大小private static int calculateSize(int numElements) {//初始化容量默认为8int initialCapacity = MIN_INITIAL_CAPACITY;//如果指定的初始化容量大于等于默认的空间大小，则重新计算初始化空间大小if (numElements >= initialCapacity) {initialCapacity = numElements;initialCapacity |= (initialCapacity >>> 1);initialCapacity |= (initialCapacity >>> 2);initialCapacity |= (initialCapacity >>> 4);initialCapacity |= (initialCapacity >>> 8);initialCapacity |= (initialCapacity >>> 16);initialCapacity++;//如果容量超过int的最大值(溢出)，则将初始化容量设置为2^30if (initialCapacity < 0)initialCapacity >>>= 1;}return initialCapacity;}private void allocateElements(int numElements) {//根所指定初始化容量来初始化数组来存储元素(默认最小为8)elements = new Object[calculateSize(numElements)];}----------------------------------------------------------------*/allocateElements(numElements);}
初始化后，用于存储队列节点的数组如下图：
- 初始化后，队列的头和尾都指向数组的索引为0的元素
- 数组长度为计算出来的长度(指定容量时，根据容量计算 (最小为8));如果未指定，默认为16
(3)从末尾添加元素add
I.add方法的使用
- add(E e):向队列末尾添加一个元素
Queue<String> queue = new ArrayDeque<String>(5);queue.add("A");queue.add("B");queue.add("C");System.out.println(queue); //[A, B, C]
II.add方法的实现解读
public boolean add(E e) {//调用addLast在队列末尾添加元素，addLast的实现在后面有详细讲解addLast(e);return true;}
III.功能相同的方法：
- offer(E e)
- offerLast(E e)
(4)从队列末尾添加元素addLast
I.addLast方法的使用
- addLast(E e):向队列末尾添加一个元素
ArrayDeque<String> queue = new ArrayDeque<String>(5);queue.add("A");queue.add("B");queue.add("C");queue.addLast("D");queue.addLast("E");System.out.println(queue); //[A, B, C, D, E]
II.addLast方法的实现解读
public void addLast(E e) {//1.元素值非空判断if (e == null)throw new NullPointerException();//2.将元素添加到数组的末尾elements[tail] = e;//3.如果队列已满，则扩容/*下面这个判断，可以分成以下几个部分(1)整个括号是一个boolean表达式，判断内括号中的内容是否与head相等(2)内括号中又分为以下几个部分:(&的优先级比=高)(2.1)(tail +1) & (elements.length - 1)(2.2)tail = 上面的表达式(2.1)的结果*/if ( (tail = (tail + 1) & (elements.length - 1)) == head)/*--------------------------------------------------private void doubleCapacity() {//1.判断是队列否已满(由上一步的赋值操作)// assert断言后面跟一个boolean的表达式// (1)如果结果为true,继续执行// (2)如果结果为false,则抛出AssertionError，程序停止执行//assert head == tail;//p指向原队列头的位置int p = head;int n = elements.length; //原队列的长度int r = n - p; // p元素右侧元素的个数int newCapacity = n << 1; //队列的新容量为原容量的2倍if (newCapacity < 0) //出现小于0的情况是newCapacity超过int的最大值，溢出了throw new IllegalStateException("Sorry, deque too big");//新对象数组用来存储队列Object[] a = new Object[newCapacity];//通过复制方式来扩容System.arraycopy(elements, p, a, 0, r);System.arraycopy(elements, 0, a, r, p);//重新指向elements = a;head = 0;tail = n;}--------------------------------------------------*/doubleCapacity();}
注：
- 从队列尾部添加，只需要一直移动队列的末尾指针(队列尾部指针一直往后移动，因为这里实现的双端队列，所以，当队列队尾在数组的最后一位时，队列的队尾再往后移动一位，就到了数组的第0个位置)即可，如下图：
(5)从队列头部插入元素
I.addFirst方法的使用
- addFirst(E e):在队列头部插入元素
ArrayDeque<String> queue = new ArrayDeque<String>(5);queue.add("A");queue.add("B");queue.add("C");queue.addLast("D");queue.addLast("E");System.out.println(queue); //[A, B, C, D, E]queue.addFirst("S");System.out.println(queue); //[S, A, B, C, D, E]queue.addFirst("S＋");System.out.println(queue); //[S＋, S, A, B, C, D, E]
II.addFirst方法的实现解读
public void addFirst(E e) {//插入的元素必须是非nullif (e == null)throw new NullPointerException();//将队列的头部元素设置为新添加的元素elements[head = (head - 1) & (elements.length - 1)] = e;/*上面的操作可以分为3步：(1)获取 (head - 1) & (elements.length -1)计算的值(2)重新设置head的值，将第一步计算出来的值赋值给head(head向前移动)(3)设置数据elements中索引为第１步的值为e*///如果队列已满，则扩容if (head == tail)doubleCapacity();}
- 从队列头部插入元素时，原队列头部一直向前移动(如果队列已经在数组的第0个位置，因为是双端队列，那么它再向前就是数组的最后一个元素的位置)
- 队列元素已经存满的３种情况：
- (1):头部一直没移动(在数组的第一个位置)，一直在从队尾添加元素，即队尾一直往后移动，当队尾移动到数组的第后一位，再次移动，队尾就移动到数组的第一个位置，此时，队头和队尾重合了
- (2):队尾一直没移动(在数组的第一个位置)，一直在队头添加元素，即队头一直往前移动(默认在数组第一个位置，往前就会移动到数组的第后一个位置)，当队头从数组的第后的一个位置一直向前移动，移动到数组的第一个元素的位置时，此时队头和队尾再次重合了，所有空间都占满了
- (3):队头和队尾都在移动，队头往前移动，队尾往后移动，当队头和队尾再次重合，那么此时所有空间也被占满了
(6)获取第一个元素getFirst
- getFirst():获取队列中的第一个元素(队头)，通过队头指针head来获取
(7)获取最后一个元素getLast
- getLast():获取队列中的第后一个元素(队尾)，通过队尾指针tail来获取
(8)压入队列方法push
- push(E e):从队列头部插入元素(通过调用addFirst方法实现)
(9)出列方法pop
- pop():删除队列中的第一个元素(通过removeFirst方法实现)
(10)删除队列方法remove和removeFirst
I.removeFirst的使用
- remove和removeFirst都是删除队列中第一个元素(remove也是通过removeFirst来实现的)
ArrayDeque<String> queue = new ArrayDeque<String>(5);queue.add("A");queue.add("B");queue.add("C");queue.addLast("D");queue.addLast("E");System.out.println(queue); //[A, B, C, D, E]*/String removeElement = queue.remove();System.out.println(removeElement); //ASystem.out.println(queue); //[B, C, D, E]
II.removeFirst的实现解读
public E removeFirst() {/*-------------------------------------------------------public E pollFirst() {int h = head;//1.从数组中通过头部索引获取头部元素值E result = (E) elements[h];//2.如果头部元素值为null，直接返回if (result == null)return null;//3.将原头部元素指向的位置的值清空elements[h] = null;//4.头部向后移动(原头部后面的元素成为新的头部)head = (h + 1) & (elements.length - 1);//5.返回删除的元素值return result;}--------------------------------------------------------*/E x = pollFirst();if (x == null)throw new NoSuchElementException();return x;}
(11)获取队列中的头部和底部值(只获取，不删除)peek,peekFirst和peekLast
- peek():获取队列的第一个元素，通过head指针来获取
- peekFirst():获取队列中的第一个元素，与peek是相同的功能
- peekLast():获取队列中的最后一个元素，通过tail指针来获取
(12)获取队列的长度size
I.size方法的使用
- size():获取队列的长度
ArrayDeque<String> queue = new ArrayDeque<String>(5);queue.add("A");queue.add("B");queue.add("C");System.out.println(queue.size()); //队列的长度为3
II.size方法的实现解读
public int size() {/** tail和head的位置关系有3种：* (1)tail在head的左侧* (2)tail在head的右侧* (3)head和tail重合*/return (tail - head) & (elements.length - 1);}
(13)将队列转化为数组toArray
I.toArray方法的使用
- toArray():返回将队列转换为的对象数组
- toArray(T[] a):将数组转化为指定的泛型数组
ArrayDeque<String> queue = new ArrayDeque<String>(5);queue.add("A");queue.add("B");queue.add("C");queue.addLast("D");queue.addLast("E");Object[] queueArr = queue.toArray();System.out.print("[");for (int i = 0; i< queueArr.length; i++) {System.out.print(queueArr[i]+",");}System.out.print("]"); //[A,B,C,D,E,]String[] qArr = new String[queue.size()];queue.toArray(qArr);System.out.print("[");for (int i = 0; i< qArr.length; i++) {System.out.print(qArr[i]+",");}System.out.print("]"); //[A,B,C,D,E,]
II.toArray方法的实现解读
public Object[] toArray() {/*---------------------------------------------------------------private <T> T[] copyElements(T[] a) {//头部在底部的左边，只能一直是从尾部添加元素，头部没动，那么从head开始到tail这一段都是队列中的元素if (head < tail) {System.arraycopy(elements, head, a, 0, size());} else if (head > tail) {int headPortionLen = elements.length - head;//从头部开始到数组结尾这一段System.arraycopy(elements, head, a, 0, headPortionLen);//从数组第一个元素开始到尾部这一段System.arraycopy(elements, 0, a, headPortionLen, tail);}return a;}----------------------------------------------------------------*/return copyElements(new Object[size()]);}public <T> T[] toArray(T[] a) {//队列的长度int size = size();//如果用于存储的新数组长度小于队列长度，则需要分配一个更大的空间给这个数组if (a.length < size)a = (T[])java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size);//复制元素copyElements(a);if (a.length > size)a[size] = null;return a;}
三、LinkedList
注：LinkedList在之前的列表章节已经讲解过了，这里不再赘述了