队列

队列是一种罕用的数据结构，它最大的特点是先入先出，即先进入队列中的元素最先进去。 滑动窗口的平均值请实现如下类型MovingAverage，计算滑动窗口中所有数字的平均值，该类型构造函数的参数确定滑动窗口的大小，每次调用成员函数next时都会在滑动窗口中增加一个整数，并返回滑动窗口中所有数字的平均值。/** * Initialize your data structure here. * @param {number} size */var MovingAverage = function(size) { this.size = size; this.arr = [] this.sum = 0};/** * @param {number} val * @return {number} */MovingAverage.prototype.next = function(val) { this.arr.push(val) this.sum += val if(this.arr.length>this.size) { this.sum -= this.arr.shift() } return this.sum / this.arr.length};最近申请次数请实现如下类型RecentCounter，它是统计过来3000ms内的申请次数的计数器。该类型的构造函数RecentCounter初始化计数器，申请数初始化为0；函数ping（int t）在工夫t增加一个新申请（t示意以毫秒为单位的工夫），并返回过来3000ms内（工夫范畴为[t-3000，t]）产生的所有申请数。假如每次调用函数ping的参数t都比之前调用的参数值大。var RecentCounter = function() { this.arr = []};/** * @param {number} t * @return {number} */RecentCounter.prototype.ping = function(t) { this.arr.push(t) while(this.arr.length > 1 && this.arr[0] + 3000 < t) { this.arr.shift() } return this.arr.length};二叉树的广度优先遍历应聘者在面试时常常须要应用队列来解决与广度优先搜寻相干的问题。图的广度优先遍历请看图的章节。 ...

摘要：本文通过剖析鸿蒙轻内核队列模块的源码，把握队列应用上的差别。本文分享自华为云社区《鸿蒙轻内核M核源码剖析系列十三 音讯队列Queue》，作者：zhushy 。 队列（Queue）是一种罕用于工作间通信的数据结构。工作可能从队列外面读取音讯，当队列中的音讯为空时，挂起读取工作；当队列中有新音讯时，挂起的读取工作被唤醒并解决新音讯。工作也可能往队列里写入音讯，当队列曾经写满音讯时，挂起写入工作；当队列中有闲暇音讯节点时，挂起的写入工作被唤醒并写入音讯。如果将读队列和写队列的超时工夫设置为0，则不会挂起工作，接口会间接返回，这就是非阻塞模式。音讯队列提供了异步解决机制，容许将一个音讯放入队列，但不立刻解决。同时队列还有缓冲音讯的作用。 本文通过剖析鸿蒙轻内核队列模块的源码，把握队列应用上的差别。本文中所波及的源码，以OpenHarmony LiteOS-M内核为例，均能够在开源站点https://gitee.com/openharmony... 获取。 接下来，咱们看下队列的构造体，队列初始化，队列罕用操作的源代码。 1、队列构造体定义和罕用宏定义1.1 队列构造体定义在文件kernel\include\los_queue.h中定义队列管制块构造体为LosQueueCB，构造体源代码如下。队列状态.queueState取值OS_QUEUE_UNUSED、OS_QUEUE_INUSED，其余构造体成员见正文局部。 typedef struct { UINT8 *queue; /**< 队列内存空间的指针 */ UINT16 queueState; /**< 队列的应用状态 */ UINT16 queueLen; /**< 队列长度，即音讯数量 */ UINT16 queueSize; /**< 音讯节点大小 */ UINT16 queueID; /**< 队列编号 */ UINT16 queueHead; /**< 音讯头节点地位 */ UINT16 queueTail; /**< 音讯尾节点地位 */ UINT16 readWriteableCnt[OS_READWRITE_LEN]; /**< 2维数组，可读、可写的音讯数量, 0:可读, 1:可写 */ LOS_DL_LIST readWriteList[OS_READWRITE_LEN]; /**< 2维双向链表数组，阻塞读、写工作的双向链表, 0:读链表, 1:写链表 */ LOS_DL_LIST memList; /**< 内存节点双向链表 */} LosQueueCB;1.2 队列罕用宏定义零碎反对创立多少队列是依据开发板状况应用宏LOSCFG_BASE_IPC_QUEUE_LIMIT定义的，每一个队列queueID是queueID类型的，取值为[0,LOSCFG_BASE_IPC_QUEUE_LIMIT)，示意队列池中各个队列的编号。 ⑴处的宏从队列池中获取指定队列编号QueueID对应的队列管制块。⑵处依据双向链表节点readWriteList[OS_QUEUE_WRITE]获取队列管制块内存地址。 ...

