数据结构：队列

---

队列

一，概述

队列是一种特殊的数据结构，它遵循先进先出（FIFO）的原则。在队列中，元素被添加到末尾，并从头部移除。队列只允许在一端进行插入操作，而在另一端进行删除操作。

队列可以形象地理解为排队买票：先来的人先买票，后来的人只能在队伍末尾等待，不允许插队。同样地，队列中的元素也是先来的先被移除。

队列的基本操作包括：

1. 入队（enqueue）：在队列的末尾添加一个元素。
2. 出队（dequeue）：从队列的头部移除一个元素。
3. 判断队列是否为空（isEmpty）。
4. 查看队头元素（front）：返回队列头部的元素但不移除它。
5. 查看队列长度（size）。

队列可以通过数组或链表来实现。在数组中，当队列满时，数组的尾指针指向下一个可用的空间；在链表中，当队列满时，最后一个节点的next指针指向下一个可用的空间。

需要注意的是，在使用队列时，必须保证队列不被溢出。在队列为空时，必须避免进行出队操作；在队列已满时，必须避免进行入队操作。可以通过一些策略来避免这种情况，例如使用循环队列或使用两个指针来分别指示队列的头部和尾部。

总之，队列是一种常见的数据结构，它广泛应用于各种场景，如生产者-消费者问题、缓冲区处理等等。掌握队列的基本概念和操作方法对于数据结构和算法的学习非常有帮助。

简介：

• 队列是一种特殊的线性表，具有特殊的添加和删除规则。
• 队列只允许在表的后端添加元素，而在前端删除元素。
• 队列中的元素按照添加的顺序排列，即先添加的元素在队列的前端，后添加的元素在队列的后端。

图示：

  Rear                       Front
   +----+----+----+----+    +----+----+
   | 1  | 2  | 3  | 4  |    | 5  | 6  |
   +----+----+----+----+    +----+----+
1
2
3
4

在上面的队列示例中，元素1、2、3、4是按照添加的顺序排列的。新添加的元素5和6被添加到队列的后端。当元素被删除时，最前端的元素（这里是元素1）将被首先删除。

Java示例：

在Java中，可以使用java.util.Queue接口来实现队列。Queue接口有很多实现，例如LinkedList、ArrayDeque等。以下是一个简单的示例：

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

public class QueueExample {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();

        // 添加元素到队列
        queue.add(1);
        queue.add(2);
        queue.add(3);
        queue.add(4);
        System.out.println("Initial Queue: " + queue);

        // 删除元素（队头元素）
        System.out.println("Removed element: " + queue.remove());
        System.out.println("Queue after removal: " + queue);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

在这个示例中，首先创建了一个整数类型的队列，然后使用add方法向队列中添加元素。接着，使用remove方法删除队列的前端元素。

二，添加数据

在Java中，使用java.util.Queue接口可以实现队列数据结构。Queue接口提供了一种方法来添加元素到队列的尾部，这种方法叫做add()。

以下是一个简单的示例，演示如何使用Queue接口和LinkedList类来实现队列，并向队列中添加元素：

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

public class Main {
    public static void main(String[] args) {
        // 创建一个新的队列
        Queue<String> queue = new LinkedList<>();

        // 向队列添加元素
        queue.add("元素1");
        queue.add("元素2");
        queue.add("元素3");

        // 打印队列的元素
        for (String element : queue) {
            System.out.println(element);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

在上述代码中，首先导入了Queue和LinkedList类。然后，创建了一个新的Queue对象，并使用add()方法向队列添加了三个元素。最后，用一个for-each循环来遍历并打印队列中的每个元素。

当运行这个程序时，它会按照它们被添加到队列的顺序（即先进先出，或FIFO）打印出这三个元素。

三，删除数据

在Java中，队列（Queue）数据结构的删除操作主要有两种：出队（remove()）和删除指定元素（remove(Object o)）。以下是一个示例：

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

public class Main {
    public static void main(String[] args) {
        // 创建一个新的队列
        Queue<String> queue = new LinkedList<>();

        // 向队列添加元素
        queue.add("元素1");
        queue.add("元素2");
        queue.add("元素3");

        // 出队操作，删除并返回队列的头部元素
        String removedElement = queue.remove();
        System.out.println("被删除的元素是：" + removedElement);
        System.out.println("队列中的元素是：" + queue);

        // 删除指定元素操作
        boolean isRemoved = queue.remove("元素2");
        System.out.println("是否删除成功：" + isRemoved);
        System.out.println("队列中的元素是：" + queue);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

在这个例子中，首先创建了一个队列并添加了一些元素。然后，使用 remove() 方法进行出队操作，这个方法会删除并返回队列的头部元素。接着，使用 remove(Object o) 方法来删除指定的元素。这个方法会尝试删除队列中的第一个出现的指定元素，并返回一个布尔值表示是否删除成功。