队列：队列在线程池等有限资源池中的应用

1.理解队列？ 典型队列，先进者先出的结构，是一种操作受限的线性数据结构。 队列类似栈，基本操作也有两个，入列（尾部插入数据）和出列（头部取出数据）   2.实现队列的方式 类似栈，也可以使用数组和链表来实现队列， 顺序队列：使用数组来实现队列 // 用数组实现的队列 public class ArrayQueue {   // 数组：items，数组大小：n   private String[] items;   private int n = 0;   // head 表示队头下标，tail 表示队尾下标   private int head = 0;   private int tail = 0;   // 申请一个大小为 capacity 的数组   public ArrayQueue(int capacity) {     items = new String[capacity];     n = capacity;   }     // 入队   public boolean enqueue(String item) {     // 如果 tail == n 表示队列已经满了     if (tail == n) return false;     items[tail] = item;     ++tail;     return true;   }   // 出队   public String dequeue() {     // 如果 head == tail 表示队列为空     if (head == tail) return null;     // 为了让其他语言的同学看的更加明确，把 -- 操作放到单独一行来写了     String ret = items[head];     ++head;     return ret;   } } 队列需要两个指针，一个队头指针head，一个队尾指针tail。当发生入队操作，tail指针后移。发生出队操作，head指针后移。 随着入队出队操作的多次进行，head指针和tail指针都会后移，当tail指针后移到数组末尾，即使数组中有空间，队列也无法进行入队操作。 可以通过数据迁移来实现对于指针的管理，但没有必要每次出队都进行数据迁移，这样做会使出队的复杂度变为O(n)。 可以在入队时判断，如果容量不足则进行一次数据迁移或者动态扩容。 这样做，时间复杂度接近于O(1)。 链式队列： 使用链表来实现队列，也需要两个指针。 一个队头指针head，一个队尾指针tail。   循环队列： 使用循环队列可以避免数据迁移。 具体实现中，假设数组有10个长度，当tail=9时，进行入队操作，这个时候tail不进行+1，而是=0。 注意：编写循环队列代码要注意确定好队空和队满的判定条件。 如图中的队满情况，head=4，tail=3，n=8  总结规律可以得到  (tail+1)%n=head 可以看到，循环队列在队满的情况下，tail指针的位置是没有数据的，也就是说，循环队列会浪费一个内存空间。 public class CircularQueue {   // 数组：items，数组大小：n   private String[] items;   private int n = 0;   // head 表示队头下标，tail 表示队尾下标   private int head = 0;   private int tail = 0;   // 申请一个大小为 capacity 的数组   public CircularQueue(int capacity) {     items = new String[capacity];     n = capacity;   }   // 入队   public boolean enqueue(String item) {     // 队列满了     if ((tail + 1) % n == head) return false;     items[tail] = item;     tail = (tail + 1) % n;     return true;   }   // 出队   public String dequeue() {     // 如果 head == tail 表示队列为空     if (head == tail) return null;     String ret = items[head];     head = (head + 1) % n;     return ret;   } } 阻塞队列和并发队列： 阻塞队列就是在队列基础上增加了阻塞操作。当队列中没有数据，会先阻塞，等到队列中插入了数据再取出数据并返回。当队满时也是一样，会等到队列中有空位，才插入数据并且返回。 事实上，上述定义就是一个生产者消费者模型。我们可以使用阻塞队列轻松实现一个生产者消费者模型。可以通过调整生产者消费者的数量来优化模型，比如配置多个消费者来应对一个生产者。 并发队列：线程安全的队列 最简单直接的方式实在入队出队方法上加锁，但锁粒度太低会导致并发度降低。 可以使用循环队列，利用cas原子操作实现高效的并发队列，这也是为什么循环队列比链式队列应用更加广泛。 对于大部分资源有限的场景，当没有空闲资源时，基本上都可以使用队列来实现请求排队。 队列的应用非常广泛，特别是一些具有某些额外特性的队列，比如循环队列、阻塞队列、并发队列。它们在很多偏底层的系统、框架、中间件的开发中，起着关键性的作用。比如高性能队列 Disruptor、Linux 环形缓存，都用到了循环并发队列；Java concurrent 并发包利用 ArrayBlockingQueue 来实现公平锁等。 思考： 1.除了线程池这种池结构会用到队列排队请求，你还知道有哪些类似的池结构或者场景中会用到队列的排队请求呢？ 消息队列，如kafka等 2.今天讲到并发队列，关于如何实现无锁并发队列，网上有非常多的讨论。对这个问题，你怎么看呢？ 使用cas原子操作+数组循环队列 考虑使用CAS实现无锁队列，则在入队前，获取tail位置，入队时比较tail是否发生变化，如果否，则允许入队，反之，本次入队失败。出队则是获取head位置，进行cas。

原文链接:https://www.cnblogs.com/wangzepu/p/11369014.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有