摘要：对于队列来说数据结构相比栈简单一些，然而也不是很难，搞懂先进先出而后用数组或者链表实现即可。本文分享自华为云社区《手写各种队列，一文搞定》，原文作者：bigsai 。 前言栈和队列是一对好兄弟，栈的机制绝对简略，后入先出，就像进入一个狭小的山洞，山洞只有一个出入口，只能后进先出(在里面的先进来，堵在外面先进去的就有点晦气)。而队列就好比是一个隧道，前面的人跟着后面走，后面人先进来(先入先出)。日常的排队就是队列运行模式的一个形容！ 栈是一种喜新厌旧的数据结构，来了新的就会解决新的把老的先停滞在这(咱们找人、约人办事最厌恶这种人)，队列就是假公济私的一种数据结构，排队先来先得，考究程序性，所以这种数据结构在程序设计、中间件等都十分宽泛的利用，例如音讯队列、FIFO磁盘调度、二叉树层序遍历、BFS宽度优先搜寻等等。 队列的核心理念就是：先进先出！ 队列的概念：队列是一种非凡的线性表，非凡之处在于它只容许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。 队列介绍咱们设计队列时候能够抉择一个规范，这里就拿力扣622设计循环队列作为队列设计的规范。 队头front：删除数据的一端。 队尾rear ：插入数据的一端。 对于数组，从数组前面插入更容易，数组后面插入较艰难，所以个别用数组实现的队列队头在数组后面，队尾在数组前面；而对于链表，插入删除在中间别离进行那么头部(后面)删除尾部插入最不便的抉择。 实现办法： MyCircularQueue(k): 结构器，设置队列长度为 k 。Front: 从队首获取元素。如果队列为空，返回 -1 。Rear: 获取队尾元素。如果队列为空，返回 -1 。enQueue(value): 向循环队列插入一个元素。如果胜利插入则返回真。deQueue(): 从循环队列中删除一个元素。如果胜利删除则返回真。isEmpty(): 查看循环队列是否为空。isFull(): 查看循环队列是否已满。一般队列依照上述的介绍，咱们很容易晓得数组实现的形式。用数组模仿示意队列。要思考初始化，插入，问题。 在这个一般队列一些操作须要留神的有： 初始化：数组的front和rear都指向0. (front和rear下标相等的时候阐明队列为空) 入队：队不满，数组不越界，先队尾地位传值，再队尾下标+1(队尾rear实际上超前一位，为了辨别空队列状况) 出队：队不空，先取队头地位元素，在队头+1。 然而很容易发现问题，每个空间域只能利用一次，造成空间极度节约，非常容易越界！ 循环队列(数组实现)针对上述的问题。有个较好的解决办法！就是对曾经申请的(数组)内存反复利用。这就是咱们所说的循环队列。循环队列的一个益处是咱们能够利用这个队列之前用过的空间。在一个一般队列里，一旦一个队列满了，咱们就不能插入下一个元素，即便在队列后面仍有空间。然而应用循环队列，咱们能应用这些空间去存储新的值。 数组实现的循环队列就是在逻辑上作批改。因为咱们队列中只须要front和rear两个指针。rear在逻辑上在前面，front在逻辑上是在后面的，但实际上它们不肯定谁在前谁在后，在计算间隔的时候须要给rear先补上数组长度减去front，而后求余即可。 初始化：数组的front和rear都指向0. 这里须要留神的是：front和rear位于同一个地位时候，证实队列外面是空的。还有在这里我具体实现时候将数组申请大了一个地位空进去，避免队列满的状况又造成front和rear在同一个地位。 入队：队不满，先队尾地位传值，再rear=(rear + 1) % maxsize; 出队：队不空，先取队头地位元素，front=(front + 1)% maxsize; 这里出队入队指标相加如果遇到最初须要转到头地位，这里间接+1求余找到地位(相比判断是否在最初更加简洁)，其中maxsize是数组理论大小。 是否为空：return rear == front; 大小：return (rear+maxsize-front)%maxsize; 这里很容易了解，一张图就能解释分明，无论是front理论在前在后都能满足要求。 这外面有几个大家须要留神的，就是指标相加如果遇到最初须要转到头的话。能够判断是否到数组开端地位。也能够间接+1求余。其中maxsize是数组理论大小。 具体实现： public class MyCircularQueue { private int data[];// 数组容器 private int front;// 头 private int rear;// 尾 private int maxsize;// 最大长度 public MyCircularQueue(int k) { data = new int[k+1]; front = 0; rear = 0; maxsize = k+1; } public boolean enQueue(int value) { if (isFull()) return false; else { data[rear] = value; rear=(rear + 1) % maxsize; } return true; } public boolean deQueue() { if (isEmpty()) return false; else { front=(front+1)%maxsize; } return true; } public int Front() { if(isEmpty()) return -1; return data[front]; } public int Rear() { if(isEmpty()) return -1; return data[(rear-1+maxsize)%maxsize]; } public boolean isEmpty() { return rear == front; } public boolean isFull() { return (rear + 1) % maxsize == front; }}循环队列(链表实现)对于链表实现的队列，要依据先进先出的规定思考头和尾的地位 ...

明天来看下LeetCode第239题-滑动窗口最大值。 首先看下题： 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧挪动到数组的最右侧。你只能够看到在滑动窗口内的 k 个数字。滑动窗口每次只向右挪动一位。 返回滑动窗口中的最大值。 输出：nums = [1,3,-1,-3,5,3,6,7], k = 3输入：[3,3,5,5,6,7]解释：滑动窗口的地位 最大值 [1 3 -1] -3 5 3 6 7 31 [3 -1 -3] 5 3 6 7 31 3 [-1 -3 5] 3 6 7 51 3 -1 [-3 5 3] 6 7 51 3 -1 -3 [5 3 6] 7 61 3 -1 -3 5 [3 6 7] 7 就是给出一个数组和一个k值，在数组里会有一个从0开始遍历到n-k+1地位的窗口，要给出每个窗口的最大值。 这题的解法有很多，咱们先来大略理下思路： 1、暴力 O(n*k) 2、堆 O(n*logk) ...

这篇文章是对LeetCode641题设计循环双端队列思路进行记录。(PS:后续应该还会在写一篇，等我把双向链表实现搞清楚了，一个指针还能理清，两个指针pre和next看着就有点晕了，等我消化下。) 先看下题： 设计实现双端队列。你的实现须要反对以下操作： MyCircularDeque(k)：构造函数,双端队列的大小为k。insertFront()：将一个元素增加到双端队列头部。 如果操作胜利返回 true。insertLast()：将一个元素增加到双端队列尾部。如果操作胜利返回 true。deleteFront()：从双端队列头部删除一个元素。 如果操作胜利返回 true。deleteLast()：从双端队列尾部删除一个元素。如果操作胜利返回 true。getFront()：从双端队列头部取得一个元素。如果双端队列为空，返回 -1。getRear()：取得双端队列的最初一个元素。 如果双端队列为空，返回 -1。isEmpty()：查看双端队列是否为空。isFull()：查看双端队列是否满了。示例： MyCircularDeque circularDeque = new MycircularDeque(3); // 设置容量大小为3circularDeque.insertLast(1); // 返回 truecircularDeque.insertLast(2); // 返回 truecircularDeque.insertFront(3); // 返回 truecircularDeque.insertFront(4); // 曾经满了，返回 falsecircularDeque.getRear(); // 返回 2circularDeque.isFull(); // 返回 truecircularDeque.deleteLast(); // 返回 truecircularDeque.insertFront(4); // 返回 truecircularDeque.getFront(); // 返回 4 家喻户晓栈和队列都是限制性的数据结构，在某些业务场景常常用到，而栈和队列其实用两种根本的数据结构数组和链表都能实现的。明天咱们先来看看如何用数组设计循环双端队列。 class MyCircularDeque { private int[] items; private int count; private int head; private int tail; public MyCircularDeque(int k) { this.count = k+1; this.items = new int[count]; this.head = 0; this.tail = 0; } public boolean insertFront(int value) { if (isFull()) { return false; } head = (head - 1 + count) % count; items[head] = value; return true; } public boolean insertLast(int value) { if (isFull()) { return false; } items[tail] = value; tail = (tail + 1) % count; return true; } public boolean deleteFront() { if (isEmpty()) { return false; } head = (head + 1) % count; return true; } public boolean deleteLast() { if (isEmpty()) { return false; } tail = (tail - 1 + count) % count; return true; } public int getFront() { if (isEmpty()) { return -1; } return items[head]; } public int getRear() { if (isEmpty()) { return -1; } return items[(tail - 1 + count) % count]; } public boolean isEmpty() { return head == tail; } public boolean isFull() { return (tail + 1) % count == head; }}首先循环队列你能够设想成一个环状，首尾是相连的，再来它的元素地位是随插入删除始终挪动的，因而效率其实是偏低的，插入元素会波及数据迁徙，所以工业上的队列个别是用链表实现的。 ...

摘要：本文通过剖析LiteOS队列模块的源码，把握队列应用上的差别。本文分享自华为云社区《LiteOS内核源码剖析系列十 音讯队列Queue》，原文作者：zhushy 。 队列（Queue）是一种罕用于工作间通信的数据结构。工作可能从队列外面读取音讯，当队列中的音讯为空时，挂起读取工作；当队列中有新音讯时，挂起的读取工作被唤醒并解决新音讯。工作也可能往队列里写入音讯，当队列曾经写满音讯时，挂起写入工作；当队列中有闲暇音讯节点时，挂起的写入工作被唤醒并写入音讯。如果将读队列和写队列的超时工夫设置为0，则不会挂起工作，接口会间接返回，这就是非阻塞模式。音讯队列提供了异步解决机制，容许将一个音讯放入队列，但不立刻解决。同时队列还有缓冲音讯的作用。 本文通过剖析LiteOS队列模块的源码，把握队列应用上的差别。LiteOS队列模块的源代码，均能够在LiteOS开源站点https://gitee.com/LiteOS/LiteOS 获取。队列源代码、开发文档，示例程序代码如下： LiteOS内核队列源代码包含队列的公有头文件kernel\base\include\los_queue_pri.h、头文件kernel\include\los_queue.h、C源代码文件kernel\base\los_queue.c。 开发指南文档–队列在线文档https://gitee.com/LiteOS/Lite... 接下来，咱们看下队列的构造体，队列初始化，队列罕用操作的源代码。 1、队列构造体定义和罕用宏定义1.1 队列构造体定义在文件kernel\base\include\los_queue_pri.h定义的队列管制块构造体为LosQueueCB，构造体源代码如下。队列状态.queueState取值OS_QUEUE_UNUSED、OS_QUEUE_INUSED，队列内存类型.queueMemType取值OS_QUEUE_ALLOC_STATIC、OS_QUEUE_ALLOC_DYNAMIC，别离示意计用户调配队列内存空间或零碎主动调配。 typedef struct { UINT8 *queueHandle; /**< 队列内存空间的指针 */ UINT8 queueState; /**< 队列的应用状态 */ UINT8 queueMemType; /**< 队列内存类型，用户调配队列内存空间或零碎主动调配 */ UINT16 queueLen; /**< 队列长度，音讯数量 */ UINT16 queueSize; /**< 音讯节点大小 */ UINT32 queueId; /**< 队列编号 */ UINT16 queueHead; /**< 音讯头节点地位 */ UINT16 queueTail; /**< 音讯尾节点地位 */ UINT16 readWriteableCnt[OS_QUEUE_N_RW]; /**< 2维数组，可读、可写的音讯数量, 0:可读, 1:可写 */ LOS_DL_LIST readWriteList[OS_QUEUE_N_RW]; /**< 2维链表数组，阻塞读、写工作的双向链表, 0:读链表, 1:写链表 */ LOS_DL_LIST memList; /**< 内存节点双向链表，兼容CMSIS时应用 */} LosQueueCB;1.2 队列罕用宏定义零碎反对创立多少队列是依据开发板状况应用宏LOSCFG_BASE_IPC_QUEUE_LIMIT定义的，每一个队列queueId是UINT32类型的。队列queueId由2局部组成：count和index，别离处于高16位和低16位。创立队列，应用后删除时，队列回收到队列池时，队列queueId的高16位即count值会加1，这样能够用来示意该队列被创立删除的次数。index取值为[0,LOSCFG_BASE_IPC_QUEUE_LIMIT)，示意队列池中各个队列的编号。 ...