嘉兴网站建设平台,app开发运营需要多少钱,广州论坛网站建设,机械网站模板队列定义
先进者先出#xff0c;这就是典型的“队列”。队列跟栈一样#xff0c;也是一种操作受限的线性表数据结构。
顺序队列和链式队列
顺序队列#xff1a;用数组实现的队列// 用数组实现的队列
public class ArrayQueue {// 数组#xff1a;items#xff0c;数组大…队列定义
先进者先出这就是典型的“队列”。队列跟栈一样也是一种操作受限的线性表数据结构。
顺序队列和链式队列
顺序队列用数组实现的队列// 用数组实现的队列
public class ArrayQueue {// 数组items数组大小nprivate 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;}
}
问题一经过不停的入队出队操作tail指针移动到最右边时如何处理
数据搬移每次出队操作相当于删除数组下标为0的数据搬移一次这样操作的时间复杂度为O(n)
优化方案如果没有空闲空间了我们只需要在入队时再集中触发一次数据的搬移操作。操作时间复杂度为O1
数组实现的非循环队列特征在用数组实现的非循环队列中队满的判断条件是 tail n队空的判断条件是 head tail。 // 入队操作将item放入队尾public boolean enqueue(String item) {// tail n表示队列末尾没有空间了if (tail n) {// tail n head0表示整个队列都占满了if (head 0) return false;// 数据搬移for (int i head; i tail; i) {items[i-head] items[i];}// 搬移完之后重新更新head和tailtail - head;head 0;}items[tail] item;tail;return true;}
链式队列用链表实现的队列基于链表的实现我们同样需要两个指针head 指针和 tail 指针。它们分别指向链表的第一个结点和最后一个结点。如图所示入队时tail-next new_node, tail tail-next出队时head head-next;循环队列数组来实现队列的时候在 tailn 时会有数据搬移操作如何避免数据搬移——用循环队列
循环队列的难点确定好队空和队满的判定条件
那针对循环队列如何判断队空和队满呢队列为空的判断条件仍然是 head tail。
队列满的条件(tail1)%nhead。你有没有发现当队列满时图中的 tail 指向的位置实际上是没有存储数据的。循环队列会浪费一个数组的存储空间。 循环队列的实现代码注意其中的 tail (tail 1) % n; head (head1)%n; public class CircularQueue {// 数组items数组大小nprivate 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;}
}
阻塞队列和并发队列
阻塞队列在队列为空的时候从队头取数据会被阻塞如果队列已经满了那么插入数据的操作就会被阻塞直到队列中有空闲位置后再插入数据然后再返回。“生产者 - 消费者模型”是的我们可以使用阻塞队列轻松实现一个“生产者 - 消费者模型” 基于阻塞队列我们还可以通过协调“生产者”和“消费者”的个数来提高数据的处理效率。比如前面的例子我们可以多配置几个“消费者”来应对一个“生产者”。
并发队列
如何实现一个线程安全的队列简单粗暴的方式是直接在enqueue()、dequeue方法上直接加锁但是并发度较低
对于基于数组的循环队列利用cas操作可以实现更高效的并发
循环队列比链式队列的应用广泛
总结
线程池没有空闲线程时新的任务请求线程资源时线程池该如何处理各种处理策略又是如何实现的呢
两种处理策略一种是非阻塞的处理方式直接拒绝该请求一种是阻塞的处理方式将请求排队等有空闲线程时再取出进行处理
队列适应于存储排队请求。基于链表和基于数组的实现基于链表的支持无限队列的无界排队但是会导致过多的请求排队等待造成响应时间过长针对响应时间比较敏感的系统基于链表实现的无限排队的线程池是不合适的。而基于数组的队列的大小有限所以线程池中排队的请求超过队列大小时接下来的请求就会被拒绝这种方式对响应时间敏感的系统来说就相对更加合理。关键的是设置一个合理的队列大小。
实际上对于大部分有限资源的场景当没有空闲资源基本都可以通过队列的数据结构来实现请求排队。例如数据库连接池
