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
分享
相关文章
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
68 1
|
8天前
|
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
125 75
|
8天前
|
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
34 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
8天前
|
【C++数据结构——栈与队列】链栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现链栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储整数,最大
34 9
|
8天前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
27 7
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
31 2
探索局域网电脑监控软件:Python算法与数据结构的巧妙结合
在数字化时代,局域网电脑监控软件成为企业管理和IT运维的重要工具,确保数据安全和网络稳定。本文探讨其背后的关键技术——Python中的算法与数据结构,如字典用于高效存储设备信息,以及数据收集、异常检测和聚合算法提升监控效率。通过Python代码示例,展示了如何实现基本监控功能,帮助读者理解其工作原理并激发技术兴趣。
56 20
|
22天前
|
【算法】栈
栈相关算法题,供参考,附有链接地址及板书
Python 中的数据结构和算法优化策略
Python中的数据结构和算法如何进行优化?
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
79 1

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等