队列.md

线程池中有限资源请求队列 功能的实现原理

队列在线程池中的应用

线程池的源码 ThreadPoolExecutor

private final BlockingQueue<Runnable> workQueue;//阻塞队列

private final ReentrantLock mainLock = new ReentrantLock();//互斥锁
private final HashSet<Worker>workers = new HashSet<Worker>();//线程集合,一个Worker对应一个线程
private final Condition termination = mainLock.newCondition();//终止条件
private int largestPoolSize;//线程池中线程数量曾经达到过的最大值
private long completedTaskCount;//已完成任务数量
private volatile ThreadFactory threadFactory;//ThreadFactory对象，用于创建线程，
private volatile RejectedExecutionHandler handler;//拒绝策略的处理句柄
private volatile long keepAliveTime; //线程池维护线程所允许的空闲时间
private volatile boolean allowCoreThreadTime0ut;

private volatile int corePoolsize;//线程池维护线程的最小数量,哪怕是空闲的
private volatile int maximumPoolSize;//线程池维护的最大线程数量

线程池会维护corePoolSize个线程，如何还有线程需要执行，就先往workQueue阻塞队列里面放，如果这个队列里面满了，将将线程放在线程池中，如果线程池中超过了maximumPoolSize最大个数，则会抛弃这个线程

队列的基本原理

队列在缓存中应用最多

生产者消费者模式，经常用队列，如Handler机制

队列（queue）又叫先进先出表，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和另一端取数据。插入数据的一端是队尾，取数据的一端则是队头。

假溢出（False Overflow） 指的是在队列的存储空间中，虽然还有空闲位置，但由于队列的指针或索引已经到达存储空间的末尾，导致无法继续插入新元素的现象。

（指针指向的是第一个要执行任务的对象，而不是空闲的对象）

（例如有五个人在排队，后面排满了，前面排队的两个人走了，但是队尾后面的不知道）

---

为了解决假溢出问题，通常采用 循环队列（Circular Queue） 的实现方式。

循环队列的核心思想：

• 将数组视为一个环形结构，当队尾指针 Rear 到达数组末尾时，可以绕回到数组的开头继续使用空闲空间。
• 通过取模运算实现指针的循环移动。

假设循环队列总容量为N，并且预留一个空的位置作为队列空，满，长度判断标志：

• 队列空：front==rear;
• 队列满：(rear+1)%N==front;
• 队列元素个数：（rear – front + N)%N

---

队列存储结构-链式队列

队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已

队列变形—双端队列Deque

Deque是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行

ArrayDeque

LinkedList

队列变形——优先级队列

优先级队列和通常的栈和队列一样，只不过里面的每一个元素都有一个”优先级”，在处理的时候，首先处理优先级最高的。如果两个元素具有相同的优先级，则按照他们插入到队列中的先后顺序处理。

在工作中最最常用

MessageQueue（Android线程润滑剂）——根据时间排序

PriorityQueue

面试

假设队列大小为 10，corePoolSize 为 3，maximumPoolSize 为 6，那么当加入 20 个任务时，执行的顺序应该是怎样的？

线程池、阻塞队列

1. 首先执行任务 1、2、3，
2. 然后任务 4~13 被放入队列。
3. 这时候队列满了，任务 14、15、16 会被马上执行，
4. 而任务 17~20 则会抛出异常。
5. 最终顺序是：1、2、3、 14、15、16、 4、5、6、7、8、9、10、11、12、13。

621：任务调度器（中）https://leetcode.com/problems/number-of-recent-calls/

https://leetcode.com/problems/design-circular-deque/

https://leetcode.com/problems/task-scheduler/

Donate