TypeScript_线性结构-数组-栈结结构

这篇具有很好参考价值的文章主要介绍了TypeScript_线性结构-数组-栈结结构。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

数据结构与算法

面试经典 150 题

编程的最终目的只有一个:对数据进行操作和处理

  • 术之尽头炁体源流
  • 编程尽头数据结构

数据结构与算法的本质就是一门专门研究数据如何组织、存储和操作的科目

系统、语言、框架源码随处可见数据结构与算法

  • 无论是操作系统(Windows、Mac OS)本身,还是我们所使用的编程语言(JavaScript、Java、C++、Python等等)还是我们在平时应用程序中用到的框架(Vue、React、Spring、Flask等等),它们的底层实现到处都是数据结构与算法,所以你要想学习一些底层的知识或者某一个框架的源码(比如 Vue、React的源码)是必须要掌握数据结构与算法的
  • 以前端为例:框架中大量使用到了栈结构、队列结构等来解决问题(比如之前框架源码时经常看到这些数据结构,Vue 源码、React 源码、Webpack 源码中可以看到队列、栈结构、队列结构等来解决问题,Webpack 中还可以看到很多 Graph 图结构)
  • 实现语言或者引擎本身也需要大量的数据结构:哈希表结构、队列结构(微任务队列、宏任务队列),前端无处不在的数据结构:DOM Tree(树结构)、AST(抽象语法树)

因为对于很多企业来说,想要短时间考察一个人的能力以及未来的潜力,数据结构与算法是非常重要的指标,也会成为它们的硬性条件

  • 对于可以将数据结构与算法掌握很好的开发人员来说,通常对于业务的把握肯定是没有问题的
  • 并且对于系统的设计也会更加合理,可以写出更加高效的代码

数据结构

  • 数据结构是数据对象,以及存在于该对象的实例和组成实例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出————《数据结构、算法与应用》
  • 数据结构是 ADT(抽象数据类型 Abstract Data Type)的物理实现————《数据结构与算法分析》
  • 数据结构(data structure)是计算机中存储、组织数据的方式。通常情况下,精心选择的数据结构可以带来最优效率的算法————中文维基百科

图书摆放规则

  • 随便放
    • 插入操作:哪里有空放哪里,一步到位
    • 查找操作:找某本书,累死…
  • 按照书名的拼音字母顺序摆放
    • 插入操作:新进一本《阿Q正传》、《理想国》,按照字母顺序找到位置,插入
    • 查找操作:二分查找法
  • 把书架划分成几个区域,按照类别存放,类别中按照字母顺序
    • 插入操作:先定类别,二分查找确定位置,移出空位
    • 查找操作:先定类别,再二分查找

常见数据结构

  • 数组(Array)
  • 栈结构(Stack)
  • 队列(Queue)
  • 链表(LinkedList)
  • 图结构(Graph)
  • 散列表(Hash)
  • 树结构(Tree)
  • 堆结构(Heap)

算法

解决问题的过程中,不仅仅数据的存储方式会影响效率,算法的优劣也会影响效率

算法

  • 一个有限的指令集,每条指令的描述不依赖于语言
  • 接受一些输入(有些情况下不需要输入)
  • 产生输出
  • 一定在有限步骤之后终止

生活中的算法

  • 找出线缆出题的地方:

    • 假如上海和杭州之间有一条高架线,高架线长度是 100000 米,有一天高架线中有其中一米出现了故障
    • 请你想出一种算法,可以快速定位到出问题的地方
  • 线性查找:

    • 从上海的起点开始一米一米的排查,最终一定能找到出问题的线段
    • 但是如果线段在另一头,我们需要排查 100000 次,这是最坏的情况,平均需要 50000 次
  • 二分查找:

    • 从中间位置开始排查,看一下问题出在上海到中间位置,还是中间到杭州的位置
    • 查找对应的问题后,再从中间位置分开,重新锁定一般的路程
    • 最坏的情况,需要多少次可以排查完呢?最坏的情况是20次就可以找到出问题的地方
    • 怎么计算出来的呢?log(100000,2),以 2 为底,100000 的对数 ≈ 20
  • 结论:

    你会发现,解决问题的办法有很多,但是好的算法对比于差的算法,效率天囊之别

线性结构

线性结构(Linear List)是由 n(n>=0)个数据元素(结点)a[0]、a[1]、a[2]…a[n-1]组成的有限序列

  • 数据元素的个数 n 定义为表的长度=list.length()list.length()=0 时称为空表)
  • 将非空的线性表(n>=1)记作:(a[0]、a[1]、a[2]…a[n-1])
  • 数据元素 a[i](0<=i<=n-1)只是个抽象符号,其具体含义在不同情况下可以不同

上面是维基百科对于线性结构的定义,有一点点抽象,其实我们只需要记住几个常见的线性结构即可

  • 数据结构(Array)
  • 栈结构(Stack)
  • 队列结构(Queue)
  • 链表结构(LinkedList)

数组

  • 几乎每种编程语言都会提供一种原生数据结构
  • 并且我们可以借助数组结构来实现其他的数据结构,比如栈(Stack)、队列(Queue)、堆(Heap)

