TypeScript 实战算法系列(一):实现数组栈与对象栈

Easter79
• 阅读 572

TypeScript 实战算法系列(一):实现数组栈与对象栈

本文由图雀社区认证作者 神奇的程序员 写作而成,图雀社区将连载其TypeScript 实战算法系列,点击阅读原文查看作者的掘金链接,感谢作者的优质输出,让我们的技术世界变得更加美好😆

前言

栈作为一种数据结构,它可以应用在很多地方,当你需要经常获取刚存放进去的数据时,那么栈这种数据结构将是你的首选。
栈的实现方式一般有两种:数组实现和对象实现,这两种实现方式最终实现的功能都是一样的,但是在性能上却有着很大的差别。
本文将详细讲解这两种实现方式的差异并用TypeScript将其实现,欢迎各位感兴趣的开发者阅读本文。

数组实现栈

本文讲解的是栈用代码的实现,如果对栈这种数据结构还不是很了解的话,可以移步我的另一篇文章:栈与队列

实现思路

栈的核心思想为后进先出(LIFO),那么我们可以用数组来描述栈。
接下来,我们来看下,一个栈都需要具备哪些功能:

  • 入栈,添加一个新元素至栈顶( 数组的末尾)。

  • 出栈,将栈顶的元素移除并返回被移除的元素。

  • 获取栈顶元素,获取当前栈顶元素返回。

  • 判断栈是否为空,判断栈( 数组)内是否有数据。

  • 清空栈,移除栈内所有的元素。

  • 获取栈大小,返回栈里的元素个数。

  • 输出栈内数据,将栈中的所有元素以字符串的形式返回。

我们分析完栈都需要具备哪些功能后,发现数组中提供了很多现成的API可以实现上述功能,接下来,跟大家分享下上述功能的实现思路。

  • 入栈( push),可以使用数组的push方法直接往数组的末尾添加元素。

  • 出栈( pop),可以使用数组的pop方法直接移除栈中的元素,该方法会返回当前被移除的元素。

  • 栈顶元素( peek),可以通过数组的长度-1获取到数组中的最后一个元素。

  • 栈是否为空( isEmpty),可以通过判断数组的长度是否为0来实现。

  • 清空栈( clear),可以将数组直接赋值为空或者调用出栈方法直至栈中的数据为空。

  • 栈大小( size),可以返回数组的长度。

  • 输出栈内数据,可以调用数组的toString方法将数组转换为字符串。

实现代码

有了实现思路后,我们就可以将上述实现思路转换为代码了。

  • 新建一个Stack.ts文件

  • 定义栈并规定其类型

    private items: any[];

  • 在构造器中初始化栈

    constructor() { this.items = []; }

  • 根据实现思路实现栈中的函数

    // 入栈 push(item:any) { this.items.push(item); } // 出栈 pop() { return this.items.pop(); } // 返回栈顶元素 peek() { return this.items[this.items.length - 1]; } // 判断栈是否为空 isEmpty() { return this.items.length === 0; } // 清空栈栈内元素 clear() { this.items = []; } // 获取栈内元素数量 size():number{ return this.items.length; } // 将栈内元素转为字符串 toString(){ return this.items.toString(); }

完整代码请移步:Stack.ts

编写测试代码

上述代码我们实现了一个栈,接下来我们往栈中添加几条数据,测试栈内的方法是否正确执行。

  • 新建一个StackTest.js文件

  • 实例化一个栈

    const stack = new Stack();

  • 测试栈内方法是否正确执行

    // 入栈stack.push("第一条数据");stack.push("第二条数据");// 出栈stack.pop();// 返回栈顶元素console.log(stack.peek());// 查看栈大小console.log(stack.size());// 判断栈是否为空console.log(stack.isEmpty());// 返回栈内所有元素console.log(stack.toString())// 清空栈stack.clear()

完整代码请移步:StackTest.js
执行结果如下
TypeScript 实战算法系列(一):实现数组栈与对象栈

对象实现栈

实现一个栈最简单的方式是通过数组存储每一个元素。在处理大量数据时,我们需要评估如何操作数据是最高效的。
在使用数组时,大部分方法的时间复杂度都为O(n),我们需要迭代整个数组直至找到目标元素,在最坏的情况下我们需要迭代数组的每一个位置。数组是元素的一个有序集合,为了保证元素排列有序,它会占用更多的内存空间。
如果我们可以直接获取元素,占用更少的内存空间,并且仍然保证所有元素都按照我们的需要进行排列,就属于最优解决方案了。

实现代码

我们可以使用一个对象来存储所有的栈元素,保证它们的顺序并且遵循LIFO原则。接下来我们来看看如何使用对象来实现栈。

  • 新建一个ObjStack.ts文件

  • 定义栈对象结构

    interface StackObj { [propName: number] : any;}

  • 定义栈并规定其类型,count用于记录栈的大小。

    private items: StackObj;private count: number;

  • 在构造器中初始化栈相关变量

    this.items = {};this.count = 0;

  • 入栈,当前栈的大小为新元素的key。

    push(item: any) { this.items[this.count] = item; this.count++;}

  • 出栈,当前栈大小-1,取出栈顶元素,删除栈顶元素,返回取出的栈顶元素

    pop() { if(this.isEmpty()){ return undefined; } this.count--; const result = this.items[this.count]; delete this.items[this.count]; console.log(this.items); return result;}

  • 返回栈顶元素,以当前栈大小-1为key获取其对应的value值。

    peek() { if(this.isEmpty()){ return undefined; } return this.items[this.count - 1];}

  • 判断栈是否为空,清空栈内元素,获取栈内元素数量

    // 判断栈是否为空isEmpty() { return this.count === 0; }// 清空栈内元素clear() { this.items = []; this.count = 0;}// 获取栈内元素数量size():number{ return this.count;}

  • 将栈内元素转为字符串,遍历当前栈对象中的数据,将栈中的数据用逗号拼接并返回。

    toString(){ if (this.isEmpty()){ return ""; } let objString = ${this.items[0]}; for (let i = 1; i < this.count; i++){ objString = ${objString},${this.items[i]} } return objString;}

