❤️ 普通队列

[!quote] 队列的规则是先入先出，【假如公路上有一条单行隧道，所有通过隧道的车辆只允许从隧道入口驶入，从隧道出口驶出，不允许逆行，因此，要想让车辆驶出隧道，只能按照它们驶入隧道的顺序。先驶入的车辆先驶出，后驶入的车辆后驶出，任何车辆都无法跳过它前面的车辆提前驶出】

• 在多线程中，争夺公平锁的等待队列
• 网络爬虫实现网站抓取，把抓取的网站 URL 存入队列中，再按照存入队列的顺序来依次抓取和解析

数组实现

public class ArrayQueue {  
    private int maxSize;     // 队列最大容量  
    private int front;     // 队列头指针  
    private int rear;     // 队列尾指针  
    private int[] arr;     // 存储数据的数组

	public ArrayQueue(int maxSize) {     //初始化队列  
	    this.maxSize = maxSize;  
	    arr = new int[maxSize];  
	}
	
	public boolean isFull() { // 判断队列是否满  
	    return rear == maxSize;  
	}  
	  
	public boolean isEmpty() { // 判断队列是否空  
	    return front == rear;  
	}
}

入队

public void addQueue(int data) { // 入队操作
	if (isFull()) {
		System.out.println("队列已满，无法添加数据");
		return;
	}
	arr[rear] = data; // 将数据存入数组中
	rear++; // 尾指针后移一位
}

出队

public int getQueue() { // 出队操作
	if (isEmpty()) {
		throw new RuntimeException("队列为空，无法取出数据");
	}
	int temp = arr[front];
	front++;        // 头指针后移一位
	return temp;
}

---

[!hint] 这样入队出队，数组左边的空间会很浪费，所以我们会在数组右侧满了的时候，将队尾放置在数组的开始

// 改进版的入队
public void addQueue(int data) { // 入队操作
	if (isFull()) {
		System.out.println("队列已满，无法添加数据");
		return;
	}
	arr[rear] = data; // 将数据存入数组中
	rear = (rear + 1) % arr.length;
}

// 改进版的出队
public int getQueue() { // 出队操作
	if (isEmpty()) {
		throw new RuntimeException("队列为空，无法取出数据");
	}
	int temp = arr[front];
	front = (front +1 ) % arr.length;    
	return temp;
}

遍历

public void showQueue() { // 遍历打印队列中元素
	if (isEmpty()) {
		System.out.println("队列为空，没有数据");
		return;
	}
	for (int i = front; i != rear; i = (i + 1) % arr.length) {
		System.out.println(arr[i]);
	}
}

[!hint] 扩容 参照数组

链表实现

双端队列

[!quote] 双端队列 双端队列综合了栈，和队列的优点

优先队列

[!quote] 优先队列

优先队列 使用二叉堆，因为用线性的数据结构来实现复杂度较高，最大堆，最小堆刚好对应最大，最小优先队列

优先队列分为：

• 最大优先队列：无论入队顺序如何，都是当前最大的元素优先出队
• 最小优先队列：无论入队顺序如何，都是当前最小的元素优先出队

最大优先队列

• 最大优先队列的插入，就是最大堆的上浮
• 最大优先队列的删除，就是最大堆的下沉

插入

删除

最小优先队列