Java数据结构之队列Queue的使用及实现原理解读

一、Java集合中实现队列Queue的两种形式

  • ArrayDeque:基于数组实现的队列
  • LinkedList:基于链表实现的队列

二、ArrayDeque的使用及实现

  • ArrayDeque是一个双端队列,即它可以在两端插入或删除,也普通的队列有所区别
1.ArrayDeque与其他集合接口的关系

ArraDequeue与其他结构的关系

2.ArrayQueue的使用及实现解读
(1)属性
  • elements : 存放元素的对象数组
  • head : 存放队列首元素的索引(未必是指向数组elements索引为0的元素,因为默认还有其他空的数组项)
  • tail : 存放队列尾元素的索引
(2)实例化方法

I.用法说明

  • new ArrayDeque();          //不指定初始化容量,按默认容量
  • new ArrayDeque(int elementCount); //指定初始化容量大小
  1. Queue<String> defaultQueue = new ArrayDeque<String>();
  2. Queue<String> queue = new ArrayDeque<String>(5);

II.实现化方法实现原理解读:

  1. public ArrayDeque() {
  2. //默认有16个元素的数组空间
  3. elements = new Object[16];
  4. }
  5. public ArrayDeque(int numElements) {
  6. /*---------------------------------------------------------------
  7. //计算数组的申请的空间大小
  8. private static int calculateSize(int numElements) {
  9. //初始化容量默认为8
  10. int initialCapacity = MIN_INITIAL_CAPACITY;
  11. //如果指定的初始化容量大于等于默认的空间大小,则重新计算初始化空间大小
  12. if (numElements >= initialCapacity) {
  13. initialCapacity = numElements;
  14. initialCapacity |= (initialCapacity >>> 1);
  15. initialCapacity |= (initialCapacity >>> 2);
  16. initialCapacity |= (initialCapacity >>> 4);
  17. initialCapacity |= (initialCapacity >>> 8);
  18. initialCapacity |= (initialCapacity >>> 16);
  19. initialCapacity++;
  20. //如果容量超过int的最大值(溢出),则将初始化容量设置为2^30
  21. if (initialCapacity < 0)
  22. initialCapacity >>>= 1;
  23. }
  24. return initialCapacity;
  25. }
  26. private void allocateElements(int numElements) {
  27.    //根所指定初始化容量来初始化数组来存储元素(默认最小为8) 
  28. elements = new Object[calculateSize(numElements)];
  29. }
  30. ----------------------------------------------------------------*/
  31. allocateElements(numElements);
  32. }

初始化后,用于存储队列节点的数组如下图:

队列初始化的数组情况

  • 初始化后,队列的头和尾都指向数组的索引为0的元素
  • 数组长度为计算出来的长度(指定容量时,根据容量计算 (最小为8));如果未指定,默认为16
(3)从末尾添加元素add

I.add方法的使用

  • add(E e):向队列末尾添加一个元素
  1. Queue<String> queue = new ArrayDeque<String>(5);
  2. queue.add("A");
  3. queue.add("B");
  4. queue.add("C");
  5. System.out.println(queue); //[A, B, C]

II.add方法的实现解读

  1. public boolean add(E e) {
  2. //调用addLast在队列末尾添加元素,addLast的实现在后面有详细讲解
  3. addLast(e);
  4. return true;
  5. }

III.功能相同的方法

  • offer(E e)
  • offerLast(E e)
(4)从队列末尾添加元素addLast

I.addLast方法的使用

  • addLast(E e):向队列末尾添加一个元素
  1. ArrayDeque<String> queue = new ArrayDeque<String>(5);
  2. queue.add("A");
  3. queue.add("B");
  4. queue.add("C");
  5. queue.addLast("D");
  6. queue.addLast("E");
  7. System.out.println(queue); //[A, B, C, D, E]

