有域名之后怎么自己做网站,做网站的品牌公司有哪些,制作网站报价单,成都餐饮设计公司有哪些文章目录前言#xff1a;理解“队列”的正确姿势一个关于队列的小思考——请求处理队列的两大“护法”————顺序队列和链式队列数组实现的队列链表实现的队列循环队列关于开篇#xff0c;你明白了吗#xff1f;最后说一句前言#xff1a; 哈喽#xff01;欢迎来到黑洞晓…
文章目录前言理解“队列”的正确姿势一个关于队列的小思考——请求处理队列的两大“护法”————顺序队列和链式队列数组实现的队列链表实现的队列循环队列关于开篇你明白了吗最后说一句前言 哈喽欢迎来到黑洞晓威的博客 上一次我们在这里聊了一下队列现在让我们再次翻开这个话题继续探讨一下这个有趣的数据结构吧 虽然队列看起来比较普通但是它在实际应用中却 有着不可替代的作用。所以无论是计算机系统中的任务调度还是网络数据包的传输队列都扮演着重要的角色。 接下来我们将深入了解队列的应用、实现以及相关算法问题。让我们一起来暴打队列吧 理解“队列”的正确姿势
王者荣耀中宫本武藏有这么一句台词——“想挑战的人排好队一个一个来”。 这句台词可以很好地联系到数据结构中的队列。在数据结构中队列就像是一群人在排队等待挑战宫本武藏每个人都必须按照先来后到的原则依次接受服务。当新的人加入队伍时必须排在队尾而队伍中的人只能按照先后顺序依次出队。 我们知道栈只支持两个基本操作 入栈push()和出栈pop()。队列跟栈非常相似支持的操作也很有限最基本的操作也是两个 入队enqueue()放一个数据到队列尾部 出队dequeue()从队列头部取一个元素。 所以队列跟栈一样也是一种 操作受限的线性表数据结构。
队列的概念很好理解基本操作也很容易掌握。作为一种非常基础的数据结构队列的应用也非常广泛比如排队、缓存、广度优先搜索等等。你准备好了吗让我们一起来探索队列的奥秘吧
一个关于队列的小思考——请求处理
我们知道CPU资源是有限的任务的处理速度与线程个数并不是线性正相关。相反过多的线程反而会导致CPU频繁切换处理性能下降。所以线程池的大小一般都是综合考虑要处理任务的特点和硬件环境来事先设置的。
当我们向固定大小的线程池中请求一个线程时如果线程池中没有空闲资源了这个时候线程池如何处理这个请求是拒绝请求还是排队请求各种处理策略又是怎么实现的呢
实际上这些问题并不复杂其底层的数据结构就是我们今天要学的内容队列queue。
队列的两大“护法”————顺序队列和链式队列
嘿大佬们我们现在知道了队列跟栈一样也是一种抽象的数据结构。它的特性很简单就是先进先出支持在队尾插入元素在队头删除元素。但是究竟
该如何实现一个队列呢
让我们来看看吧就像栈一样队列也可以用数组来实现这种实现方式叫做顺序队列。还可以用链表来实现这种实现方式叫做链式队列。顺序队列和链式队列都有各自的优缺点需要根据实际情况进行选择。所以无论是顺序队列还是链式队列都是我们实现队列的可选方案。现在让我们先来看下基于数组的实现方法吧
数组实现的队列
// 用数组实现的队列
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;}
}
比起栈的数组实现队列的数组实现稍微有点儿复杂但是没关系。我稍微解释一下实现思路你很容易就能明白了。
对于栈来说我们只需要一个 栈顶指针 就可以了。但是队列需要两个指针一个是head指针指向队头一个是tail指针指向队尾。
你可以结合下面这张图来理解。当a、b、c、d依次入队之后队列中的head指针指向下标为0的位置tail指针指向下标为4的位置。 当我们调用两次出队操作之后队列中head指针指向下标为2的位置tail指针仍然指向下标为4的位置。 你肯定已经发现了随着不停地进行入队、出队操作head和tail都会持续往后移动。当tail移动到最右边即使数组中还有空闲空间也无法继续往队列中添加数据了。这个问题该如何解决呢
你是否还记得在数组那一节我们也遇到过类似的问题就是数组的删除操作会导致数组中的数据不连续。你还记得我们当时是怎么解决的吗对用 数据搬移但是每次进行出队操作都相当于删除数组下标为0的数据要搬移整个队列中的数据这样出队操作的时间复杂度就会从原来的O(1)变为O(n)。能不能优化一下呢
实际上我们在出队时可以不用搬移数据。如果没有空闲空间了我们只需要在入队时再集中触发一次数据的搬移操作。借助这个思想出队函数dequeue()保持不变我们稍加改造一下入队函数enqueue()的实现就可以轻松解决刚才的问题了。下面是具体的代码 // 入队操作将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;}
从代码中我们看到当队列的tail指针移动到数组的最右边后如果有新的数据入队我们可以将head到tail之间的数据整体搬移到数组中0到tail-head的位置。 这种实现思路中出队操作的时间复杂度仍然是O(1)但入队操作的时间复杂度还是O(1)吗你可以用我们第3节、第4节讲的算法复杂度分析方法自己试着分析一下。
接下来我们再来看下 基于链表的队列实现方法。
链表实现的队列
基于链表的实现我们同样需要两个指针head指针和tail指针。它们分别指向链表的第一个结点和最后一个结点。如图所示入队时tail-next new_node, tail tail-next出队时head head-next。我将具体的代码放到GitHub上你可以自己试着实现一下然后再去GitHub上跟我实现的代码对比下看写得对不对。
首先我们需要定义一个节点类它包含一个值属性和一个指向下一个节点的指针属性
public class NodeT { // 这是一个泛型类T表示节点的值可以是任何类型T value; // 存储节点的值NodeT next; // 指向下一个节点的指针public Node(T value) { // 构造函数用来创建新的节点this.value value; // 设置节点的值this.next null; // 初始时指针为空}
}接下来我们定义一个队列类它包含一个指向队列头部的指针属性和一个指向队列尾部的指针属性
public class QueueT { // 这是一个泛型类T表示队列的元素可以是任何类型NodeT head; // 指向队列头部的指针NodeT tail; // 指向队列尾部的指针public Queue() { // 构造函数用来创建新的队列this.head null; // 初始时头部指针为空this.tail null; // 初始时尾部指针为空}
}在队列类中我们可以实现以下方法
enqueue(value)将一个元素添加到队列的尾部。
public void enqueue(T value) { // 将元素value添加到队列的尾部NodeT newNode new Node(value); // 创建一个新的节点if (tail null) { // 如果队列为空head newNode; // 将头部指针指向新节点tail newNode; // 将尾部指针指向新节点} else { // 如果队列不为空tail.next newNode; // 将当前尾部节点的指针指向新节点tail newNode; // 将尾部指针指向新节点}
}
dequeue()从队列的头部移除并返回一个元素。
public T dequeue() { // 从队列的头部移除并返回一个元素if (head null) { // 如果队列为空return null; // 返回null}T value head.value; // 获取队列头部节点的值head head.next; // 将头部指针指向下一个节点if (head null) { // 如果队列为空tail null; // 将尾部指针也置为空}return value; // 返回队列头部节点的值
}
peek()返回队列头部的元素但不移除它。
public T peek() { // 返回队列头部的元素但不移除它if (head null) { // 如果队列为空return null; // 返回null}return head.value; // 返回队列头部节点的值
}isEmpty()检查队列是否为空。
public boolean isEmpty() { // 检查队列是否为空return head null; // 如果头部指针为空队列为空
}clear()清空队列。
public void clear() { // 清空队列head null; // 将头部指针置为空tail null; // 将尾部指针置为空
}在这里偷偷告诉大家基于链表的队列我懒得写了于是就交给了ChatGPT完成说实话效果竟然出奇的好大家在学习这些基础内容的时候也不妨善用ChatGPT说必定你就能解锁一个优质的老师哈哈哈。 循环队列
我们刚才用数组来实现队列的时候在tailn时会有数据搬移操作这样入队操作性能就会受到影响。那有没有办法能够避免数据搬移呢我们来看看循环队列的解决思路。
循环队列顾名思义它长得像一个环。原本数组是有头有尾的是一条直线。现在我们把首尾相连扳成了一个环。我画了一张图你可以直观地感受一下。 我们可以发现图中这个队列的大小为8当前head4tail7。当有一个新的元素a入队时我们放入下标为7的位置。但这个时候我们并不把tail更新为8而是将其在环中后移一位到下标为0的位置。当再有一个元素b入队时我们将b放入下标为0的位置然后tail加1更新为1。所以在ab依次入队之后循环队列中的元素就变成了下面的样子 通过这样的方法我们成功避免了数据搬移操作。看起来不难理解但是循环队列的代码实现难度要比前面讲的非循环队列难多了。要想写出没有bug的循环队列的实现代码我个人觉得最关键的是 确定好队空和队满的判定条件。
在用数组实现的非循环队列中队满的判断条件是tail n队空的判断条件是head tail。那针对循环队列如何判断队空和队满呢
队列为空的判断条件仍然是head tail。但队列满的判断条件就稍微有点复杂了。我画了一张队列满的图你可以看一下试着总结一下规律。 就像我图中画的队满的情况tail3head4n8所以总结一下规律就是(31)%84。多画几张队满的图你就会发现当队满时 (tail1)%nhead。
你有没有发现当队列满时图中的tail指向的位置实际上是没有存储数据的。所以循环队列会浪费一个数组的存储空间。
Talk is cheap如果还是没怎么理解那就show you code吧。
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;}
}
关于开篇你明白了吗
队列的知识就讲完了我们现在回过来看下开篇的问题。线程池没有空闲线程时新的任务请求线程资源时线程池该如何处理各种处理策略又是如何实现的呢
我们一般有两种处理策略。
第一种是非阻塞的处理方式直接拒绝任务请求
另一种是阻塞的处理方式将请求排队等到有空闲线程时取出排队的请求继续处理。那如何存储排队的请求呢
我们希望公平地处理每个排队的请求先进者先服务所以队列这种数据结构很适合来存储排队请求。我们前面说过队列有基于链表和基于数组这两种实现方式。这两种实现方式对于排队请求又有什么区别呢
基于链表的实现方式可以实现一个支持无限排队的无界队列unbounded queue但是可能会导致过多的请求排队等待请求处理的响应时间过长。所以针对响应时间比较敏感的系统基于链表实现的无限排队的线程池是不合适的。
而基于数组实现的有界队列bounded queue队列的大小有限所以线程池中排队的请求超过队列大小时接下来的请求就会被拒绝这种方式对响应时间敏感的系统来说就相对更加合理。 不过设置一个合理的队列大小也是非常有讲究的。队列太大导致等待的请求太多队列太小会导致无法充分利用系统资源、发挥最大性能。
最后说一句
感谢大家的阅读文章通过网络学习资源以及自己的学习过程整理出来希望能帮助到大家。
才疏学浅难免会有纰漏如果你发现了错误的地方可以提出来我会对其加以修改。
