学习JavaScript数据结构

作者: 欢西西西 | 来源:发表于2021-12-10 09:07 被阅读0次

一、数组Array

典型应用之斐波那契数列：前2个项都为1，从第三项开始，每一项都等于前2项之和，求斐波那契数列的前20项。

第一反应是，用2个变量记录前两项，每次循环时更新这两个变量并打印出来：

以上做法的问题是这2个变量仅作为临时计算实用，结果的20个数并没能保存下来

用数组的方式：目的是要把这20个数利用数组arr保存下来，并去掉numPrev1 和 numPrev2这两个临时的变量，利用数组下标取值的方式计算出每一项：

数组的便利之处就在于【能只用一个变量存多个数据，不用创建很多变量来存每一项】，【利用数组下标能很方便地取各个位置上的值】，对保存和处理那些【在顺序上有规律的数据】来说非常实用。

二、栈Stack

后进先出，操作方向仅在栈顶

栈是一个遵循后进先出原则（LIFO）的有序集合，我们可以在数组的 任意位置 上操作元素，但栈限制了操作位置：只能在栈顶 进行存取操作。栈被用来在编程语言中保存变量、方法的调用顺序；保存访问过的路径，比如浏览器保存历史记录以回退到上一路径等。

1.创建一个基于数组的栈

2.创建一个基于对象的栈

将key为0的作为栈底，key越大越靠近栈顶

3.使用WeakMap保护私有属性

使用以上两种方法时，Stack的实例仍能访问并修改_items属性，用下划线命名只是一种约定，依赖于开发者的常识，我们希望能保护内部的元素，将_items作为私有属性，限制实例对它的访问：

WeakMap 的设计目的在于，有时我们想在某个对象上面存放一些数据，但是这会形成对于这个对象的引用，只要引用存在，垃圾回收 机制就不会释放对象占用的内存。 WeakMap 就是为了解决这个问题而诞生的，它的键名所引用的对象都是弱引用 ，只要所引用的对象的 其他引用 都被清除，垃圾回收机制就会释放该对象所占用的内存。也就是说，一旦不再需要，WeakMap 里面的键名对象和所对应的键值对会自动消失，不用手动删除引用

4.利用栈实现进制转换

将10进制转换为2~36的任意进制，例如转换为二进制，将十进制的数除以2，每次将余数压入栈中，用商继续除以2，直到商为0.

5.校验圆括号是否平衡

三、队列（Queue）与双端队列（Deque:double-ended queue）

1.队列

先进先出

队列是遵循先进先出（FIFO，也成为先来先服务）原则的一组有序的项。它与栈非常类似，但栈 只在栈顶 进行存取，而队列是只能在 队尾存，队首取 ：最新添加的元素必须排在末尾，最早被添加的元素最先得到服务。

常见的例子就是打印队列，先来先打印，后来先排队

经典问题之击鼓传花

围圈传递花，音乐停花在谁手里则谁淘汰，游戏里小朋友位置不变，传递花，用队列模拟就是相当于队列首部放一束花不懂，为危险位置，队列首部的小朋友不断跑到队列尾，音乐停谁在队首谁淘汰。

循环队列

2.双端队列

双端队列，允许我们同时从 两端进行存取。

常见的例子是用双端队列存储最近的几次操作，最早的操作排在最前面，当需要撤销时从队尾弹出最近的一次操作，就像栈一样，后进的先出；当存储的操作数达到设定时，有最新操作进来就需要移除最早的操作，这个时候要从最前面移除，这时候就像队列一样，先进的先出，所以双端队列就像栈和队列相结合的一种数据结构。

双端队列是两端都可以存取，不过这个例子是在两端取，仅需要在一端存

判断字符串是否是回文（正读和反读相同）

用栈的思路是先反转再对比原字符串

用双端队列的思路是同时从两端取一个字符，对比是否相同

四、链表LinkedList

1. 链表LinkedList

链表能够确定一组（不是保存一组，链表本身只存第一个元素head的引用）有序的元素集合。不同于数组的是，链表中的元素在内存中并不是连续放置的，每个节点都存储元素本身和指向下一个节点的指针，元素顺序就是靠这些指向下一节点的指针来确定的。

实际这些节点并不是这样顺序排列的

在数组中插入或删除元素的成本很高，因为需要移动元素；

链表的好处就是添加或删除时不需要移动元素，只需要改变指针指向；

当然，链表的缺点是额外保存了指针，而且因为元素在内存中不是连续放置的，在访问链表中间的元素时，只能从前往后迭代，无法像数组一样能直接通过位置找到元素；

当你需要添加和移除很多元素时，应该首选链表而非数组。

删除元素

2.双向链表

每个节点除了存储下个节点的指针外，还要存储上一个节点的指针

双向链表由于同时保存了前后两个节点的引用，可以进行前序和后序遍历，普通链表只能从前往后。由于可以进行双向遍历，当确定了要操作的元素位置时，可以根据位置的前后来决定遍历的方向，以减少迭代次数。

但是每个节点都要多分配一个指针存储前一个结点引用，增删时也需要维护前驱节点的指向。

3.循环链表

与链表的不同点在于，链表的最后一个元素的next不再指向undefined而是指向head节点；双向链表的head节点的prev指向最后一个节点。

循环链表的优点在于，从任意一个位置出发，都能遍历整个链表；普通链表则只能从指定位置遍历到尾部，或首部（如果是双向链表的话）。

循环链表中没有NULL指针，在遍历时也可以减少判断null的这个操作

五、集合Set

集合由一组无序且不相同的项组成。例如：N = {'A', 10, '哈', 4};

集合内的项无序且唯一

我们可以使用对象来模拟集合。将项作为对象的key以保证唯一性，增加项时则增加属性，删除项则删除该属性。

在进行集合运算时，可以用扩展运算符将集合转化为数组来操作：

1.并集：new Set([...setA,...setB])

2.交集：new Set([...setA].filter(i=>setB.has(i)))

3.差集：new Set([...setA].filter(i=>!setB.has(i)))

六、字典Map和散列表HashMap(page 145)

集合是以[值，值]的形式存储元素，字典以[键，值]的形式来存储元素。字典也称作映射、符号、关联数组。

在字典中，我们将key转化为字符串后，将value存在该字符串属性中。

在散列表(哈希表)中，我们【将key转化为字符串再使用每个字符的ASCII值转成一个数字】，将value存在该数字位置。这个转换函数是散列(hash)函数，散列函数的作用，就是给定一个键值，返回值在表中的位置。

1.处理散列表中的冲突

当不同的key有相同的散列值时，会有冲突，因为不同的值将对应同一个位置。

方法1：分离链接：为散列表的每一个位置创建一个链表，这样一个位置上相当于能存多个值了，不过存的时候需要既存值也存键，因为取的时候需要使用键来匹配链表中的值。

方法2：线性探查：当添加元素时发现位置被占了，就从此位置向后迭代，以找一个空闲的位置并插入。在查找值时，如果要查找的位置上有值，并且所存的key与要查找的key相同，则返回，否则向后查找哈希值为当前位置的元素并匹配key。当要删除某个值时，除了删除那个位置上的值以外，还要将其他冲突的元素移动至之前的位置，不产生空位置。