II.addLast方法的实现解读

  1. public void addLast(E e) {
  2. //1.元素值非空判断
  3. if (e == null)
  4. throw new NullPointerException();
  5. //2.将元素添加到数组的末尾
  6. elements[tail] = e;
  7. //3.如果队列已满,则扩容
  8. /*
  9.    下面这个判断,可以分成以下几个部分
  10.    (1)整个括号是一个boolean表达式,判断内括号中的内容是否与head相等
  11.    (2)内括号中又分为以下几个部分:(&的优先级比=高)
  12. (2.1)(tail +1) & (elements.length - 1)
  13. (2.2)tail = 上面的表达式(2.1)的结果 
  14. */
  15. if ( (tail = (tail + 1) & (elements.length - 1)) == head)
  16. /*--------------------------------------------------
  17. private void doubleCapacity() {
  18. //1.判断是队列否已满(由上一步的赋值操作)
  19. // assert断言后面跟一个boolean的表达式
  20. // (1)如果结果为true,继续执行
  21. // (2)如果结果为false,则抛出AssertionError,程序停止执行
  22. //
  23. assert head == tail;
  24. //p指向原队列头的位置
  25. int p = head;
  26. int n = elements.length; //原队列的长度
  27. int r = n - p; // p元素右侧元素的个数
  28. int newCapacity = n << 1; //队列的新容量为原容量的2倍
  29. if (newCapacity < 0)   //出现小于0的情况是newCapacity超过int的最大值,溢出了
  30. throw new IllegalStateException("Sorry, deque too big");
  31.        //新对象数组用来存储队列 
  32. Object[] a = new Object[newCapacity];
  33. //通过复制方式来扩容
  34. System.arraycopy(elements, p, a, 0, r);
  35. System.arraycopy(elements, 0, a, r, p);
  36. //重新指向
  37. elements = a;
  38. head = 0;
  39. tail = n;
  40. }
  41. --------------------------------------------------*/
  42. doubleCapacity();
  43. }

注:

  • 从队列尾部添加,只需要一直移动队列的末尾指针(队列尾部指针一直往后移动,因为这里实现的双端队列,所以,当队列队尾在数组的最后一位时,队列的队尾再往后移动一位,就到了数组的第0个位置)即可,如下图:

从队列末尾插入元素

(5)从队列头部插入元素

I.addFirst方法的使用

  • addFirst(E e):在队列头部插入元素
  1. ArrayDeque<String> queue = new ArrayDeque<String>(5);
  2. queue.add("A");
  3. queue.add("B");
  4. queue.add("C");
  5. queue.addLast("D");
  6. queue.addLast("E");
  7. System.out.println(queue); //[A, B, C, D, E]
  8. queue.addFirst("S");
  9. System.out.println(queue); //[S, A, B, C, D, E]
  10. queue.addFirst("S+");
  11. System.out.println(queue); //[S+, S, A, B, C, D, E]

II.addFirst方法的实现解读

  1. public void addFirst(E e) {
  2. //插入的元素必须是非null
  3. if (e == null)
  4. throw new NullPointerException();
  5. //将队列的头部元素设置为新添加的元素
  6. elements[head = (head - 1) & (elements.length - 1)] = e;
  7. /*
  8. 上面的操作可以分为3步:
  9. (1)获取 (head - 1) & (elements.length -1)计算的值
  10. (2)重新设置head的值,将第一步计算出来的值赋值给head(head向前移动)
  11. (3)设置数据elements中索引为第1步的值为e
  12. */
  13. //如果队列已满,则扩容
  14. if (head == tail)
  15. doubleCapacity();
  16. }
  • 从队列头部插入元素时,原队列头部一直向前移动(如果队列已经在数组的第0个位置,因为是双端队列,那么它再向前就是数组的最后一个元素的位置)

从队列头部插入元素

  • 队列元素已经存满的3种情况:
    • (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来实现的)
  1. ArrayDeque<String> queue = new ArrayDeque<String>(5);
  2. queue.add("A");
  3. queue.add("B");
  4. queue.add("C");
  5. queue.addLast("D");
  6. queue.addLast("E");
  7. System.out.println(queue); //[A, B, C, D, E]*/
  8. String removeElement = queue.remove();
  9. System.out.println(removeElement); //A
  10. System.out.println(queue); //[B, C, D, E]

