Java算法 数据结构 栈 队列 优先队列 比较器

目录

栈 Stack

性质

构造

方法

代码示例

队列 Queue

性质

构造

方法

代码示例

优先队列 PriorityQueue

性质

构造

方法

代码示例

比较器

1. Comparator 接口的方法

2. 常见的内置比较器

1. 自然排序比较器（naturalOrder()）

2. 逆序排序比较器（reverseOrder()）

3. nullsFirst() 和 nullsLast()

3. 示例：常用的比较器

自定义类使用 Comparator 排序

输出：

4. 多重排序

5. 使用 Comparator 的常见场景

1. PriorityQueue

2. Collections.sort()

3. Arrays.sort()

6. 自定义比较器的实现方式

1. 使用匿名类实现 Comparator：

2. 使用 Lambda 表达式实现 Comparator（推荐）：

3. 使用方法引用实现 Comparator：

7. 总结

---

栈 Stack

性质

后进先出

可以弹出栈顶元素 或者返回栈顶元素(不删除)

后压入栈的元素先出来

构造

• 创建栈对象：

Stack<Integer> stack = new Stack<>(); 创建了一个类型为 Integer 的栈。

方法

• push()：将元素压入栈中。
• peek()：查看栈顶元素，但不移除它。
• pop()：移除并返回栈顶元素。
• size()：获取栈中元素的数量。
• isEmpty()：判断栈是否为空。

代码示例

