前端学数据结构与算法(二):数组的操作特性与栈的应用

前言

数据结构与算法有相互依存的关系,如果将这个两个又进行划分,无疑数据结构又是这座大厦的基础。首先从线性数据结构开始,介绍大家耳熟能详的数据结构-数组。因为JavaScript已经为数组封装了很多增删改查以及遍历的方法,这里就不再赘述具体API了。而后半部分将使用数组实现一种受限的数据结构-栈。最后会解题几道leetCode上与栈相关的题目,方便更加深入理解这种受限数据结构的用途。

数组特性

重温一下上一章复杂度分析最后留下的一个示例,它的时间复杂度是多少:

function test(arr) {
	let len = arr.length
    for (let i = 0; i < len; i++) {
    	arr.shift()
    }
}

通过上一章的知识点,我们很容易知道,一层循环嘛。那就是O(n)复杂度,但这里并非如此,复杂度应是O(n²),至于为什么,首先从数组的特性开始说起。

数组的定义

从百度百科里数组的定义,可以了解数组主要有以下特性:

  • 存储多个相同类型的集合
  • 长度固定
  • 占用连续的存储空间

但是在JavaScript中,数组的特性基本都不符合以上三条。首先可以存放JavaScript里任意不同的数据到同一个数组里;然后长度是可以动态扩容的;最后绝大部分情况下确实是占用连续的存储空间,但如果是以下情况:

const arr = ['a', 'b']

arr[10000000000] = 'c'

JavaScript中不会去开辟这么大的连续的内存,仅仅存储这3个变量,而是使用哈希表(散列表)这种数据结构去存储,这样的话占用的内存虽然不是连续的,但是节约了存储空间,不过因为访问的key需要通过哈希函数转次手,所以访问效率会低于连续存储的数组。JavaScript里的数组为何与其他语言的相差这么多,仅仅是因为是在传统数组上进行了再一次的底层封装,才让其使用这么灵活。

数组的增删查

一般考量一个数据结构的性能,主要从增删查三个基本操作分别考量,因为改你只需要查到这个元素即可。不同场景下的这几种基本操作频率的不同,从而也决定了使用哪种数据结构更为高效。

往数组里增加元素,不同的位置时间复杂度并不相同,我们分别来分析首位、中间部位、尾部三种情况。例如我在数据的首位增加一条数据:

const arr = [1, 2, 3, 4];

arr.unshift(0)
原数组会变成[0, 1, 2, 3, 4],原来数组的第一位变为新插入的元素,旧数据整体向后移动一位,所以时间复杂度是O(n)

从中间部位插入元素时,插入之前的元素不用移位,但是之后的元素还是需要整体后移,所以时间复杂度依然还是O(n);但如果是从数组的最后插入元素时,前面所有的元素都不需要移动,数组末尾添加一个元素即可,所以时间复杂度是O(1)

从上面增加元素的表现可以看出来,数组的特性是,只要里面的元素位置会发生变动,就需要搬家这个操作,所以删除操作依然如此。只要不是删除的最后一个元素,其他位置元素的删除都需要O(n)复杂度,如果是删除最后一个元素,那一样只需要O(1)

再看本章开头的那段实例,即使是只使用一层的循环,也可以理解为什么时间复杂度依然会是O(n²),这是数组的特性决定的。而shift方法也只是封装的方法,该方法在其内部会执行O(n)的操作。

function test(arr) {
	let len = arr.length
    for (let i = 0; i < len; i++) {
    	arr.shift() // 每一次操作都需要整体搬家
    }
}

数组最重要的特性,那就是根据下标访问数组内的元素,无论是任何位置,时间复杂度都是O(1)。当然如果你需要访问到对应某个值,还是需要O(n)的复杂度去遍历。

我们对数组操作API做了简单了解,随机访问是数组的优势,或仅仅在数组的末尾增加与删除操作也是O(1)的操作,其他情况都是O(n)的复杂度。

受限的数据结构-栈

可以把栈想象成是叠盘子这个行为,当我们开始摞的时候是放在之前盘子的上面,而取的时候是从最上面的盘子开始拿。栈是一种遵从后进先出的有序数据集合,一头堵死,最先进入栈的元素,最后出栈。

对上面数组的增删查分析我们知道,在数组的最后一位进行增加与删除都是O(1)的复杂度,所以非常适合用来实现栈这种数据结构。其实完全可以把数组当栈使用,但实现栈的目的就是为了只暴露少量的接口供外面使用,防止有中间的过多操作。我们用数组来实现一个栈:

class Stack {
  constructor() {
    this._data = []
  }
  push(e) {
    this._data.push(e)
  }
  pop() {
    return this._data.pop()
  }
  size() {
  	return this._data.length
  }
}

实现栈的方式不仅仅只有数组,用对象、链接都没问题,只不过数组有封装好的对应方法,用其他方式需要自己手写pushpop操作而已。

LeetCode解题

