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

小咪咪 2021-09-18 04:50 228阅读 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]![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;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqYXZhZG9n_size_16_color_FFFFFF_t_70 2]  
**循环队列数组示例代码**

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;
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqYXZhZG9n_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191202222259278.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqYXZhZG9n,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqYXZhZG9n_size_16_color_FFFFFF_t_70 1]: /images/20210918/5e2c53698e024ce091e2077255a4d688.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqYXZhZG9n_size_16_color_FFFFFF_t_70 2]: /images/20210918/550e4925b2f04d2db706702144668cf7.png