【Java Queue】Java中队列Queue（PriorityQueue优先队列）接口 及 双端队列Deque（LinkedList链表、ArrayDeque）接口_java 接口中使用queue接收数据

一、Queue 接口

Java集合框架的Queue接口提供了队列数据结构的功能。它继承了Collection接口。

1.实现队列的类

由于Queue是一个接口，因此我们无法提供它的直接实现。
为了使用Queue的功能，我们需要使用实现它的类：

• ArrayDeque：双端队列
• LinkedList：双向链表
• PriorityQueue：优先队列
  

2.继承Queue接口

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

• Deque
• BlockingQueue
• BlockingDeque
  

3.队列数据结构的工作流程

4.使用Queue

1. 使用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<>();
1
2
3
4
5
6
7
8

2. Queue的方法
Queue接口包括Collection接口的方法，因为Collection是Queue的超级接口。
常用方法：

• add：将元素插入队列，成功则add()返回True，失败则返回异常。
• offer: 将元素插入队列，成功则offer()返回True，失败则返回False。
• element：返回队列的开头。如果为空，则发生异常。
• peek：返回队列的开头，如果为空，返回null。
• remove：返回并删除队列的开头，如果为空，发生异常。
• poll：返回并删除队列的开头，如果为空，返回False。

5.PriorityQueue优先队列

PriorityQueue类提供堆数据结构的功能。
实现了Queue接口：

PriorityQueue优先队列与普通队列不同的是，它是按排序顺序检索的。
如果我们以升序检索元素。在这种情况下，优先队列的头是最小的元素。检索到该元素后，下一个最小的元素将成为队列的头。

注意：优先队列的元素可能没有排序。但是，元素总是按排序顺序检索的。

创建优先级队列，我们必须导入java.util.PriorityQueue包。

PriorityQueue<Integer> numbers = new PriorityQueue<>();
1

上面是一个没有任何参数的优先级队列。在这种情况下，优先级队列的头是队列中最小的元素。元素将按升序从队列中移除。
并且，我们也可以借助 Comparator 接口自定义元素的顺序。

增加访问及删除元素的方法同Queue接口方法！
其他：
①遍历PriorityQueue：

	//创建优先级队列
      PriorityQueue<Integer> numbers = new PriorityQueue<>();
      ......
	 //使用iterator()方法
      Iterator<Integer> iterate = numbers.iterator();
      while(iterate.hasNext()) {
          System.out.print(iterate.next());
          System.out.print(", ");
      }
1
2
3
4
5
6
7
8
9

②PriorityQueue其他方法：

③PriorityQueue 比较器(comparator)：
优先级队列元素都是按自然顺序（升序）检索的。 但是，我们可以自定义此顺序。

所以，我们需要创建自己的comparator类，它实现了Comparator接口。

import java.util.PriorityQueue;
import java.util.Comparator;
class Main {
    public static void main(String[] args) {

        //创建优先级队列
        PriorityQueue<Integer> numbers = new PriorityQueue<>(new CustomComparator());
        numbers.add(4);
        numbers.add(2);
        System.out.print("PriorityQueue: " + numbers);
    }
}

