Java_集合之Queue的用法

素颜马尾好姑娘i 2023-07-04 11:14 95阅读 0赞

### 一.认识Queue ###

顾名思义，Queue代表的线性表中的队列，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，遵循先进先出原则（FIFO,First In First Out)。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

### **二、Queue的用法** ###

**我们先来看看Queue在java集合体系中所处的位置。**

**![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYXNlcXJy_size_16_color_FFFFFF_t_70][]**

如图所示，Queue是作为Collection接口的一个子接口，而Deque继承了Queue接口，也就是说Deque拥有更多操作。不过需要注意的是，Queue和Deque都是接口，不能实例化对象，而LinkedList类实现了Deque接口，也就间接实现了Queue,所以我们可以用LinkedList来实现队列的操作。

我们先来看看Queue的所有方法（不包含从Collection继承来的方法，Deque里方法更多，这里就不介绍了）

<table style="width:669px;"> 
 <tbody> 
  <tr> 
   <td style="width:88px;">返回值类型</td> 
   <td style="width:120px;">&nbsp;方法</td> 
   <td style="width:463px;">描述</td> 
  </tr> 
  <tr> 
   <td style="width:88px;">boolean</td> 
   <td style="width:120px;">add(E e)</td> 
   <td style="width:463px;">添加元素到队列中，如果不违反容量限制立即执行，若无可用可用空间会抛出异常</td> 
  </tr> 
  <tr> 
   <td style="width:88px;">E</td> 
   <td style="width:120px;">element()</td> 
   <td style="width:463px;">返回这个队列的头，但不删除</td> 
  </tr> 
  <tr> 
   <td style="width:88px;">boolean</td> 
   <td style="width:120px;">offer(E e)</td> 
   <td style="width:463px;">将指定的元素插入到队列中，如果不违反容量限制立即执行</td> 
  </tr> 
  <tr> 
   <td style="width:88px;">E</td> 
   <td style="width:120px;">peek()</td> 
   <td style="width:463px;">返回队头元素，但不删除,若队列为空，则返回null</td> 
  </tr> 
  <tr> 
   <td style="width:88px;">E</td> 
   <td style="width:120px;">poll()</td> 
   <td style="width:463px;">返回这个队列的队头元素并删除队头元素,若队列为空，则返回null</td> 
  </tr> 
  <tr> 
   <td style="width:88px;">E</td> 
   <td style="width:120px;">remove()</td> 
   <td style="width:463px;">返回队头元素并删</td> 
  </tr> 
 </tbody> 
</table>

**我们简单测试一下代码**

package com.rong.question;
    
    import java.util.LinkedList;
    import java.util.Queue;
    
    public class QueueTest {
        public static void main(String[] args) {
            Queue<Integer> queue = new LinkedList<>();
            queue.add(1);//用add方式添加
            queue.offer(2);//用offer添加
            queue.offer(3);
            System.out.println("队头元素："+ queue.element());//用element获取队头
            System.out.println("队头元素："+queue.peek());//用peek获取队头
            System.out.println("删除元素："+queue.poll());//用poll方式出队
            System.out.println("删除元素："+queue.remove());//用remove方式出队
            System.out.println("队头元素："+ queue.element());
        }
    }

![20200210150307728.png][]

### 三、关于PriorityQueue(优先级队列） ###

PriorityQueue是Queue的一个实现类，方法与上面的差不多，但PriorityQueue保持了队列顶部元素总是最小，也就说用peek()和element()都会返回队列中的最小元素，而poll()就会删除掉当前队列的最小元素；

也就是说如果是数字会按照从小到大进行出队，而是字母的话就会按照a,b,c,d,e.....的方式出队。

使用的Priority时需要注意的是：

1.  优先级队列不允许 null 元素。
2.  依靠自然排序的优先级队列（也就是默认方式排序）还不允许插入不可比较的对象（这样做可能导致 ClassCastException）。

**我们简单测试一下：**

package com.rong.question;
    
    import java.util.*;
    
    public class Test {
        public static void main(String[] args) {
            PriorityQueue<Integer> pq = new PriorityQueue<>();
            pq.offer(5);
            pq.offer(7);
            pq.offer(2);
            pq.offer(4);
            System.out.println("================数字=================");
            System.out.println("当前队头："+pq.element());
            System.out.print(pq.poll()+"\t");
            System.out.print(pq.poll()+"\t");
            System.out.print(pq.poll()+"\t");
            System.out.print(pq.poll()+"\t");
    
            System.out.println();
            PriorityQueue<String> strings = new PriorityQueue<>();
            strings.offer("c");
            strings.offer("a");
            strings.offer("s");
            strings.offer("e");
            System.out.println("=================字符串===============");
            System.out.print(strings.poll()+"\t");
            System.out.print(strings.poll()+"\t");
            System.out.print(strings.poll()+"\t");
            System.out.print(strings.poll()+"\t");
        }
    }

![20200211145604902.png][]

**自定义排序方式**

package com.rong.question;
    
    import java.util.*;
    
    public class Test {
        public static void main(String[] args) {
            //自定义比较器，降序
            Comparator<Integer> cmp = new Comparator<Integer>() {
                public int compare(Integer e1, Integer e2) {
                    return e2 - e1;
                }
            };
            PriorityQueue<Integer> pq = new PriorityQueue<>(cmp);
            pq.offer(5);
            pq.offer(7);
            pq.offer(2);
            pq.offer(4);
            System.out.println("================数字=================");
            System.out.println("当前队头："+pq.element());
            System.out.print(pq.poll()+"\t");
            System.out.print(pq.poll()+"\t");
            System.out.print(pq.poll()+"\t");
            System.out.print(pq.poll()+"\t");
        }
    }

![20200211152507208.png][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYXNlcXJy_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200210140229240.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYXNlcXJy,size_16,color_FFFFFF,t_70
[20200210150307728.png]: https://img-blog.csdnimg.cn/20200210150307728.png
[20200211145604902.png]: https://img-blog.csdnimg.cn/20200211145604902.png
[20200211152507208.png]: https://img-blog.csdnimg.cn/20200211152507208.png