列队 Queue 接口概述

￡神魔★判官ぃ 2024-03-23 20:58 100阅读 0赞

在Java中，Queue（队列）是一种基本的数据结构，用于按照先进先出（FIFO）的顺序存储元素。Java提供了多种实现Queue接口的类，以下是几种常见的实现方式：

![c5a1d2b1cb8040dc8a27e74c74add655.png][]

1.  LinkedList：LinkedList实现了Queue接口，并且支持队列的所有操作，包括添加元素到队尾、获取队头元素、删除队头元素等。

Queue<String> queue = new LinkedList<>();
    queue.add("element1"); // 添加元素到队尾
    String element = queue.peek(); // 获取队头元素
    String removedElement = queue.remove(); // 删除队头元素

2. ArrayDeque：ArrayDeque也实现了Queue接口，并且支持队列的操作。它使用可调整大小的数组来存储元素，可以在队列的两端进行高效地插入和删除操作。

Queue<String> queue = new ArrayDeque<>();
    queue.offer("element1"); // 添加元素到队尾
    String element = queue.peek(); // 获取队头元素
    String removedElement = queue.poll(); // 删除队头元素

3. PriorityQueue：PriorityQueue是一种基于优先级的队列，它允许你根据元素的自然顺序或自定义的Comparator来确定元素的优先级。

Queue<Integer> queue = new PriorityQueue<>();
    queue.offer(3); // 添加元素到队列并根据优先级排序
    queue.offer(1);
    queue.offer(2);
    int element = queue.peek(); // 获取优先级最高的元素
    int removedElement = queue.poll(); // 删除并返回优先级最高的元素

通过使用上述的Queue实现类，你可以根据具体的需求选择适合的队列实现，并进行相应的操作。

### 继承Queue的接口 ###

Queue接口还可以被各种子接口继承：

>  *  Deque
>  *  BlockingQueue
>  *  BlockingDeque

![Deque，BlockingQueue和BlockingDeque扩展了Queue接口。][Deque_BlockingQueue_BlockingDeque_Queue]![093f776f8dbc427986e63c0a48594ebb.png][]

### 队列数据结构的工作流程 ###

在队列中，以**先进先出**的方式存储和访问元素。也就是说，**从后面添加元素，从前面删除元素**。

![队列数据结构的工作：先进先出。][queue-implementation.png]![23671018434143f8877fa2e79c5fd816.png][]

### 如何使用队列（Queue）？ ###

在Java中，必须导入java.util.Queue包才能使用Queue。

// 使用 LinkedList 创建
    Queue<String> animal1 = new LinkedList<>();
    
    // 使用 ArrayDeque 创建
    Queue<String> animal2 = new ArrayDeque<>();
    
    // 使用 PriorityQueue创建
    Queue<String> animal 3 = new PriorityQueue<>();

在这里，我们分别创建了类LinkedList，ArrayDeque和PriorityQueue的对象Animal1，Animal2和Animal3。 这些对象可以使用Queue接口的功能。

### Queue的方法 ###

Queue接口包括Collection接口的所有方法。 这是因为Collection是Queue的超级接口。

Queue接口的一些常用方法是：

>  *  **add()** \- 将指定的元素插入队列。如果任务成功，则add()返回true，否则将引发异常。
>  *  **offer()** \- 将指定的元素插入队列。如果任务成功，则offer()返回true，否则返回false。
>  *  **element()** \- 返回队列的开头。如果队列为空，则引发异常。
>  *  **peek()** \- 返回队列的开头。 如果队列为空，则返回null。
>  *  **remove()** \- 返回并删除队列的头部。如果队列为空，则引发异常。
>  *  **poll()** \- 返回并删除队列的开头。 如果队列为空，则返回null。

### 队列接口的实现 ###

**1.添加元素：** 为了在队列中添加一个元素，我们可以使用add()方法。在PriorityQueue中不保留插入顺序。元素是根据优先级顺序存储的，默认是升序的。

**例子**

// Java program to add elements
    // to a Queue
      
    import java.util.*;
      
    public class GFG {
      
        public static void main(String args[])
        {
            Queue<String> pq = new PriorityQueue<>();
      
            pq.add("Geeks");
            pq.add("For");
            pq.add("Geeks");
      
            System.out.println(pq);
        }
    }

**输出**

[For, Geeks, Geeks]

**2.删除元素：** 为了从队列中删除一个元素，我们可以使用remove()方法。如果有多个这样的对象，那么第一个出现的对象将被删除。除此之外，poll()方法也被用来删除头部并返回。

**例子**

// Java program to remove elements
    // from a Queue
      
    import java.util.*;
      
    public class GFG {
      
        public static void main(String args[])
        {
            Queue<String> pq = new PriorityQueue<>();
      
            pq.add("Geeks");
            pq.add("For");
            pq.add("Geeks");
      
            System.out.println("Initial Queue " + pq);
      
            pq.remove("Geeks");
      
            System.out.println("After Remove " + pq);
      
            System.out.println("Poll Method " + pq.poll());
      
            System.out.println("Final Queue " + pq);
        }
    }

