JS数据结构&算法学习——队列

简介: 在之前的栈,是一种受限的线性结构,为先进后出,那么同为线性结构的队列,特点又是怎么样的呢?

队列

在之前的栈,是一种受限的线性结构,为先进后出,那么同为线性结构的队列,特点又是怎么样的呢?

概念

队列是一种受限的线性表,先进先出,它只允许我们在表的前端进行删除操作,在表的后端进行添加操作。

生活应用

  1. 在生活中最常看到的队列场景就是排队了,即我们在排队时,排头也就是我们的表头,它允许出去,无法进行插队也就是添加操作,而排尾,也就是我们的表尾,它允许有人进行排队,即添加操作
  2. 在火车检票的时候,我们正常的是进行排队,而军人,老人等特殊人群可以优先进行处理,这就是优先队列。

程序应用

  1. 就拿我们JS来说,事件队列是比较常见的,因为JS是一门单线程语言,即在我们触发我们的函数的时候,会有一个事件队列,其会按照事件的触发顺序来执行,即先触发先执行,这就是队列的一种体现
  2. 当然线程队列也是一种队列的体现,我们一般为了任务能够并行处理,会用到多线程,但是多个线程会占据非常多的内存,所以这个时候我们可以通过使用线程队列,按照次序来启动线程,并处理对应的任务。

队列结构

当然队列结构的实现和栈一样,可以通过数组和链表实现

首先我们先封装一下队列

function queue(){
    //队列的属性
    this.items = []
    //队列的相关操作
}
var queue = new queue()
复制代码

因为JS中的类是基于对象的所以我们封装了一个队列类,在类中我们可以定义队列的属性与方法,封装好之后我们可以去通过调用来对队列实现一些操作

常见操作及封装

  1. enqueue(element):在队列的尾部添加元素
  2. dequeue():移除队列的首个元素,并返回其值
  3. front():返回队列的第一个元素
  4. isEmpty:判断队列是否为空队列
  5. size:返回队列长度
  6. toString():转换字符串

enqueue(element):使用push方法来进行入队封装

queue.prototype.enqueue = function (element) {
      this.items.push(element)
}
复制代码

dequeue():通过JS提供的shift的方法来进行出队操作

queue.prototype.delet = function () {
      return this.items.shift()
}
复制代码

front():直接通过数组下标来返回队首元素

queue.prototype.front = function () {
      return this.items[0]
}
复制代码

isEmpty():通过数组的length来进行栈的判空

queue.prototype.isEmpty = function () {
      return this.items.length == 0
}
复制代码

size()

queue.prototype.size = function () {
      return this.items.length
}
复制代码

toString():通过声明字符串变量,对栈进行遍历,通过JS字符串的特性,来进行字符串拼接,最后返回其字符串,其实现原理和栈的toString一样。

queue.prototype.toString = function () {
      var reString = ''
      for (let i = 0; i < this.items.length; i++) {
        reString += this.items[i] + ''
      }
      return reString
    }
复制代码

使用

在封装好之后我们就可以开始进行调用

queue.enqueue(1)
queue.enqueue(19)
queue.enqueue(11)
console.log(queue)
复制代码

1.webp.jpg

queue.delet()
console.log(queue)
复制代码

1.webp.jpg

大家可以试着自己些写一下并体验队列的这几种操作

击鼓传花

相信大家都玩过击鼓传花的游戏吧,击鼓的时候传递花朵,鼓声停,花在谁手中谁就受惩罚

现在有不同的游戏规则,即同学围成一圈,按阿拉伯数字顺序进行数数,当某人数到在场人数的时候就会被淘汰

我们现在要用队列来实现这个游戏并返回来最终获胜者的姓名

  1. 算法原理:

1.webp.jpg

现在我们将所有人按次序放入一个队列中,然后从队首开始出队入队,以此当出现在场人数的时候,其正好是队首,出队,多次操作,得到结果

  1. 算法实现:
  1. 创建队列并将所有人入队
var queue = new queue
    for (let i = 0; i < list.length; i++) {
     queue.enqueue(nameList[i])
}
复制代码
  1. 开始循环入队出队直到队列的长度为1
while (queue.size() > 1) {
      //开始数num,当不是num的时候出队后重新入队,当num是在场人数时,出队。
      for (let i = 0; i < num - 1; i++) {
        queue.enqueue(queue.dequeue())
      }
      //删除目标即现在的队首
      queue.dequeue()
    }



相关文章
|
10天前
|
运维 监控 JavaScript
内网网管软件中基于 Node.js 的深度优先搜索算法剖析
内网网管软件在企业网络中不可或缺,涵盖设备管理、流量监控和安全防护。本文基于Node.js实现深度优先搜索(DFS)算法,解析其在网络拓扑遍历中的应用。通过DFS,可高效获取内网设备连接关系,助力故障排查与网络规划。代码示例展示了图结构的构建及DFS的具体实现,为内网管理提供技术支持。
34 11
|
2月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
158 77
|
3天前
|
算法 调度 C++
STL——栈和队列和优先队列
通过以上对栈、队列和优先队列的详细解释和示例,希望能帮助读者更好地理解和应用这些重要的数据结构。
16 4
|
7天前
|
监控 网络协议 算法
基于问题“如何监控局域网内的电脑”——Node.js 的 ARP 扫描算法实现局域网内计算机监控的技术探究
在网络管理与安全领域,监控局域网内计算机至关重要。本文探讨基于Node.js的ARP扫描算法,通过获取IP和MAC地址实现有效监控。使用`arp`库安装(`npm install arp`)并编写代码,可定期扫描并对比设备列表,判断设备上线和下线状态。此技术适用于企业网络管理和家庭网络安全防护,未来有望进一步提升效率与准确性。
23 8
|
1月前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
86 29
|
16天前
|
DataX
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
|
1月前
|
存储 算法 C语言
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
95 25
|
1月前
|
存储 人工智能 算法
C 408—《数据结构》算法题基础篇—数组(通俗易懂)
408考研——《数据结构》算法题基础篇之数组。(408算法题的入门)
72 23
|
2月前
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
50 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
2月前
|
JavaScript 算法 安全
深度剖析:共享文件怎么设置密码和权限的 Node.js 进阶算法
在数字化时代,共享文件的安全性至关重要。本文聚焦Node.js环境,介绍如何通过JavaScript对象字面量构建数据结构管理文件安全信息,包括使用`bcryptjs`库加密密码和权限校验算法,确保高效且安全的文件共享。通过实例代码展示加密与权限验证过程,帮助各行业实现严格的信息资产管理与协作。

热门文章

最新文章