# 队列
- 队列：先进先出；队列跟栈一样，也是一种操作受限的线性表数据结构。
- 基本操作：入队 `enqueue()`——放一个数据到队列尾部，出队 `dequeue()`——从队列头部取一个元素
- 某些额外特性的队列，比如循环队列、阻塞队列、并发队列。
    - Disruptor、Linux 环形缓存，都用到了循环并发队列；Java concurrent 并发包利用 ArrayBlockingQueue 来实现公平锁等。
    
# 队列的实现
- 基于数组的顺序队列
    - 固定大小的数组，`head`指针指向对头，`tail`指针指向队尾，入队与出队时，两个指针都会持续后移；
    - 多次入队出队操作后，当`tail`指针指向数组最右边，而`head`指针并不指向数组最左边时，无法再进行入队操作
    - 数据搬移，将数据整体搬移到数组最左边
    
- 基于链表的链式队列
    - 同样需要`head`和`tail`指针，入队时，`tail.next = new_node, tail = tail.next`，出队时，`head = head.next`

- 循环队列        
    - 数组来实现队列的时候，在 `tail==n` 时，会有数据搬移操作
    - 循环队列，入队时 `tail=(tail+1)%n`，即当`tail==n`时，入队操作`tail`的值变为0，即数组的开头
    - 循环队列会出现，`head`索引在数组中的位置位于`tail`索引后
    
# 队列的实际应用
- 阻塞队列：在队列的基础上增加了阻塞操作。
    - 当队列为空时，从队头取数据会被阻塞，直到队列中有数据了才返回；当队列已满，插入数据的操作会被阻塞，直到队列有空闲位置
    - 阻塞队列实现“生产者-消费者模型”，可以有效的协调生产和消费的速度
    
- 并发队列：多个线程同时操作队列，如何保证线程安全？
    - 最直接的实现方法是直接在入队、出队方法上加上锁，但锁粒度大并发度会比较低
    
- 线程池没有空闲线程时，新的任务请求线程资源时，线程池该如何处理？  
    - 非阻塞的处理方式，直接拒绝任务请求
    - 阻塞的处理方式，将请求排队，等到有空闲线程时，取出排队的请求继续处理
        - 基于链表， 实现一个支持无限排队的无界队列（`unbounded queue`）， 可能会导致过多的请求排队等待，请求处理的响应时间过长。所以，针对响应时间比较敏感的系统，基于链表实现的无限排队的线程池是不合适的。
        - 基于数组实现的有界队列（`bounded queue`），队列的大小有限，所以线程池中排队的请求超过队列大小时，接下来的请求就会被拒绝，这种方式对响应时间敏感的系统来说，就相对更加合理
        
- 对于大部分资源有限的场景，当没有空闲资源时，基本上都可以通过“队列”这种数据结构来实现请求排队，比如数据库连接池等。       
    
# LeetCode：队列