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;
}
@Override
public 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>() {
@Override
public 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