JS数据结构&算法学习——栈

简介: 为什么说栈是一种受限的数据结构呢?栈和数组不同,如果我们想删除或者插入数组中的某一个元素后,其没有限制,但是栈不同,由于他的结构原因,他的操作是受限制的。

与数组相比,栈是受限的线性结构

概念

为什么说栈是一种受限的数据结构呢?栈和数组不同,如果我们想删除或者插入数组中的某一个元素后,其没有限制,但是栈不同,由于他的结构原因,他的操作是受限制的。

通过上面的结构,我们可以知道,栈只有一个可操作端,也就是我们想删除中间的元素,我们需要先移除这个元素上面的元素才能对目标元素进行移除,对于这种特性,我们称作为后进先出(LIFO),我们对于栈的操作有两种名词即:

  1. 入栈:在栈顶添加新元素
  2. 出栈:删除栈顶元素

生活应用

  1. 叠放的盘子:如果我们想要拿到一摞盘子中间的一个,那么我们需要去将上面的盘子移开,进而拿到我们想要的盘子
  2. 停车场的车:如果停车场内放满了车,你想要把自己的车开走,那么你就需要将其他人的车移开,给自己的车开辟一条路

程序应用(函数调栈)

A函数调用B函数,B函数调用C函数,C函数调用D函数

  1. A压入进栈(未执行完)
  2. A调用B将B压入栈
  3. 以此类推
  4. D执行完成出栈
  5. C执行完成出栈
  6. 以此类推

PS:递归很容易出现栈溢出

栈结构

我们通常可以使用链表和数组来实现栈结构

  1. 栈封装结构结构:
function stack(){
    //栈的属性
    this.items = []
    //栈的相关操作
}
var stack = new stack()
stack.psuh()
复制代码
  1. 因为JS中的类是基于对象的所以我们封装了一个栈类,在类中我们可以定义栈的属性与方法,封装好之后我们可以去通过调用来对栈实现我们上文所提及的入栈,出栈等操作。
  2. 操作封装
    这里我们有两种封装方式,一种是为对象实例添加方法,一种是通过原型为类添加方法,我们一般是通过原型来封装,节省内存
//对象实例
this.push = function() {}
//类
Stack.prototype.push = function (element) {}
复制代码
  1. 添加栈顶元素压栈:使用push方法来进行压栈封装
Stack.prototype.push = function (element) {
    this.items.push(element)
}
复制代码
  1. 删除栈顶元素出栈:使用pop()方法来进行取元素封装
Stack.prototype.pop = function () {
    return this.items.pop()
}
复制代码
  1. 查看栈顶元素:通过调用数组的length来返回栈顶元素
Stack.prototype.peek = function () {
    return this.items[this.items.length - 1]
}
复制代码
  1. 判空:同样通过数组的length来进行栈的判空
Stack.prototype.isEmpty = function () {
    return this.items.length === 0
}
复制代码
  1. 取栈长
Stack.prototype.size = function () {
    return this.items.length
}
复制代码
  1. 栈转换字符串:通过声明字符串变量,对栈进行遍历,通过JS字符串的特性,来进行字符串拼接,最后返回其字符串
Stack.prototype.toString = function (element) {
    var reString = ''
    for(let i = 0; i < this.items.length; i++){
        reString += this.items[i] + ''
    }
    return reString
}
复制代码

使用

  1. 压栈 将1,20通过push压入栈中,此时的栈为[1,20]
stack.push(1)
stack.push(20)、
console.log(stack)
复制代码
  1. 取栈顶 这个时候栈顶为20,所以返回为20
console.log(stack.peek())
复制代码
  1. 拼接栈元素 返回值为120,即将栈中元素拼接起来
console.log(stack.toString())
复制代码

1.webp.jpg

十进制—>二进制de转换

十进制&二进制的转换是计算机中比较常见的操作,我们先来了解一下他们是如何转换的

举个栗子:100(10进制)转换

100/2 = 50 余0 ,50/2 = 25 余0 ,25/2 = 12 余1 ,12/2 = 6 余0 , 6/2 = 3 余0 ,3/2 = 1 ,余1 ,1/2 = 0 余1

得到1100100,这就是十进制数100转换为二进制的结果

那么我们现在知道了十进制转换二进制的原理,那么我们就可以根据栈的特性来对与十进制与二进制转换的封装

function TtoT(tNumber) {
    var stack = new stack
    while (tNumber > 0) {
        stack.push(tNumber%2)
        iNumber = Math.floor(tNumber/2)
    }
    return stack.UtoString
}
复制代码

