Java数据结构之队列(动力节点Java学院整理)

队列是一种有序列表，在其中所有插入操作必须在后端进行，而所有的删除操作必须在前端进行的数据结构。这种结构有时被称为先进先出（FIFO）。

队列的分类

• 普通队列：队列和栈一样，都是只能在一端进行插入操作，在另一端进行删除操作的特殊线性表。队列的特点是：先进先出。适用于数据必须按照插入顺序处理的必要场合。

• 双端队列（Deque）：是能够在队列任意一端入队和出队的队列。双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。双端队列可以在队列任意一端入队和出队，因此队列的队首、队尾都是动态变化的。

• 优先队列：优先队列这里不再讲解，有兴趣可以自行查阅。

队列的创建

Queue<String> queue = new LinkedList<>();

• Queue是队列的接口，常见的实现类有LinkedList和ArrayDeque

• LinkedList是一个用链表实现的双向队列，因此既可以表现出队列的特点，也可以表现出栈的特点

• ArrayDeque是一个用数组实现的双向队列，它可以像队列一样在队尾添加元素，在队首弹出元素；同时也可以像栈一样，在队尾添加元素，在队尾弹出元素。

队列的常用方法

插入方法

• offer(E e)：向队列末端插入一个元素

Queue<String> queue = new LinkedList<>();
queue.offer("first");
queue.offer("second");

• add(E e)：向队列末端插入一个元素，如果队列已满，则抛出异常

Queue<String> queue = new LinkedList<>();
queue.add("first");
queue.add("second");

查询方法

• peek()：返回队首元素，但不删除

Queue<String> queue = new LinkedList<>();
queue.offer("first");
queue.offer("second");
String peek = queue.peek();
System.out.println(peek);
System.out.println(queue);

输出结果为

first
[first, second]

• element()：返回队首元素，但不删除。如果队列为空，则抛出异常

Queue<String> queue = new LinkedList<>();
queue.offer("first");
queue.offer("second");
String element = queue.element();
System.out.println(element);
System.out.println(queue);

输出结果为

first
[first, second]

删除方法

• poll()：弹出队首元素，如果队列为空，则返回null

Queue<String> queue = new LinkedList<>();
queue.offer("first");
queue.offer("second");
String poll = queue.poll();
System.out.println(poll);
System.out.println(queue);

输出结果为

first
[second]

• remove()：弹出队首元素，如果队列为空，则抛出异常

Queue<String> queue = new LinkedList<>();
queue.offer("first");
queue.offer("second");
String remove = queue.remove();
System.out.println(remove);
System.out.println(queue);

输出结果为

first
[second]

示例说明

队列模拟银行排队场景

有一家银行，来到银行的客户需要在大厅排队等候叫号叫到自己号码时，才能进入办理业务。试用队列模拟这个场景。

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class BankQueueSimulation {

    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        for (int i = 1; i <= 10; i++) {
            String number = String.format("%03d", i);
            queue.offer(number);
        }
        Scanner scanner = new Scanner(System.in);
        while (true) {
            System.out.print("请输入你的号码：");
            String inputNumber = scanner.next();
            if (queue.contains(inputNumber)) {
                while (!queue.peek().equals(inputNumber)) {
                    String otherNumber = queue.poll();
                    System.out.println("现在叫到" + otherNumber + "号，请等待。");
                }
                queue.poll();
                System.out.println("现在叫到" + inputNumber + "号，请进入。");
                break;
            } else {
                System.out.println("该号码不在队列中，请重新输入。");
            }
        }
    }
}

以上程序模拟了一个银行的叫号排队场景。程序先使用循环将10个固定号码插入队列中，接着通过输入将客户的号码加入到队列中。如果队列中存在该号码，程序就会循环弹出队列中的元素，直到遇到该号码，然后弹出该号码，输出提示让客户进入办公室办理业务。

双端队列模拟操作系统任务队列

对于操作系统，通常有两种情况将任务加入任务队列：

1. 普通任务，当任务执行时会将自己从队列中删除
2. 定时任务，当任务超时时才会将自己从队列中删除

这里就不再讨论第二种情况。

import java.util.ArrayDeque;
import java.util.Queue;

public class SystemTaskQueueSimulation {

    public static void main(String[] args) {

        Queue<Integer> taskQueue = new ArrayDeque<>();

        System.out.println("-----初始化任务队列-----");
        for (int i = 1; i <= 5; i++) {
            int taskId = i * 10;
            taskQueue.offer(taskId);
            System.out.println("插入任务" + taskId);
        }

        System.out.println("-----开始遍历任务队列，添加任务，删除任务-----");
        System.out.println("首先插入一个任务");
        taskQueue.offer(60);    //添加一个任务

        System.out.println("当前任务队列中队列首：" + taskQueue.peek());
        int task1 = taskQueue.poll();    //删除队列首的第一个任务
        System.out.println("删除成功，删除任务" + task1);
        System.out.println("当前任务队列中队列首：" + taskQueue.peek());

        System.out.println("再插入两个任务");
        taskQueue.offer(70);
        taskQueue.offer(80);
        System.out.println("当前任务队列中队列首：" + taskQueue.peek());

        int task2 = taskQueue.poll();    //删除队列首的第一个任务
        System.out.println("删除成功，删除任务" + task2);
        System.out.println("当前任务队列中队列首：" + taskQueue.peek());

        System.out.println("再插入两个任务");
        taskQueue.offer(90);
        taskQueue.offer(100);
        System.out.println("当前任务队列中队列首：" + taskQueue.peek());
    }
}

在上述程序中，使用ArrayDeque实现了一个双端队列，循环添加5个任务到任务队列中。接着，我们向任务队列中再添加一个任务，查看队列中的任务顺序，删除队列首的第一个任务，再查看队列中的任务顺序，最后再插入两个任务观察队列中的任务顺序变化。