JavaScript数据结构之栈

1,662 阅读8分钟

总结一下这两天学习js数据结构中的栈

不学不知道,一学吓一跳。可以利用数据结构的思想来实现一些算法,能把原本O(n^2)的时间复杂度降低到O(1),虽然只是对一些数组的api进行封装

为什么学习数据结构

1.语言是相通的吗

经常听很多前辈说,编程语言是相通的,掌握了一门,其他语言就就很容易掌握,但是个人认为每门语言都有自己的优缺点,都有自己能胜任的地方,也都有自己无能为力的地方。 比如说让我们前端工程师踏入后端领域的node.js,也只是在很多公司作为中间层来使用,并不能像java,c那样来真正的代替后端。 比如说机器语言python,这样近乎万能的语言,在面对高性能计算的时候,利用的很多python库,底层也都是c语言实现的。 所以个人认为真正相通的不是语言,而是数据结构和算法。 数据结构和算法是脱离编程语言而存在的,不同的语言有不同的实现,但内在的逻辑不会有变化,所体现的编程思想不会有变化。

2.一段亲身经历

在之前的面试中,去了一家是线上课程的公司,当时笔试和前两面都比较顺利,到了终面部门负责人的时候,懵圈了。那位大佬是计算机出身的前百度高级工程师,特别注重数据结构和算法。寒暄了几句后开始进入了主题,(噩梦的开始)看了我写的笔试题后,问我为什么这个快排这样写?我当时写的阮一峰老师的版本, 我没说话,然后又问我,你不知道这样写不仅时间复杂度会加大,连空间复杂度都会消耗吗?我懵圈的摇了摇头,然后又问我,你知道堆排序吗?我又懵圈的摇了摇头,然后又问我,你知道时间复杂度吗?我又无奈的摇了摇头;然后大佬放弃了,不再问了,开始了对我的评价,你连这最基本的数据结构都不知道,怎么能知道你的代码是好是坏呢,如果遇到bug别人半个小时能解决的,你说不定得用两个小时。。。深刻教育了一番出去和hr谈话了,最后的结果虽然是拿到offer了,但是级别定的低,money也给的少。 我一直以为前端和数据结构和算法无关,能实现业务功能就行,但是经过这次面试后,我打破了之前的观点,就算写业务,也有写的好也有写的一般的,之前的嵌套循环,每一层都把时间复杂度提高了一个档次,所以决定重头学起数据结构和算法。

3.学习数据结构的目标

数据结构的精髓在于总结提炼了许多存储管理和使用数据的模式,这些模式的背后是最精华的编程思想,这些思想的领悟需要时间,不要想当然的认为学会了几种数据结构就可以在工作中大显身手,但学会了数据结构,对自身能力的提升是不言而喻的。


接下来开始主题吧

数据结构之---栈

1.栈的定义

栈是一种特殊的线性表,仅能在线性表的一端操作,栈顶允许操作,栈底不允许操作。栈的特性:先进后出(后进先出)。

下图展示了栈的工作原理

栈某种意义上讲,它像是一个开口的盒子,先放进去的东西总是会被后放进去的东西压在下面,那么如果想拿出被压住的东西,必须要先取出顶部的东西,也就是后放进去的东西。

就像我们日常生活中的羽毛球桶

每次取羽毛球时,都只能从顶部取,最底下的羽毛球,你是取不到的,用完了羽毛球后,也只能从顶部放回去。(当然,特殊情况不考虑)

2.栈的实现

从数据存储的角度看,实现栈有两种方式,一种是以数组做基础,一种是以链表做基础,数组是最简单的实现方式,本文以基础的数组来实现栈。

栈的基本操作包括创建栈、销毁栈、出栈、入栈、获取栈顶元素、获取栈的大小、清空栈。

我们定义以下几个栈的方法:

  • push 添加一个元素到栈顶(向桶里放入一个羽毛球)
  • pop 弹出栈顶元素(从桶里顶部拿出一个羽毛球)
  • top 返回栈顶元素(看一眼桶里最顶端的羽毛球,但是不拿出来)
  • isEmpty 判断栈是否为空(看看羽毛球是不是都用完了)
  • size 返回栈里元素的个数(数一下桶里还有多少羽毛球)
  • clear 清空栈(把桶里的羽毛球都倒出来扔掉)

然后我们利用es6的class的实现以上的方法 新建一个stack.js文件

class Stack {
  constructor() {
    this.items = []; // 使用数组存储数据
  }
  push(item) {
    this.items.push(item); // 往栈里压入一个元素
  }
  pop() {
    return this.items.pop(); // 把栈顶的元素移除
  }
  top() {
    return this.items[this.items.length - 1]; // 返回栈顶的元素
  }
  isEmpty() {
    return this.items.length === 0; //返回栈是否为空
  }
  size() {
    return this.items.length; // 返回栈的大小
  }
  clear() {
    this.items = []; // 清空栈
  }
}