我们根据栈的先入后出的特性,对待转换数字进行转换,压入转换数字对于2的除法运算的余数,并通过变量保存当前的运算结果为下一次计算做准备,最后获取到我们转换后的栈,当然我们可以将我们上文toString方法的封装,将其倒置,可以得到二进制结果的字符串。

Stack.prototype.UtoString = function (element) {
    var reString = ''
      for (let i = this.items.length; i > 0; i--) {
        reString += this.items[i - 1] + ''
      }
      return reString
}
复制代码

1.webp.jpg


目录
打赏
0
0
2
0
69
分享
相关文章
架构学习:7种负载均衡算法策略
四层负载均衡包括数据链路层、网络层和应用层负载均衡。数据链路层通过修改MAC地址转发帧;网络层通过改变IP地址实现数据包转发;应用层有多种策略,如轮循、权重轮循、随机、权重随机、一致性哈希、响应速度和最少连接数均衡,确保请求合理分配到服务器,提升性能与稳定性。
271 11
架构学习:7种负载均衡算法策略
深度剖析:共享文件怎么设置密码和权限的 Node.js 进阶算法
在数字化时代,共享文件的安全性至关重要。本文聚焦Node.js环境,介绍如何通过JavaScript对象字面量构建数据结构管理文件安全信息,包括使用`bcryptjs`库加密密码和权限校验算法,确保高效且安全的文件共享。通过实例代码展示加密与权限验证过程,帮助各行业实现严格的信息资产管理与协作。
局域网网络管控里 Node.js 红黑树算法的绝妙运用
在数字化办公中,局域网网络管控至关重要。红黑树作为一种自平衡二叉搜索树,凭借其高效的数据管理和平衡机制,在局域网设备状态管理中大放异彩。通过Node.js实现红黑树算法,可快速插入、查找和更新设备信息(如IP地址、带宽等),确保网络管理员实时监控和优化网络资源,提升局域网的稳定性和安全性。未来,随着技术融合,红黑树将在网络管控中持续进化,助力构建高效、安全的局域网络生态。
52 9
基于 Node.js Socket 算法搭建局域网屏幕监控系统
在数字化办公环境中,局域网屏幕监控系统至关重要。基于Node.js的Socket算法实现高效、稳定的实时屏幕数据传输,助力企业保障信息安全、监督工作状态和远程技术支持。通过Socket建立监控端与被监控端的数据桥梁,确保实时画面呈现。实际部署需合理分配带宽并加密传输,确保信息安全。企业在使用时应权衡利弊,遵循法规,保障员工权益。
53 7
深度探秘:运用 Node.js 哈希表算法剖析员工工作时间玩游戏现象
在现代企业运营中,确保员工工作时间高效专注至关重要。为应对员工工作时间玩游戏的问题,本文聚焦Node.js环境下的哈希表算法,展示其如何通过快速查找和高效记录员工游戏行为,帮助企业精准监测与分析,遏制此类现象。哈希表以IP地址等为键,存储游戏网址、时长等信息,结合冲突处理与动态更新机制,确保数据完整性和时效性,助力企业管理层优化工作效率。
35 3
如何学习JavaScript?
如何学习JavaScript?
81 5
JavaScript学习第二章--字符串
本文介绍了JavaScript中的字符串处理,包括普通字符串和模板字符串的使用方法及常见字符串操作方法如`charAt`、`concat`、`endsWith`等,适合前端学习者参考。作者是一位热爱前端技术的大一学生,专注于分享实用的编程技巧。
45 2
JavaScript学习第一章
本文档介绍了JavaScript的基础知识,包括其在网页中的作用、如何通过JavaScript动态设置HTML元素的CSS属性,以及JavaScript中的变量类型(`var`、`let`、`const`)和数据类型(基本数据类型与引用数据类型)。通过实例代码详细解释了JavaScript的核心概念,适合初学者入门学习。
70 1
【EMNLP2024】基于多轮课程学习的大语言模型蒸馏算法 TAPIR
阿里云人工智能平台 PAI 与复旦大学王鹏教授团队合作,在自然语言处理顶级会议 EMNLP 2024 上发表论文《Distilling Instruction-following Abilities of Large Language Models with Task-aware Curriculum Planning》。
JavaScript算法和数据结构:写一个二分查找的函数。
JavaScript算法和数据结构:写一个二分查找的函数。
63 0

热门文章

最新文章