[数据结构与算法-小白系列]第1️⃣天栈、队列

自己给自己写个序

本人算法小白,文章主要分享自己学习算法的过程,文章不求高深只求 通俗易懂,如果你同样对算法一窍不通欢迎关注我,毕竟负负得正💯 如果你通过此篇文章学到了一丢丢知识,欢迎点赞支持一下哟💋

第一天学点啥?

很多学习数据结构与算法的教程第一节会讲时间复杂度和空间复杂度,但对于算法小白而言,我们关心程序的复杂度吗? 老子能把程序写出来就不错了! 同意的老铁来波666

用啥语言写代码?

答: 当然是我们的javascript了!

又问: 那为啥用javascript?

又答: 因为javascript是一种解释性语言，其提供了一个非常方便的开发过程,在使用前不像一些语言需要先编译,javascript上可运行在浏览器下可运行在服务器,可谓神通广大无所不能...

不比比了,主要的原因是只会javascript

题外篇:
现在很多公司团队在分析技术选型的时候一顿比比,比如讨论项目是用Vue还是React时

负责人曰:

通过xxxx分析,最后我们确定用Vue

实际上

我们只会Vue

好了,比比的差不多了,要进入正题了👌

什么是数据结构

可以分开来理解 数据&结构,举个栗子

场景:家里有颗苹果树,苹果熟了,需要把苹果摘下放起来

方案:为了方便吃,我们打算把苹果统一放在篮子里

这里,我们可以把苹果看做是数据 把苹果放到篮子里面看做是存储数据的结构

有人可能会问,那为什么我们不把苹果放在麻袋里?别忘了我们的前提是 方便吃 显然放在篮子里面比放在麻袋里面更方便我们拿取苹果来吃,这就是根据不同的场景,选择不同放苹果的方案,也就是根据不同的场景选择不同的 数据存储结构

栈(先进后出)

继续拿吃苹果的例子:

这个时候苹果多了,为了更加的方便吃苹果,我们打算把生的苹果放在下面, 把熟苹果放在上面,这样我们在吃苹果的时候 从上而下 拿,可以优先吃熟苹果。

分析:

为什么我们要把苹果 排个序?(熟在上,生在下)

本质上说,是为了方便吃更多的苹果,优先吃熟的,等熟的吃完了,生的也熟了

但!别忘了我们的前提是苹果多了,假设我们就2个苹果,哪个苹果生哪个苹果熟,我们一眼就可以找到,这个时候就不需要排序了

其实这就是数据结构的本质解决大量数据存储的问题,如果数据量小,管他怎么存,存起来就好了

而这里,我们用的存苹果的方式就是一种栈数据结构,栈要解决的场景就是数据的先进后出

用代码实现栈

这里我们基于数组来实现, 可以理解栈就是数组,只不过对数据的进和出有所规定 (先进后出)

首先我们来熟悉下数组的基本api

push 向数组的最后面插入数据
unshift 向数组的最前面插入数据
pop 取出数组最后一项数据
shift 取出数组第一项数据

下面我们就用这些api来实现栈

class Z {
  constructor() {
    this.arr = [];
  }
  
  // 入栈
  push(item) {
    this.arr.push(item);
  }
  // 出栈
  pop() {
    return this.arr.pop();
  }
  // 获取长度
  len() {
    return this.arr.length;
  }
  // 清空栈
  isEmpty() {
    this.arr.length = 0;
  }
}
// 使用
const z = new Z();
z.push(1);
console.log(z.pop()); // 1

队列

理解了栈,队列就比较容易理解了,队列也是 存储数据 的一种方式,和栈不一样的是队列的数据结构满足先进先出格式,比如我们把苹果放在一个类似管道装置的容器存放,管道两边一边用过来存苹果,一边用来取苹果

用代码实现队列

class D {
  constructor() {
    this.arr = [];
  }
  // 入队
  push(item) {
    this.arr.push(item);
  }
    // 出队
  pop() {
    return this.arr.shift();
  }
  // 获取长度
  len() {
    return this.arr.length;
  }
  // 清空队列
  isEmpty() {
    this.arr.length = 0;
  }
}
// 使用
const d = new D();
d.push(1);
console.log(z.pop()); // 1

有什么实际用途？

很多人都有这种疑惑，学了很多理论知识，但在实际生产中又有什么用？有我写页面来的实在吗?

借助栈实现reverse(翻转数组) 栈的规则是先进后出，按照这个规则,把数据先放进去再拿出来正好把数据反了个个

// 使用
const z = new Z(); // Z类 是上面实现的 栈
const arr = [1, 2, 3, 4, 5];
const item = 0;
// 一个个入栈
arr.forEach((item) => {
  z.push(item);
});
// 在一个个出栈
let arr2 = [];
while (z.len() > 0) {
  arr2.push(z.pop());
}
console.log(arr2);  // [ 5, 4, 3, 2, 1 ]

借助队列实现发布订阅模式

我们先简单粗暴的理解下什么是发布订阅模式

首先我们要有订阅者来 订阅事件
其次我们要有个发布者来 发布事件
当发布者发布事件的时候,所有的订阅者都可以收到通知,收到通知的顺序是按照先订阅先通知原则

ok, 下面我们就用代码来实现一下把

// 基于队列实现发布订阅模式
const d = new D();  //D类 是上面实现的队列
class T {
  constructor() {}
  // 订阅者 订阅事件
  on(fn) {
    // 把事件入队列
    d.push(fn);
  }
  // 发布者 发布事件
  emit() {
    console.log("d.len", d.len());
    // 按照顺序执行队列
    while (d.len() > 0) {
      const fn = d.pop();
      fn(); // 执行
    }
  }
}
const t = new T();
t.on(() => {
  console.log(1);
});
t.on(() => {
  console.log(2);
});
t.on(() => {
  console.log(3);
});
t.emit();
// 1
// 2
// 3

总结

今天我们学习了数据结构的栈和队列,并且用强大的javascript实现了一遍,并且还学习了栈和队列的使用场景, 希望这些例子可以引起我们更多的关于数据结构的思考

最后

希望和你交个朋友 💖