**输出**

Initial Queue [For, Geeks, Geeks]
    After Remove [For, Geeks]
    Poll Method For
    Final Queue [Geeks]

**3.遍历队列：** 有多种方法来遍历队列。最著名的方法是将队列转换为数组并使用for循环进行遍历。然而，队列也有一个内置的迭代器，可以用来遍历队列。

**例子**

// Java program to iterate elements
    // to a Queue
      
    import java.util.*;
      
    public class GFG {
      
        public static void main(String args[])
        {
            Queue<String> pq = new PriorityQueue<>();
      
            pq.add("Geeks");
            pq.add("For");
            pq.add("Geeks");
      
            Iterator iterator = pq.iterator();
      
            while (iterator.hasNext()) {
                System.out.print(iterator.next() + " ");
            }
        }
    }

**输出**

For Geeks Geeks

#### **队列的特点：** 以下是队列的特点。 ####

>  *  队列用于在队列的末端插入元素，并从队列的开头删除。它遵循FIFO概念。
>  *  Java队列支持集合接口的所有方法，包括插入、删除等。
>  *  LinkedList、ArrayBlockingQueue和PriorityQueue是最常使用的实现方式。
>  *  如果对阻塞队列进行任何空操作，就会抛出NullPointerException。
>  *  java.util包中的队列是无界队列。
>  *  java.util.concurrent包中的队列是有界队列。
>  *  除了Deques之外，所有的队列都分别支持在队列的尾部和头部进行插入和删除。Deques支持两端的元素插入和删除。

### 实现队列接口的类 ###

**1.PriorityQueue：** 在集合框架中实现的PriorityQueue类为我们提供了一种根据优先级来处理对象的方法。众所周知，队列遵循先入先出的算法，但有时需要根据优先级来处理队列中的元素，这时PriorityQueue就发挥作用了。让我们看看如何使用这个类来创建一个队列对象。

**例子**

import java.util.*;
      
    class Zeus {
      
        public static void main(String args[])
        {
            // Creating empty priority queue
            Queue<Integer> pQueue
                = new PriorityQueue<Integer>();
      
            // Adding items to the pQueue
            // using add()
            pQueue.add(10);
            pQueue.add(20);
            pQueue.add(15);
      
            // Printing the top element of
            // the PriorityQueue
            System.out.println(pQueue.peek());
      
            // Printing the top element and removing it
            // from the PriorityQueue container
            System.out.println(pQueue.poll());
      
            // Printing the top element again
            System.out.println(pQueue.peek());
        }
    }

**输出**

10
    10
    15

**2.** **LinkedList：** LinkedList是一个在集合框架中实现的类，它内在地实现了链接列表数据结构。它是一个线性数据结构，其中的元素不存储在连续的位置，每个元素都是一个独立的对象，有数据部分和地址部分。这些元素使用指针和地址进行链接。每个元素被称为一个节点。由于其动态性和易于插入和删除的特点，它们比数组或队列更受欢迎。让我们看看如何使用这个类来创建一个队列对象。

**例子**

import java.util.*;
      
    class Zeus {
      
        public static void main(String args[])
        {
            // Creating empty LinkedList
            Queue<Integer> ll
                = new LinkedList<Integer>();
      
            // Adding items to the ll
            // using add()
            ll.add(10);
            ll.add(20);
            ll.add(15);
      
            // Printing the top element of
            // the LinkedList
            System.out.println(ll.peek());
      
            // Printing the top element and removing it
            // from the LinkedList container
            System.out.println(ll.poll());
      
            // Printing the top element again
            System.out.println(ll.peek());
        }
    }

**输出**

10
    10
    20

**3.** **PriorityBlockingQueue：** 需要注意的是，PriorityQueue和LinkedList的实现都不是线程安全的。如果需要线程安全的实现，PriorityBlockingQueue是一个替代性的实现。PriorityBlockingQueue是一个无界的阻塞队列，它使用与PriorityQueue类相同的排序规则，并提供阻塞的检索操作。  
因为它是无界的，添加元素有时会因为资源耗尽而失败，导致OutOfMemoryError。让我们看看如何使用这个类来创建一个队列对象。

**例子**

import java.util.concurrent.PriorityBlockingQueue;
    import java.util.*;
      
    class Zeus {
        public static void main(String args[])
        {
            // Creating empty priority
            // blocking queue
            Queue<Integer> pbq
                = new PriorityBlockingQueue<Integer>();
      
            // Adding items to the pbq
            // using add()
            pbq.add(10);
            pbq.add(20);
            pbq.add(15);
      
            // Printing the top element of
            // the PriorityBlockingQueue
            System.out.println(pbq.peek());
      
            // Printing the top element and
            // removing it from the
            // PriorityBlockingQueue
            System.out.println(pbq.poll());
      
            // Printing the top element again
            System.out.println(pbq.peek());
        }
    }