通常数组的内存是连续的,所以数组在知道下标值的情况下,访问效率是非常高的

TypeScript_线性结构-数组-栈结结构,数据结构与算法,typescript

  • 栈也是一种非常常见的数据结构,并且在程序中的应用非常广泛
  • 数组
    • 我们知道数组是一种 线性结构,并且可以在数组的 任意位置 插入和删除数据
    • 但是有时候,我们为了实现某些功能,必须对这种 任意性 加以 限制
    • 栈和队列 就是比较常见的受限的线性结构

TypeScript_线性结构-数组-栈结结构,数据结构与算法,typescript

栈(Stack),它是一种受限的数据结构,后进先出(LIFO)

  • 其限制是仅允许在 表的一端 进行插入和删除运算。这一端被称为 栈顶,相对地,把另一端称为 栈底
  • LIFO(last in first out)表示就是后进入的元素,第一个弹出栈空间。类似于自动餐托盘,最后放上的托盘,往往先把它拿出去使用
  • 向一个栈插入新元素又称作 进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为栈顶元素
  • 从一个栈删除元素又称作出 栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素

题目

有六个元素 6、5、4、3、2、1 的顺序进栈,问下面哪一个不是合法的出栈序列?

  • 5、4、3、6、1、2
  • 4、5、3、2、1、6
  • 3、4、6、5、2、1 ×
  • 2、3、4、1、5、6

实现栈结构有两种比较常见的方式:

  • 基于数组实现
  • 基于链表实现

实现栈

  • 创建一个 Stack,用户创建栈的类,可以顶一个泛型类
  • 在构造函数中,定义了一个变量(数组类型),这个变量可以用于保存当前栈对象中所有的元素
  • 之后不论是压栈操作还是出栈操作,都是从数组中添加和删除元素
class Stack<T> {
  private data: T[] = []
}

在 node 环境下执行 ts 代码

$ npm i -g ts-node

栈的操作

  • push(element):添加一个新元素到栈顶位置
  • pop():移除栈顶的元素,同时返回被移除的元素
  • peek():返回栈顶的元素,不会对栈做任何修改
  • isEmpty():如果栈里面没有任何元素就返回 true,否则返回 false
  • size():返回栈里的元素个数。这个方法和数组的 length 属性很类似
class ArrayStack {
  private data: any[] = []
  // push:将一个元素压入栈中
  push(element: any) {
    this.data.push(element)
  }
  // pop:将栈顶元素弹出栈(返回出去,并且从栈顶移除)
  pop(): any {
    return this.data.pop()
  }
  // peek:看一眼栈顶元素,但是不进行任何操作
  peek(): any {
    return this.data[this.data.length - 1]
  }
  // isEmpty:判断栈是否为空
  isEmpty(): boolean {
    return this.data.length === 0
  }
  // size:返回栈的数据个数
  size(): number {
    return this.data.length
  }
}

const stack1 = new ArrayStack()
stack1.push('aaa')
stack1.push('bbb')

console.log(stack1.peek())
console.log(stack1.pop())
console.log(stack1.pop())
console.log(stack1.isEmpty())
console.log(stack1.size())

泛型重构栈

class ArrayStack<T> {
  private data: T[] = []
  push(element: T) {
    this.data.push(element)
  }
  pop(): T | undefined {
    return this.data.pop()
  }
  peek(): T | undefined {
    return this.data[this.data.length - 1]
  }
  isEmpty(): boolean {
    return this.data.length === 0
  }
  size(): number {
    return this.data.length
  }
}

接口抽离和封装

import { IStack } from './IStack'

class LinkedStack<T> implements IStack<T> {
  private data: T[] = []
  push(element: T) {
    this.data.push(element)
  }
  pop() {
    return this.data.pop()
  }
  peek() {
    return this.data[this.data.length - 1]
  }
  isEmpty() {
    return this.data.length === 0
  }
  size() {
    return this.data.length
  }
}

使用接口定义栈的结构

interface IStack<T> {
  push(element: T): void
  pop(): T | undefined
  peek(): T | undefined
  isEmpty(): boolean
  size(): number
}

export { IStack }

十进制转二进制

为什么需要十进制转二进制

  • 现实生活中,我们主要使用十进制
  • 在计算机科学中,二进制非常重要,因为计算机里所有内容都是二进制数字表示的(0 和 1)
  • 没有十进制和二进制相互转换的能力,与计算机交流就很困难
  • 转换二进制是计算机科学和编程领域中经常使用的算法

如何实现十进制转二进制

  • 要把十进制转换成二进制,我们可以将十进制数字和 2 整除(二进制是满二进一),直到结果是 0 为止
import ArrayStack from './stack_refactor'

function decimalToBinary(decimal: number): string {
  // 1.创建一个栈,用于存放余数
  const stack = new ArrayStack<number>()

  // 2.使用循环 while(不确定次数,只知道循环结束条件) for(知道循环的次数)
  while (decimal > 0) {
    const result = decimal % 2
    stack.push(result)
    decimal = Math.floor(decimal / 2)
  }

  // 3.所有的余数都已经放在 stack 中,依次取出即可
  let binary = ''
  while (!stack.isEmpty()) {
    binary += stack.pop()
  }
  return binary
}

