Day5 队列：队列在有限线程池资源中的使用-向日葵屋

Day5 队列：队列在有限线程池资源中的使用

小咪咪 2021-09-18 04:50 230阅读 0赞

主题：队列在有限线程池资源中的使用

问：什么是队列？
答：先进先出 FIFO，和栈一样，是一种操作受限的线性表数据结构
问：队列的操作？
答：入栈和出栈
问：有哪些队列？
答：
    1. 循环队列
    2. 阻塞队列
    3. 并发队列
问：队列的实现方式？
答：链表和数组

基于链表的实现方式，可以实现一个支持无限排队的无界队列（unbounded queue），但是可能会导致过多的请求排队等待，请求处理的响应时间过长。所以，针对响应时间比较敏感的系统，基于链表实现的无限排队的线程池是不合适的。

而基于数组实现的有界队列（bounded queue），队列的大小有限，所以线程池中排队的请求超过队列大小时，接下来的请求就会被拒绝，这种方式对响应时间敏感的系统来说，就相对更加合理。不过，设置一个合理的队列大小，也是非常有讲究的。队列太大导致等待的请求太多，队列太小会导致无法充分利用系统资源、发挥最大性能。

队列实现示例：

数组
public class ArrayQueue {
    private String[] items;
    private int n;
    private int tail;
    private int head;
    public ArrayQueue(int capacity) {
        items = new String[capacity];
        this.n = capacity;
    }
    // 入队
    public boolean enqueue(String item) {
        // 判断队列是否已满
        if(tail == n) return false;
        items[tail] = item;
        tail ++;
        return true;    
    }
    // 出队
    public String dequeue() {
        // 判断是否有数据
        if (head == tail) return null;
        String tmp = items[head];
        head++;
        return tmp;
    }
}

如下两幅图所示，当tail=7的时候，即使有空闲的空间，以上代码就无法添加了，需要重新搬移数据。

在这里插入图片描述 watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqYXZhZG9n_size_16_color_FFFFFF_t_70 1
那只需要修改入队代码：

// 入队操作
public boolean enqueue（String item） {
    // 表示 tail 已经到达数组终点，需要搬移数据了
    if (tail == n) {
        // 判断数组是否还有空间，如果没有了，返回 false
        if (head == 0) return false;
        // 如果还有空间，将head到tail这段数据进行搬移
        for(int i=head;i<tail;i++) {
            items[i-head] = items[i];
            head = 0;
            tail = tail - head;
        }
    }
    items[tail] = item;
    tail++;
    return true;
}

在这里插入图片描述
循环队列数组示例代码

public class CircularQueue {
    private String[] items;
    private int n;
    private int head;
    private int tail;
    public CircularQueue(int capacity) {
        items = new String[capacity];
        this.n = capacity;
    }
    // 入队
    public boolean enqueue(String item) {
        // 先判断队列是否已满
        if((tail+1) % n == head) return false;
        items[tail] = item;
        tail ++;
        return true;
    }
    // 出队
    public String dequeue() {
        // 判断队列是否为空
        if(tail == head) return null;
        String tmp = items[head];
        head = (head+1) % n;
        return tmp;
    }
}