数据结构 - 队列（精简介绍）

单端队列

普通队列为单端队列，先进先出（FIFO）

只能从尾部插入，头部取出元素

省流图：

单端队列操作：Queue实现

Queue<Integer> queue = new LinkedList<>();
// 添加元素到队列的尾部
queue.offer(1);
queue.offer(2);
// 获取并移除队列的头部元素
int head = queue.poll();
// 获取但不移除队列的头部元素
int peek = queue.peek();
// 判断队列是否为空
boolean isEmpty = queue.isEmpty();
// 获取队列的大小
int size = queue.size();
1
2
3
4
5
6
7
8
9
10
11
12

双端队列

单端队列升级版，允许在队头和队尾都进行元素的插入删除操作

双端队列操作：Deque实现

Deque<Integer> deque = new ArrayDeque<>();
// 添加元素到双端队列的尾部
deque.offerLast(1);
deque.offerLast(2);
// 添加元素到双端队列的头部
deque.offerFirst(0);
// 获取并移除双端队列的头部元素
int head = deque.pollFirst();
// 获取并移除双端队列的尾部元素
int tail = deque.pollLast();
// 获取但不移除双端队列的头部元素
int peekHead = deque.peekFirst();
// 获取但不移除双端队列的尾部元素
int peekTail = deque.peekLast();
// 判断双端队列是否为空
boolean isEmpty = deque.isEmpty();
// 获取双端队列的大小
int size = deque.size();
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

循环队列

循环队列（Circular Queue），也称为环形队列，是一种队列数据结构，它将队列的最后一个位置连接到队列的第一个位置，使其形成一个环。在循环队列中，队列的前端和后端都可以绕回到数组的起始位置，从而有效利用数组的空间。

循环队列具有以下特点：

1. 固定大小：循环队列的大小是固定的，一旦创建后就不能改变。
2. 环绕：当到达数组的末尾时，指针将绕回到数组的起始位置。
3. 满队列和空队列的区别：为了区分队列为空还是满，通常保留一个数组位置不使用，或者使用一个额外的变量来记录队列的大小。

循环队列手动实现

public class CircularQueue {
    private int[] queue;
    private int front;
    private int rear;
    private int size;
    private int capacity;

    public CircularQueue(int capacity) {
        this.capacity = capacity;  // 队列容量（一般大小固定）
        this.queue = new int[capacity];
        this.front = 0; // 前端索引
        this.rear = 0;  // 后端索引
        this.size = 0;  // 队列中元素个数
    }

    public boolean isFull() {
        return size == capacity;
    }

    public boolean isEmpty() {
        return size == 0;
    }

	// 入队
    public boolean enqueue(int item) {
        if (isFull()) {
            System.out.println("队列为空");
            return false;
        }
        queue[rear] = item;
        rear = (rear + 1) % capacity; // 后端指针往后移，循环队列要取余
        size++;
        return true;
    }

	// 出队
    public Integer dequeue() {
        if (isEmpty()) {
            System.out.println("队列为空");
            return null;
        }
        int item = queue[front];
        front = (front + 1) % capacity;
        size--;
        return item;
    }

    public void display() {
        if (isEmpty()) {
            System.out.println("队列为空");
            return;
        }
        for (int i = 0; i < size; i++) {
            System.out.print(queue[(front + i) % capacity] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        CircularQueue cq = new CircularQueue(5);

        cq.enqueue(1);
        cq.enqueue(2);
        cq.display();
        
        cq.dequeue();
        cq.display();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

优先级队列

本质上是大/小根堆，队列中元素会根据某种规则进行优先级排序

• 利用PriorityQueue，比较器Comparator 中指定 比较/排序 规则

Q 不断取最大礼物并开方

2558. 从数量最多的堆取走礼物 - 力扣（LeetCode）

public long pickGifts(int[] gifts, int k) {
    // 队列从头最大到尾最小，降序排序
    PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> o2 - o1);
    for (int i = 0; i < gifts.length; i++) {
        pq.offer(gifts[i]);
    }
    // 关键步骤：取出最大数，开方，再放进去，重复k次
    for (int i = 0; i < k; i++) {
        int max = pq.poll();
        pq.offer((int)Math.sqrt(max)); // 由于是优先级队列，再放入元素后会自动重新排序的
    }
    long res = 0;
    while (!pq.isEmpty()){
        res += pq.poll();
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17