有效括号

20.有效括号

给定一个只包括 ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ 的字符串 s ,判断字符串是否有效

有效字符串需满足:文章来源地址https://www.toymoban.com/news/detail-692959.html

  • 左括号必须用相同类型的右括号闭合
  • 左括号必须以正确的顺序闭合
  • 每个右括号都有一个对应的相同类型的左括号
import ArrayStack from './stack_refactor'

function isValid(s: string): boolean {
  // 创建栈结构
  const stack = new ArrayStack<string>()
  // 2.遍历s中所有的括号
  for (let i = 0; i < s.length; i++) {
    const c = s[i]
    switch (c) {
      case '(':
        stack.push(')')
        break
      case '{':
        stack.push('}')
        break
      case '[':
        stack.push(']')
        break
      default:
        if (c !== stack.pop()) return false
        break
    }
  }
  return stack.isEmpty()
}

到了这里,关于TypeScript_线性结构-数组-栈结结构的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构与算法——TypeScript】算法的复杂度分析、 数组和链表的对比

    什么是算法复杂度(现实案例)? ❤️‍🔥 前面已经解释了什么是算法? 其实就是解决问题的一系列步骤操作、逻辑。 ✅ 对于同一个问题,我们往往有很多种解决思路和方法,也就是可以采用不同的算法。 举个例子(现实例子):在一个庞大的图书馆中,我们需要找一本书

    2024年02月14日
    浏览(53)
  • 数据结构与算法之堆: Leetcode 215. 数组中的第K个最大元素 (Typescript版)

    数组中的第K个最大元素 https://leetcode.cn/problems/kth-largest-element-in-an-array/ 描述 给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。 请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。 你必须设计并实现时间复杂度为 O(n) 的算法解决此

    2024年02月07日
    浏览(53)
  • 线性数据结构:数组、受限数组(栈、队列)、线性表

      数组(Array)是有序的元素序列。属于线性结构(有且仅有一个前驱、有且仅有一个后继)。   数组的关键在于在内存中的物理地址对应的是 一段连续的内存 。这意味着如果想要在任意位置删除/新增一个元素,那么该位置往后的所有元素,都需要往前挪/往后挪一个位

    2024年03月09日
    浏览(53)
  • 数据结构——线性数据结构(数组,链表,栈,队列)

    数组(Array) 是一种很常见的数据结构。它由相同类型的元素(element)组成,并且是使用一块连续的内存来存储。 我们直接可以利用元素的索引(index)可以计算出该元素对应的存储地址。 数组的特点是: 提供随机访问 并且容量有限。 2.1. 链表简介 链表(LinkedList) 虽然是

    2024年02月11日
    浏览(44)
  • 5:数据结构--5.1:线性结构,5.2:数组与矩阵

     转上一节: 考点1:线性表 1:线性表 顺序表:数据在内存中紧邻。 (1)顺序存储方式:数组的内存是连续分配的,并且是静态分配的,即在使用数组之前需要分配固 定大小的空间。  (2)链表(linked-list)存储方式:链表的内存是不连续的,前一个元素存储地址的下一个地址

    2024年04月09日
    浏览(57)
  • 【数据结构与算法——TypeScript】图结构(Graph)

    认识图结构以及特性 什么是图? 在计算机程序设计中, 图结构 也是一种非常常见的数据结构。 但是, 图论 其实是一个非常大的话题 认识一下关于图的一些内容 图的抽象数据类型 一些算法实现。 什么是图 ? 图结构是一种与 树结构 有些相似的数据结构。 图论 是 数学 的一

    2024年02月12日
    浏览(44)
  • 【数据结构与算法——TypeScript】哈希表

    哈希表介绍和特性 哈希表是一种非常重要的数据结构,但是很多学习编程的人一直搞不懂哈希表到底是如何实现的。 在这一章节中,我门就一点点来实现一个自己的哈希表。 通过实现来理解哈希表背后的原理和它的优势。 几乎所有的编程语言都有直接或者间接的应用这种数

    2024年02月13日
    浏览(42)
  • 算法 数据结构分类 数据结构类型介绍 数据结构线性非线性结构 算法合集 (一)

     数据结构分为:                            a.线性结构                            b.非线性结构  a.线性结构:                       数据与结构存在一对一的线性关系; a . 线性结构 存储 分为:                                   顺序存储

    2024年02月10日
    浏览(53)
  • 数据结构之线性表的类型运用Linear Lists: 数组,栈,队列,链表

    定义 一个最简单,最基本的数据结构。一个线性表由多个相同类型的元素穿在一次,并且每一个元素都一个前驱(前一个元素)和后继(后一个元素)。 线性表的类型 常见的类型:数组、栈、队列、链表 这些不同数据结构的特性可以解决不同种类的问题 题面 题目描述 有

    2024年02月12日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包