class CustomComparator implements Comparator<Integer> {
    @Override
    public int compare(Integer number1, Integer number2) {
        int value =  number1.compareTo(number2);
        //元素以相反的顺序排序
        if (value > 0) {
            return -1;
        }
        else if (value < 0) {
            return 1;
        }
        else {
            return 0;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

二、Deque接口

Java集合框架的Deque接口提供了双端队列(Deque)的功能。它继承了Queue接口。

1.实现Deque的类

为了使用Deque接口的功能，我们需要使用实现接口的类：

• ArrayDeque
• LinkedList
  

2. 双端队列的工作原理

在常规队列中，元素是从后面添加的，而从前面删除的。但是，在双端队列中，我们可以从前后插入和删除元素。

3.使用Deque

1. 使用Deque
在Java中，我们必须导入要使用Deque的包 java.util.Deque 。

//使用 ArrayDeque创建
Deque<String> animal1 = new ArrayDeque<>();
//使用 ArrayLinkedList创建
Deque<String> animal2 = new LinkedList<>();
1
2
3
4

2. Deque的方法

由于Deque继承了Queue接口，因此它继承了Queue接口的所有方法。

除了Queue接口中可用的方法之外，Deque界面还包括以下方法：

• addFirst() - 在双端队列的开头添加指定的元素。如果双端队列已满，则引发异常。
• addLast() - 在双端队列的末尾添加指定的元素。如果双端队列已满，则引发异常。
• offerFirst() - 在双端队列的开头添加指定的元素。如果双端队列已满，则返回false。
• offerLast() - 在双端队列的末尾添加指定的元素。如果双端队列已满，则返回false。
• getFirst() - 返回双端队列的第一个元素。如果双端队列为空，则引发异常。
• getLast() - 返回双端队列的最后一个元素。如果双端队列为空，则引发异常。
• peekFirst() - 返回双端队列的第一个元素。如果双端队列为空，则返回null。
• peekLast() - 返回双端队列的最后一个元素。如果双端队列为空，则返回null。
• removeFirst() - 返回并删除双端队列的第一个元素。如果双端队列为空，则引发异常。
• removeLast() - 返回并删除双端队列的最后一个元素。如果双端队列为空，则引发异常。
• pollFirst() - 返回并删除双端队列的第一个元素。如果双端队列为空，则返回null。
• pollLast() - 返回并删除双端队列的最后一个元素。如果双端队列为空，则返回null。

3.双端队列作为堆栈数据结构
Java Collections框架的Stack类提供了堆栈的实现。

但是，建议Deque用作堆栈而不是Stack类。这是因为Stack的方法是同步的。

以下是Deque接口提供的用于实现堆栈的方法：

• push() - 在双端队列的开头添加元素
• pop() - 从双端队列的开头删除元素
• peek() - 从双端队列的开头返回一个元素

4.LinkedList双向链表

Java集合框架的LinkedList类提供了链表数据结构的功能。
1.由LinkedList实现的接口

2.Java中的LinkedList实现
Java LinkedList类提供了双向链表实现。

链表中的每个元素都称为节点。它包含3个字段：

• Prev - 将前一个元素的地址存储在列表中。 第一个元素为null。
• Next - 在列表中存储下一个元素的地址。 最后一个元素为null。
• Data - 存储实际数据。

链表中的元素不是按顺序存储的。相反，它们是分散的，并通过链接(Prev和Next)连接。

链接列表中包含3个元素。

• Dog - 第一个元素将null作为前一个地址，并将Cat的地址作为下一个地址
• Cat - 第二个元素将Dog的地址作为前一个地址，将Cow的地址作为下一个地址
• Cow - 最后一个元素将Cat的地址作为前一个地址，并将null作为下一个元素

3.使用
(1)将元素添加到LinkedList：

1. animals.add("Cat");
2. animals.add(1,"Cat");
3. animals.addAll(mammals);
4. 使用listIterator()方法:
 		LinkedList<String> animals= new LinkedList<>();
        //创建ListIterator对象
        ListIterator<String> listIterate = animals.listIterator();
        listIterate.add("Dog");
1
2
3
4
5
6
7
8

(2)访问LinkedList元素:

1. animals.get(1);
2. 创建Iterator的对象:
        Iterator<String> iterate = animals.iterator();
        while(iterate.hasNext()) {
            System.out.print(iterate.next());
        }
3. 使用listIterator()方法:
		//创建ListIterator对象
        ListIterator<String> listIterate = animals.listIterator();
        while(listIterate.hasNext()) {
            System.out.print(listIterate.next());
        }
        // 向后遍历
        while(listIterate.hasPrevious()) {
            System.out.print(listIterate.previous());
        } 
        /**
        hasNext() - 如果存在下一个元素，则返回true
		next() - 返回下一个元素
		hasPrevious() - 如果存在先前的元素，则返回true
		previous() - 返回上一个元素
		  */    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

(3)查找 LinkedList 元素:

1. animals.contains("Dog");
2. indexOf()或lastIndexOf():
		//第一次出现Dog
        int index1 = animals.indexOf("Dog");
        //最后一次出现Dog
        int index2 = animals.lastIndexOf("Dog");
1
2
3
4
5
6

(4)更改 LinkedList 元素:

1. animals.set(3, "Zebra");
2. 创建ListIterator对象
        ListIterator<String> listIterate = animals.listIterator();
        listIterate.next();
        //更改由next()返回的元素
        listIterate.set("Cow");
1
2
3
4
5
6

(5)删除LinkedList元素:

1. animals.remove(1);
2. 创建ListIterator对象
        ListIterator<String> listIterate = animals.listIterator();
        listIterate.next();
        //删除next()返回的元素
        listIterate.remove();
3. animals.clear();//删除所有元素
4. animals.removeIf((Integer i)->i < 4);//删除所有小于4的元素
1
2
3
4
5
6
7
8

4.LinkedList作为Deque和Queue
由于LinkedList类还实现了Queue和Deque接口，因此它也可以实现这些接口的方法。

5.遍历LinkedList迭代
(1)forEach循环遍历

for(String animal: animals) {
    System.out.print(animal);
    System.out.print(", ");
}
1
2
3
4

(2)for循环

for(int i=0; i < animals.size(); i++) {
    System.out.print(animals.get(i));
    System.out.print(", ");
}
1
2
3
4

(3)iterator()方法

Iterator<String> iterate = animals.iterator();
while(iterate.hasNext()) {
   System.out.print(iterate.next());
   System.out.print(", ");
}
1
2
3
4
5

6.LinkedList与ArrayList
LinkedList和ArrayList都实现Collections框架的List接口。 但是，它们之间存在一些差异。

5.ArrayDeque双端队列

在Java中，我们可以使用ArrayDeque该类使用数组来实现队列和双端队列数据结构。

1.由ArrayDeque实现的接口

2.使用
为了创建ArrayDeque双端队列，我们必须导入java.util.ArrayDeque包。

//创建字符串类型ArrayDeque
ArrayDeque<String> animals = new ArrayDeque<>();

//创建整数类型ArrayDeque
ArrayDeque<Integer> age = new ArrayDeque<>();
1
2
3
4
5

方法同Deque方法，除此之外：

• 删除元素：使用clear()方法；
• 迭代遍历ArrayDeque：
  iterator() - 返回可用于遍历ArrayDeque双端队列的迭代器
  descendingIterator() -返回一个迭代器，该迭代器可用于以相反顺序遍历ArrayDeque双端队列

为了使用这些方法，我们必须导入java.util.Iterator包。

import java.util.ArrayDeque;
import java.util.Iterator;

class Main {
    public static void main(String[] args) {
        ArrayDeque<String> animals= new ArrayDeque<>();
        animals.add("Dog");
        animals.add("Cat");
        animals.add("Horse");

        System.out.print("ArrayDeque: ");

        //使用iterator()
        Iterator<String> iterate = animals.iterator();
        while(iterate.hasNext()) {
            System.out.print(iterate.next());
            System.out.print(", ");
        }

        System.out.print("\n反向ArrayDeque: ");
        //使用descendingIterator()
        Iterator<String> desIterate = animals.descendingIterator();
        while(desIterate.hasNext()) {
            System.out.print(desIterate.next());
            System.out.print(", ");
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

3.其他方法

4.ArrayDeque作为堆栈
要在Java中实现LIFO（后进先出）堆栈，建议在Stack类上使用双端队列。该ArrayDeque类比Stack类快。

ArrayDeque 提供了以下可用于实现堆栈的方法。

• push() - 在堆栈顶部添加一个元素
• peek() - 从堆栈顶部返回一个元素
• pop() - 返回并从堆栈顶部删除元素

5.ArrayDeque与 LinkedList类

ArrayDeque和Java的LinkedList都实现了Deque接口。但是，它们之间存在一些差异。

• LinkedList支持空元素，而ArrayDeque不支持。
• 链表中的每个节点都包含到其他节点的链接。这就是LinkedList比ArrayDeque需要更多存储空间的原因。
• 如果要实现队列或双端队列数据结构，则ArrayDeque可能比LinkedList快。