import java.util.Stack;public class StackExample {public static void main(String[] args) {// 创建一个栈对象Stack<Integer> stack = new Stack<>();// 入栈stack.push(10);stack.push(20);stack.push(30);// 查看栈顶元素System.out.println("栈顶元素: " + stack.peek());// 出栈System.out.println("出栈元素: " + stack.pop());System.out.println("栈顶元素: " + stack.peek());// 查看栈的大小System.out.println("栈的大小: " + stack.size());// 判断栈是否为空if (stack.isEmpty()) {System.out.println("栈为空");} else {System.out.println("栈不为空");}}
}

队列 Queue

先进先出

可以移除队列头部元素 并且获取这个元素

也可以获取队列头部元素(不删除)

先进入队列的元素先出来

性质

构造

Queue<Integer> queue = newLinkedList<>();

创建了一个类型为 Integer 的队列。

方法

• offer(E e)：将元素 e 加入队列，若队列没有满（在 LinkedList 实现中，offer() 通常会成功）。
• peek()：返回队列头部元素，但不删除它。若队列为空，返回 null。
• poll()：移除并返回队列头部的元素。如果队列为空，返回 null。
• size()：获取队列中的元素个数。
• isEmpty()：判断队列是否为空。

代码示例

import java.util.Queue;
import java.util.LinkedList;public class QueueExample {public static void main(String[] args) {// 创建一个队列对象Queue<Integer> queue = new LinkedList<>();// 入队queue.offer(10);queue.offer(20);queue.offer(30);// 查看队列头部元素System.out.println("队列头部元素: " + queue.peek());// 出队System.out.println("出队元素: " + queue.poll());System.out.println("队列头部元素: " + queue.peek());// 查看队列的大小System.out.println("队列的大小: " + queue.size());// 判断队列是否为空if (queue.isEmpty()) {System.out.println("队列为空");} else {System.out.println("队列不为空");}}
}

优先队列 PriorityQueue

性质

PriorityQueue 是一个优先级队列，它会按照元素的自然顺序或指定的比较器排序。在 PriorityQueue 中，出队的顺序是根据元素的优先级（大小或比较器的排序规则）来决定的。

构造

PriorityQueue<Integer> priorityQueue = newPriorityQueue<>();

方法

• add(E e)：将元素 e 插入到队列中。如果队列已满（取决于实现的容量限制），则抛出异常。
• offer(E e)：将元素 e 插入队列。如果队列容量已满，则返回 false，不会抛出异常。这个方法通常更安全，推荐使用。
• poll()：移除并返回队列头部的元素（优先级最高的元素）。如果队列为空，返回 null。
• peek()：返回队列头部的元素（优先级最高的元素），但不移除它。如果队列为空，返回 null。
• remove()：移除队列中的一个元素。通常情况下，poll() 是更常用的出队操作。
• size()：返回队列中元素的个数。
• isEmpty()：检查队列是否为空。
• clear()：清空队列中的所有元素。

代码示例

import java.util.PriorityQueue;public class PriorityQueueExample {public static void main(String[] args) {// 创建一个优先级队列对象PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();// 入队priorityQueue.offer(30);priorityQueue.offer(10);priorityQueue.offer(20);// 查看队列头部元素System.out.println("队列头部元素: " + priorityQueue.peek());// 出队System.out.println("出队元素: " + priorityQueue.poll());System.out.println("队列头部元素: " + priorityQueue.peek());// 查看队列的大小System.out.println("队列的大小: " + priorityQueue.size());}
}

比较器

1. Comparator 接口的方法

Comparator 接口包含以下几个方法：

• compare(T o1, T o2)：比较 o1 和 o2，如果返回值为负数，则 o1 排在 o2 之前；如果返回值为零，则 o1 和 o2 相等；如果返回值为正数，则 o1 排在 o2 之后。
• reversed()：返回一个与当前比较器顺序相反的比较器。
• thenComparing(Comparator<? super T> other)：如果 compare() 方法返回 0，则继续使用另一个比较器 other 进行比较。
• naturalOrder()：返回一个自然排序的比较器（升序）。
• reverseOrder()：返回一个逆序排序的比较器（降序）。
• nullsFirst() / nullsLast()：处理 null 值的排序，nullsFirst() 会将 null 值排在前面，nullsLast() 会将 null 值排在后面。

2. 常见的内置比较器

1. 自然排序比较器（naturalOrder()）

Comparator.naturalOrder() 返回一个自然排序的比较器，通常是升序排序。适用于实现了 Comparable 接口的对象。

java复制代码
Comparator<Integer> naturalOrder = Comparator.naturalOrder();

2. 逆序排序比较器（reverseOrder()）

Comparator.reverseOrder() 返回一个降序排序的比较器。

java复制代码
Comparator<Integer> reverseOrder = Comparator.reverseOrder();

3. nullsFirst() 和 nullsLast()

这两个方法用来处理 null 值的排序：

• nullsFirst()：将 null 值排在前面。
• nullsLast()：将 null 值排在后面。

java复制代码
Comparator<String> nullsFirst = Comparator.nullsFirst(Comparator.naturalOrder());
Comparator<String> nullsLast = Comparator.nullsLast(Comparator.naturalOrder());

3. 示例：常用的比较器

自定义类使用 Comparator 排序

假设我们有一个 Person 类，包含 name 和 age 字段，我们可以根据不同的字段排序。

java复制代码
import java.util.*;class Person {String name;int age;Person(String name, int age) {this.name = name;this.age = age;}@Overridepublic String toString() {return name + ": " + age;}
}public class ComparatorExample {public static void main(String[] args) {List<Person> people = Arrays.asList(new Person("Alice", 30),new Person("Bob", 25),new Person("Charlie", 35));// 按年龄升序排序Comparator<Person> byAge = Comparator.comparingInt(p -> p.age);Collections.sort(people, byAge);System.out.println("按年龄升序排序：" + people);// 按名字升序排序Comparator<Person> byName = Comparator.comparing(p -> p.name);Collections.sort(people, byName);System.out.println("按名字升序排序：" + people);// 按年龄降序排序Comparator<Person> byAgeDesc = Comparator.comparingInt(Person::getAge).reversed();Collections.sort(people, byAgeDesc);System.out.println("按年龄降序排序：" + people);}
}

输出：

yaml复制代码
按年龄升序排序：[Bob: 25, Alice: 30, Charlie: 35]
按名字升序排序：[Alice: 30, Bob: 25, Charlie: 35]
按年龄降序排序：[Charlie: 35, Alice: 30, Bob: 25]

4. 多重排序

如果我们希望对多个属性进行排序，可以使用 thenComparing() 方法。例如，按 age 排序，如果年龄相同，则按 name 排序：

java复制代码
Comparator<Person> byAgeThenName = Comparator.comparingInt(Person::getAge).thenComparing(Person::getName);Collections.sort(people, byAgeThenName);

5. 使用 Comparator 的常见场景

1. PriorityQueue

在使用 PriorityQueue 时，你可以通过传递自定义的 Comparator 来指定队列中的优先级顺序。例如，按降序排列整数：

java复制代码
PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
pq.offer(10);
pq.offer(20);
pq.offer(30);while (!pq.isEmpty()) {System.out.println(pq.poll());  // 输出：30, 20, 10
}

2. Collections.sort()

你可以在排序时传递自定义的比较器。例如，按字符串的长度排序：

java复制代码
List<String> strings = Arrays.asList("apple", "banana", "pear", "grape");Collections.sort(strings, Comparator.comparingInt(String::length));System.out.println(strings);  // 输出：[pear, apple, grape, banana]

3. Arrays.sort()

Arrays.sort() 也可以接受一个比较器。例如，按数字的降序排列：

java复制代码
Integer[] numbers = {3, 1, 4, 1, 5, 9};
Arrays.sort(numbers, Comparator.reverseOrder());
System.out.println(Arrays.toString(numbers));  // 输出：[9, 5, 4, 3, 1, 1]

6. 自定义比较器的实现方式

1. 使用匿名类实现 Comparator：

java复制代码
Comparator<Person> byName = new Comparator<Person>() {@Overridepublic int compare(Person p1, Person p2) {return p1.name.compareTo(p2.name);}
};

2. 使用 Lambda 表达式实现 Comparator（推荐）：

java复制代码
Comparator<Person> byName = (p1, p2) -> p1.name.compareTo(p2.name);

3. 使用方法引用实现 Comparator：

java复制代码
Comparator<Person> byName = Comparator.comparing(Person::getName);

7. 总结

Java 提供了多种方式来实现比较器 Comparator，你可以：

• 使用内置的 Comparator 方法（如 naturalOrder()、reverseOrder()、nullsFirst() 等）。
• 定制比较器，使用 Comparator.comparing()、thenComparing() 等进行多重排序。
• 使用自定义 Comparator 对象来排序集合，如 PriorityQueue、Collections.sort()、Arrays.sort() 等。

通过灵活地使用这些比较器，你可以对各种类型的对象进行多样化的排序。

4o