II.removeFirst的实现解读

  1. public E removeFirst() {
  2. /*-------------------------------------------------------
  3. public E pollFirst() {
  4. int h = head;
  5. //1.从数组中通过头部索引获取头部元素值
  6. E result = (E) elements[h];
  7. //2.如果头部元素值为null,直接返回
  8. if (result == null)
  9. return null;
  10. //3.将原头部元素指向的位置的值清空
  11. elements[h] = null;
  12. //4.头部向后移动(原头部后面的元素成为新的头部)
  13. head = (h + 1) & (elements.length - 1);
  14. //5.返回删除的元素值
  15. return result;
  16. }
  17. --------------------------------------------------------*/
  18. E x = pollFirst();
  19. if (x == null)
  20. throw new NoSuchElementException();
  21. return x;
  22. }
(11)获取队列中的头部和底部值(只获取,不删除)peek,peekFirst和peekLast
  • peek():获取队列的第一个元素,通过head指针来获取
  • peekFirst():获取队列中的第一个元素,与peek是相同的功能
  • peekLast():获取队列中的最后一个元素,通过tail指针来获取
(12)获取队列的长度size

I.size方法的使用

  • size():获取队列的长度
  1. ArrayDeque<String> queue = new ArrayDeque<String>(5);
  2. queue.add("A");
  3. queue.add("B");
  4. queue.add("C");
  5. System.out.println(queue.size()); //队列的长度为3

II.size方法的实现解读

  1. public int size() {
  2. /*
  3. * tail和head的位置关系有3种:
  4. * (1)tail在head的左侧
  5. * (2)tail在head的右侧
  6. * (3)head和tail重合
  7. */
  8. return (tail - head) & (elements.length - 1);
  9. }
(13)将队列转化为数组toArray

I.toArray方法的使用

  • toArray():返回将队列转换为的对象数组
  • toArray(T[] a):将数组转化为指定的泛型数组
  1. ArrayDeque<String> queue = new ArrayDeque<String>(5);
  2. queue.add("A");
  3. queue.add("B");
  4. queue.add("C");
  5. queue.addLast("D");
  6. queue.addLast("E");
  7. Object[] queueArr = queue.toArray();
  8. System.out.print("[");
  9. for (int i = 0; i< queueArr.length; i++) {
  10. System.out.print(queueArr[i]+",");
  11. }
  12. System.out.print("]"); //[A,B,C,D,E,]
  13. String[] qArr = new String[queue.size()];
  14. queue.toArray(qArr);
  15. System.out.print("[");
  16. for (int i = 0; i< qArr.length; i++) {
  17. System.out.print(qArr[i]+",");
  18. }
  19. System.out.print("]"); //[A,B,C,D,E,]

II.toArray方法的实现解读

  1. public Object[] toArray() {
  2. /*---------------------------------------------------------------
  3. private <T> T[] copyElements(T[] a) {
  4. //头部在底部的左边,只能一直是从尾部添加元素,头部没动,那么从head开始到tail这一段都是队列中的元素
  5. if (head < tail) {
  6. System.arraycopy(elements, head, a, 0, size());
  7. } else if (head > tail) {
  8. int headPortionLen = elements.length - head;
  9. //从头部开始到数组结尾这一段
  10. System.arraycopy(elements, head, a, 0, headPortionLen);
  11. //从数组第一个元素开始到尾部这一段
  12. System.arraycopy(elements, 0, a, headPortionLen, tail);
  13. }
  14. return a;
  15. }
  16. ----------------------------------------------------------------*/
  17. return copyElements(new Object[size()]);
  18. }
  19. public <T> T[] toArray(T[] a) {
  20. //队列的长度
  21. int size = size();
  22. //如果用于存储的新数组长度小于队列长度,则需要分配一个更大的空间给这个数组
  23. if (a.length < size)
  24. a = (T[])java.lang.reflect.Array.newInstance(
  25. a.getClass().getComponentType(), size);
  26. //复制元素
  27. copyElements(a);
  28. if (a.length > size)
  29. a[size] = null;
  30. return a;
  31. }

三、LinkedList

注:LinkedList在之前的列表章节已经讲解过了,这里不再赘述了