看完上面的代码,是不是觉得很惊讶,这里实现的栈,竟然就只是对数组做了一层封装而已!

只是做了一层封装么?

  • 给你一个数组,你可以通过索引操作任意一个元素,但是给你一个栈,你能操作任意元素么?栈提供的方法只允许你操作栈顶的元素,也就是数组的最后一个元素,这种限制其实提供给我们一种思考问题的方式,这个方式也就是栈的特性,后进先出。
  • 既然栈的底层实现其实就是数组,栈能做的事情,数组一样可以做啊,为什么弄出一个栈来,是不是多此一举?封装是为了更好的利用,站在栈的肩膀上思考问题显然要比站在数组的肩膀上思考问题更方便,后面的练习题你将有所体会。
3.栈的应用

3.1.1 判断括号是否匹配 说说我之前遇到的面试题,给一段字符串,判断里面的括号是否是成对出现 比如说

()ss()ss(sss(ss)(ss)ss) 合法

()ss()ss(sss(ss)(ss)ss)) 不合法

3.1.2 思路分析 括号有嵌套关系,也有并列关系,如果我们用数组或者对象的方法也能解决,今天我们试着用栈来解决这个问题。

  • 遍历字符串
  • 如果是左括号,就压入栈中
  • 如果是右括号,判断栈是否为空,如果不为空,则把栈顶元素移除(也就是在栈中存放的左括号),这对括号就抵消了;如果不为空,就说明缺少左括号,返回false
  • 循环结束后,看栈的大小是否为0,如果不为0,就说明没有成对出现,为0,就说明全部抵消了。

3.1.3 用栈来分析是不是觉得很简单呢,下面看代码实现

{
       function isDouuble(str) {
          const stack = new Stack();
          const len = str.length;
          for (let i = 0; i < len; i++) {
            const item = str[i];
            if (str[i] === "(") {
              stack.push(item); // 入栈
            } else if (item === ")") {
              if (stack.isEmpty()) {
                return false;
              } else {
                stack.pop(); // 出栈
              }
            }
          }
          return stack.size() === 0;
        }
        console.log(isDouuble("()ss()ss(sss(ss)(ss)ss)")); // true
        console.log(isDouuble("()ss()ss(sss(ss)(ss)ss)(")); // false
        console.log(isDouuble("()ss()ss(sss(ss)(ss)ss))")); // false
        console.log(isDouuble("()ss()ss(sss(ss)(ss)ss))(")); // false
      }

3.2.1 实现一个min方法的栈

实现一个栈,除了常见的push,pop方法以外,提供一个min方法,返回栈里最小的元素,且时间复杂度为o(1)

3.2.2 思路分析 可以利用两个栈来实现,一个栈用来存储数据,一个栈用来存储栈里最小的数据; 利用编程中分而治之的思想,就是分开想分开处理

  • 定义两个栈,dataStack 和 minStack;
  • 对于dataStack栈来说,正常的psuh,pop实现就好;
  • 对于minStatck栈来说,它是要存储栈里最小的值,所以当minStack为空的时候,那么push进来的数据就是最小的;如果不为空,此时minStack栈顶的元素就是最小的,如果push进来的元素比栈顶的元素还小,直接push进来就行,这样minStack栈的栈顶始终都是栈里的最小值。

3.2.3 代码实现 (时间复杂度为O(1))

 {
        class MinStack {
          constructor() {
            this.dataStack = new Stack(); // 普通的栈
            this.minStack = new Stack(); // 存储最小值的栈
          }
          // push 和 pop 两个栈都要操作,保持大小统一
          push(item) {
            this.dataStack.push(item); // 常规操作
            if (this.minStack.isEmpty() || item < this.minStack.top()) {
              this.minStack.push(item); // 保证minStack栈顶是最小的值
            } else {
              this.minStack.push(this.minStack.top()); // 保持两个栈的大小一样
            }
          }
          pop() {
            this.minStack.pop();
            return this.dataStack.pop(); // 返回真实的数字
          }
          min() {
            return this.minStack.top(); // 返回最小的数字
          }
        }

        const minstack = new MinStack();
        minstack.push(3);
        minstack.push(2);
        minstack.push(6);
        minstack.push(8);
        console.log(minstack.min()); // 2
        console.log(minstack.pop()); // 8
        minstack.push(1);
        console.log(minstack.min()); // 1
      }
4.栈的小结

栈的底层是不是使用了数组这不重要,重要的是栈的这种后进先出的特性,重要的是我们只能操作栈顶元素的的限制,一定要忽略掉栈的底层如何实现,而只去关心栈的特性。