**输出**

10
    10
    15

#### 队列接口的方法 ####

队列接口继承了集合接口中的所有方法，同时实现了以下方法。

<table> 
 <thead> 
  <tr> 
   <th>方法</th> 
   <th>描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>add(int index, element)</td> 
   <td>这个方法用来在队列中的某个特定索引处添加一个元素。当一个参数被传递时，它只是在队列的末端添加元素。</td> 
  </tr> 
  <tr> 
   <td>addAll(int index, Collection collection)</td> 
   <td>这个方法用来添加给定集合中的所有元素到队列中。当传递一个参数时，它在队列的末尾添加给定集合的所有元素。</td> 
  </tr> 
  <tr> 
   <td>size()</td> 
   <td>该方法用于返回队列的大小。</td> 
  </tr> 
  <tr> 
   <td>clear()</td> 
   <td>这个方法用来删除队列中的所有元素。然而，创建的队列的引用仍然被保存。</td> 
  </tr> 
  <tr> 
   <td>remove()</td> 
   <td>这个方法用来从队列的前面删除元素。</td> 
  </tr> 
  <tr> 
   <td>remove(int index)</td> 
   <td>这个方法从指定的索引中删除一个元素。它将随后的元素（如果有的话）向左移动并将它们的索引减少1。</td> 
  </tr> 
  <tr> 
   <td>remove(element)</td> 
   <td>该方法用于删除并返回队列中第一次出现的给定元素。</td> 
  </tr> 
  <tr> 
   <td>get(int index)</td> 
   <td>该方法返回指定索引的元素。</td> 
  </tr> 
  <tr> 
   <td>set(int index, element)</td> 
   <td>这个方法用新的元素替换给定索引上的元素。这个函数返回刚刚被新元素替换的元素。</td> 
  </tr> 
  <tr> 
   <td>indexOf(element)</td> 
   <td>该方法返回给定元素的第一次出现，如果该元素在队列中不存在，则返回 <em>-1</em> 。</td> 
  </tr> 
  <tr> 
   <td>lastIndexOf(element)</td> 
   <td>该方法返回给定元素的最后一次出现，如果该元素在队列中不存在，则返回 <em>-1</em> 。</td> 
  </tr> 
  <tr> 
   <td>equals(element)</td> 
   <td>该方法用于比较给定元素与队列中的元素是否相等。</td> 
  </tr> 
  <tr> 
   <td>hashCode()</td> 
   <td>该方法用于返回给定队列的哈希代码值。</td> 
  </tr> 
  <tr> 
   <td>isEmpty()</td> 
   <td>该方法用于检查队列是否为空。如果队列是空的，它返回 true，否则返回 false。</td> 
  </tr> 
  <tr> 
   <td>contains(element)</td> 
   <td>该方法用于检查队列是否包含给定的元素。如果队列包含该元素，它返回真。</td> 
  </tr> 
  <tr> 
   <td>containsAll(Collection)</td> 
   <td>该方法用于检查队列是否包含所有的元素集合。</td> 
  </tr> 
  <tr> 
   <td>sort(Comparator comp)</td> 
   <td>该方法用于在给定的比较器的基础上对队列中的元素进行排序。</td> 
  </tr> 
  <tr> 
   <td>boolean add(object)</td> 
   <td>该方法用于将指定的元素插入队列中，成功后返回true。</td> 
  </tr> 
  <tr> 
   <td>boolean offer(object)</td> 
   <td>该方法用于将指定的元素插入队列中。</td> 
  </tr> 
  <tr> 
   <td>Object poll()</td> 
   <td>该方法用于检索和删除队列的头部，如果队列是空的，则返回null。</td> 
  </tr> 
  <tr> 
   <td>Object element()</td> 
   <td>这个方法用于检索，但不删除队列的头部。</td> 
  </tr> 
  <tr> 
   <td>Object peek()</td> 
   <td>这个方法用来检索，但不删除这个队列的头部，如果这个队列是空的，则返回null。</td> 
  </tr> 
 </tbody> 
</table>

[c5a1d2b1cb8040dc8a27e74c74add655.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/d02a1136bf614a0c92ef215b194c9c20.png
[Deque_BlockingQueue_BlockingDeque_Queue]: https://www.nhooo.com/run/images/queue-subinterfaces.png
[093f776f8dbc427986e63c0a48594ebb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/dd6a6e88597b48669c2b30236ed61413.png
[queue-implementation.png]: https://www.nhooo.com/run/images/queue-implementation.png
[23671018434143f8877fa2e79c5fd816.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/a779d8541677430fa882490621f12cd0.png