正是由于栈的受限,往往再处理特定问题时,逻辑会更清晰。

20.有效的括号 ↓

给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
有效字符串需满足:
  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
示例:
  "()[]{}"  // true
  "([)]"    // false
  "{[]}"  // true

这是一个使用栈解决的经典的问题:思路就是创建一个栈,遇到左括号时就入栈,遇到右括号时就弹出栈顶元素,看当前的括号是否与弹出的匹配,只要有一次不匹配,就返回false,最后检查该栈是否为空即可。

代码如下:

var isValid = function (s) {
    const leftBrackets = '([{'
    const brackets = {
        ')': '(',
        ']': '[',
        '}': '{'
    }
    const stack = new Stack()
    for (const c of s) {
        if (leftBrackets.indexOf(c) > -1) {
            stack.push(c) // 左括号就入栈
        } else {
            const d = stack.pop() // 弹出栈顶元素
            if (d !== brackets[c]) { // 是否匹配
                return false
            }
        }
    }
    return stack.size() === 0 // 是否为空
};

71.简化路径 ↓

以Unix风格给出一个文件的绝对路径,将其转换为规范路径。
一个点(.)表示当前目录本身;
此外,两个点(..)表示将目录切换到上一级(指向父目录);
两者都可以是复杂相对路径的组成部分。
请注意,返回的规范路径必须始终以斜杠 / 开头,并且两个目录名之间必须只有一个斜杠 /。
最后一个目录名(如果存在)不能以 / 结尾。此外,规范路径必须是表示绝对路径的最短字符串。
示例:
  输入:"/a/./b/../../c/"
  输出:"/c"
  
  输入:"/a/../../b/../c//.//"
  输出:"/c"
  
  输入:"/a//b////c/d//././/.."
  输出:"/a/b/c"

解题思路:首先使用split按照/进行路径分割,因为两个目录之间的多个/只能有一个斜杠,这样多个连续/被分割后,中间存在的只是空字符串,而空字符串和.对当前的目录路径没有影响,只有遇到..会返回上一级的目录,依然使用栈解决。

代码如下:

var simplifyPath = function (path) {
    const stack = new Stack() // 添加join方法
    const pathArr = path.split('/')
    for (const s of pathArr) {
        if (s === '' || s === '.') {
            continue;
        } else if (s === '..') {
            stack.pop()
        } else {
            stack.push(s)
        }
    }
    return '/' + stack.join('/')
};

150.逆波兰表达式求值 ↓

有效的运算符包括 +, -, *, / 。每个运算对象可以是整数,也可以是另一个逆波兰表达式,求表达式的值。
示例:
  输入: ["4", "13", "5", "/", "+"]
  输出: 6
  解释: 该算式转化为常见的中缀算术表达式为:(4 + (13 / 5)) = 6
  
  输入: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
  输出: 22
  解释: 
  该算式转化为常见的中缀算术表达式为:
    ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
  = ((10 * (6 / (12 * -11))) + 17) + 5
  = ((10 * (6 / -132)) + 17) + 5
  = ((10 * 0) + 17) + 5
  = (0 + 17) + 5
  = 17 + 5
  = 22

解题思路:观察这个转换表达式求值运算的过程可以发现,没有*/优先级高于+-这么一说,只是根据运算符出现先后顺序计算。所以我们依然创建一个栈,只要遇到的是数字就压入栈,如果遇到运算符就从栈里弹出两个数字参与运算,将运算的结果再一次压入栈内即可,直到表达式全部运算完成。

代码如下:

const SIGN = {
  '*': (a, b) => a * b,
  '/': (a, b) => a / b | 0, // 向下取整
  '+': (a, b) => a + b,
  '-': (a, b) => a - b
}

var evalRPN = function(tokens) {
  const stack = new Stack()
  tokens.forEach(item => {
    if (item in SIGN) { // 是运算符
      const b = stack.pop()
      const a = stack.pop() // 弹出两个
      const res = SIGN[item](a, b)
      stack.push(res) // 结果再压入栈
    } else {
      stack.push(+item) // 是数字直接压入栈
    }
  })
  return stack.pop()
};

理解栈这种数组结构非常重要,后续的章节还会探讨递归相关的问题,而递归的实现也就是调用了系统的函数调用栈;同样理解数组的增删查原理也很重要,它能让我们避免陷入以为代码越短效率越高的陷阱,因为增删查的API只是JavaScript替我们封装的而已,很多操作内部依然是O(n)

最后

还是留一个题目,这个题目不是力扣上的,可以挑战下,如下:

计算字符串表达式的值:
"3+8*5-6/3"           // 41
"1+2*2-6+8/2*3-4"     // 7

提示:
  使用两个栈

本章github源码

这是一个系列文章,这个仓库里,会更加完整的收录文章内的代码与力扣题解,同时也会不定期编写力扣题解丰富这个仓库,欢迎大家收录。

下一篇
举报

扫码关注云+社区

领取腾讯云代金券