Queue
Queue
队列是一种FIFO( First In First Out)型的线性结构
Queue的实现类有LinkedList和PriorityQueue。最常用的实现类是LinkedList
Queue queue = new LinkedList();
// add() 和 remove() 在失败时会抛出异常
// 添加元素
queue.offer(1);
// 删除元素
queue.poll();
// 查看队首元素
queue.peek();
// 获取队列长度
queue.size()
Deque
普通队列可以从队尾添加元素，从队首删除元素，而**双端队列( double ended queue )**可以在两头进行添加和删除
示例
Deque deque = new LinkedList();
// add() 和 remove() 在失败时会抛出异常
// 添加元素
deque.offerFirst(1);
deque.offerLast(1);
// 删除元素
deque.pollFirst();
deque.pollLast();
// 查看元素
deque.peekFirst();
deque.peekLast();
// 获取队列长度
deque.size()
Deque的堆栈操作
Java堆栈的Stack已经过时，官方推荐使用Deque替代Stack使用
Deque的堆栈操作方法：
- push() : 等效于addFirst()
- pop() : 等效于removeFirst()
- peek() : 等效于peekFirst()
Priority queue
PriorityQueue，即优先队列。优先级队列可以保证每次取出来的元素都是队列中的最小或最大的元素（Java优先级队列默认每次取出来的为最小元素）
大小关系： 元素的比较可以通过元素本身进行自然排序，也可以通过构造方法传入比较器进行比较
时间复杂度
PriorityQueue的peek和element操作的时间复杂度都为常数，add、offer、remove以及poll的时间复杂度是log(n)
Comparable比较器
// Comparable接口
public interface Comparable<T> {
public int compareTo(T o);
}
该接口只存在一个public int compareTo(T o);方法，该方法表示所在的对象和o对象进行比较，返回值分三种：
- 1： 表示当前对象大于o对象
- 0： 表示当前对象等于o对象
- -1： 表示当前对象小于o对象
在优先级队列中或者具有比较特征的集合中存储的对象需要实现Comparable接口
示例
public class Student implements Comparable{
private int id;
private String name;
private int age;
public Student(int id, String name, int age) {
this.id = id;
this.name = name;
this.age = age;
}
public int getId() {
return id;
}
@Override
public int compareTo(Object o) {
Student o1 = (Student)o;
return this.id - o1.id;
}
}
public class PriorityQueueTest {
public static void main(String[] args) {
PriorityQueue<Student> queue = new PriorityQueue<>();
queue.add(new Student(2,"王昭君",18));
queue.add(new Student(1,"吕布",19));
queue.add(new Student(5,"貂蝉",17));
queue.add(new Student(3,"赵云",20));
queue.add(new Student(4,"荆轲",18));
System.out.println(queue.remove());
System.out.println(queue.remove());
System.out.println(queue.remove());
System.out.println(queue.remove());
System.out.println(queue.remove());
}
}
Comparator比较器
// Comparator接口
public interface Comparator<T> {
int compare(T o1, T o2);
}
该接口中提供了int compare(T o1, T o2)方法，该方法需要参数是两个待比较的对象 返回结果是int类型
- 1： 表示o1对象大于o2对象
- 0： 表示o1对象等于o2对象
- -1: 表示o1对象小于o2对象
示例
PriorityQueue<Student> queue = new PriorityQueue<>(new Comparator<Student>() {
@Override
public int compare(Student o1, Student o2) {
return o2.getId() - o1.getId();
}
});
底层原理
优先队列的底层是以一个小顶堆或大顶堆的数组结构来维护的，这样来保证每次取出的元素为最大或最小
- 小顶堆（任意一个非叶子节点的权值，都不大于其左右子节点的权值）
- 大顶堆（任意一个非叶子节点的权值，都大于其左右子节点的权值）
父节点与子节点的编号关系
- leftNo = parentNo * 2 + 1;
- rightNo= parantNo * 2 + 2;
- parentNo = (nodeNo - 1) / 2;