完整代码请移步:ObjStack.ts

编写测试代码

上述代码我们用对象实现了一个栈,接下来我们往栈中添加几条数据,测试栈内的方法是否正确执行。

  • 新建一个StackObjTest.js文件

  • 实例化一个栈

    const stack = new ObjStack();

  • 测试栈内方法是否正确执行

    // 入栈stack.push("第一条数据");stack.push("第二条数据");// 出栈stack.pop();// 返回栈顶元素console.log(stack.peek());// 查看栈大小console.log(stack.size());// 判断栈是否为空console.log(stack.isEmpty());// 返回栈内所有元素console.log(stack.toString())// 清空栈stack.clear()

完整代码请移步:StackObjTest.js
执行结果如下
TypeScript 实战算法系列(一):实现数组栈与对象栈

二者的区别

数组大部分方法的时间复杂度都为O(n),数组中的元素是一个有序集合,为了保证元素排列有序,它会占用更多的内存空间。
对象可以通过key直接访问到目标元素时间复杂度为O(1),我们可以直接目标元素进行操作,速度明显比数组快了很多倍。
接下来,我们通过一个实例来看看这两者在执行速度上的差异。

十进制转二进制

把十进制转为二进制,需要将该十进制除以2并对商取整,直到结果是0为止。

  • 声明一个函数参数为一个十进制数

    const decimalToBinaryStack = function (decNumber) {}

  • 函数内部声明一个变量,用于接收当前传进来的参数进行除法运算后得到的值。

    // 传进来的十进制数let number = decNumber;

  • 函数内部实例化一个栈,用于保存模运算后得出的值。

  • 函数内部声明两个变量,用户保存当前模运算的值和最终生成的二进制字符串

    // 余数let rem;// 二进制结果let binaryString = "";

  • while循环,判断当前参数进行除法运算后得到的值是否为0,如果不为0就对当前结果进行模运算,将模运算得到的值入栈,对当前结果进行除法运算,直至当前结果为0。

    while (number > 0) { // 模运算 rem = Math.floor(number % 2); // 将余数入栈 stack.push(rem); // 当前十进制结果除以二 number = Math.floor(number / 2);}

  • while循环,将栈中的数据取出拼接到二进制结果字符串中去

    while (!stack.isEmpty()) { binaryString += stack.pop().toString();}

  • 返回二进制结果字符串

    return binaryString;

完整代码请移步:Examples.js

实现代码如上所述,唯一不同的就是一个使用的是对象栈一个使用的数组栈,接下来我们来看下不同栈的运行时间差距。TypeScript 实战算法系列(一):实现数组栈与对象栈

写在最后

  • 公众号无法外链,如果文中有链接,可点击下方阅读原文查看😊

❤️爱心三连击

1.看到这里了就点个在看支持下吧,你的在看是我创作的动力。

2.关注公众号图雀社区「带你一起学优质实战技术教程」

3.特殊阶段,带好口罩,做好个人防护。

4.添加微信【little-tuture】,拉你进技术交流群一起学习。

                 ● 前端基础进阶(一):JavaScript 内存空间详细图解 
                 ● 最简实现Promise,支持异步链式调用(20行) 
                 ● 你不知道的 Webpack(4000字,手写源码) 
                 
                
               
              
             
            
           
          
         
       
   
      
      
      
  
     
     
     
 
    
    
    

   
   
   

·END·

图雀社区

汇聚精彩的免费实战教程

TypeScript 实战算法系列(一):实现数组栈与对象栈

关注公众号回复 z 拉学习交流群

喜欢本文,点个“在看”告诉我

TypeScript 实战算法系列(一):实现数组栈与对象栈

本文分享自微信公众号 - 图雀社区(tuture-dev)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Wesley13 Wesley13
3年前
java将前端的json数组字符串转换为列表
记录下在前端通过ajax提交了一个json数组的字符串,在后端如何转换为列表。前端数据转化与请求varcontracts{id:'1',name:'yanggb合同1'},{id:'2',name:'yanggb合同2'},{id:'3',name:'yang
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
待兔 待兔
4个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Wesley13 Wesley13
3年前
MySQL 的慢 SQL 怎么优化?
!(https://oscimg.oschina.net/oscnet/7b00ec583b5e42cc80e8c56c6556c082.jpg)Java技术栈www.javastack.cn关注阅读更多优质文章(https://www.oschina.net/action/GoToLink?urlhttp
Wesley13 Wesley13
3年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Easter79 Easter79
3年前
TypeScript 实战算法系列(十四):实现二叉搜索树
!(https://oscimg.oschina.net/oscnet/14bf276948e54283aff2632b9c5899e4.png)本文由图雀社区认证作者 神奇的程序员 写作而成,图雀社区将连载其TypeScript实战算法系列,点击阅读原文查看作者的掘金链接,感谢作者的优质输出,让我们的技术世界变得更加美
Python进阶者 Python进阶者
10个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这
Easter79
Easter79
Lv1
今生可爱与温柔,每一样都不能少。
文章
2.8k
粉丝
5
获赞
1.2k