JavaScript数据结构与算法

一、前言

1.1.什么是数据结构？

数据结构就是在计算机中，存储和组织数据的方式。常见的数据结构：

• 数组（Aarray）

• 栈（Stack）

• 链表（Linked List）

• 图（Graph）

• 散列表（Hash）

• 队列（Queue）

• 树（Tree）

• 堆（Heap）

1.2.什么是算法？

算法（Algorithm）的定义

• 一个有限指令集，每条指令的描述不依赖于语言；

• 接收一些输入（有些情况下不需要输入）；

• 产生输出；

• 一定在有限步骤之后终止；

算法通俗理解：解决问题的办法/步骤逻辑。数据结构的实现，离不开算法。

二、栈结构（Stack）

2.1.简介

数组是一个线性结构，并且可以在数组的任意位置插入和删除元素。而栈和队列就是比较常见的受限的线性结构。

栈的特点为先进后出，后进先出（LIFO：last in first out）。

程序中的栈结构：

• 函数调用栈：A（B（C（D（））））：即A函数中调用B，B调用C，C调用D；在A执行的过程中会将A压入栈，随后B执行时B也被压入栈，函数C和D执行时也会被压入栈。所以当前栈的顺序为：A->B->C->D（栈顶）；函数D执行完之后，会弹出栈被释放，弹出栈的顺序为D->C->B->A（函数调用栈）;

• 递归：为什么没有停止条件的递归会造成栈溢出？比如函数A为递归函数，不断地调用自己（因为函数还没有执行完，不会把（自己）函数弹出栈），不停地把相同的函数A压入栈，最后造成栈溢出（Stack Overfloat）

栈结构的实现

• 基于数组实现

• 基于链表实现

什么是链表？

一种数据结构，javascript中并没有自带链表

• 先实现栈结构基于数组

对数组进行一层包装，使其具有栈的特性

栈的操作

• push（element）//将元素压入栈

• pop //从栈中取出元素，并返回值

• peek//返回栈顶元素

• isEmpty//判断栈是否为空，为空返回true不为空false

• size//返回栈的长度

• toString//toString方法

应用—-十进制转成二进制

只需要将给十进制数字和2整除。直到结果是0为止

将10转换成二进制

先将0压入栈，以此类推，最后入栈的数为1，后依次出栈

思路：将数除2获取余数依次存入栈内，整除2后的结果，作为下一次运行的结果继续循环，直到结果0为止；出栈

• while循环

• Math.floor()

三、认识队列

是一种受限的线性结构，只允许在前端删除元素，在后端插入元素，符合先进先出（FIFO first in first out）

队列应用

打印队列

打印文档，按输入顺序

线程队列

在开发中，为了让任务并行处理，通常开启多个线程，但不能让大量线程同时运行处理任务（占用过多资源），因此使用线程队列。其会依照次序来启动线程，并且处理对应的任务。

封装队列常见操作

• 后端添加 enter-queue——enqueue

• 前端删除 delete-queue—–dequeue

• 返回前端元素，对队列不做修改front

• 判断为空isEmpty

• 长度size

• toString

击鼓传花

• 击鼓传花是一个常见的面试算法题.使用队列可以非常方便的实现最终的结果.

• 原游戏规则:

  • 班级中玩一个游戏,所有学生围成一圈,从某位同学手里开始向旁边的同学传一束花.

  • 这个时候某个人(比如班长)，在击鼓,鼓声停下的一颗,花落在谁手里，谁就出来表演节目.

• 修改游戏规则.

  • 几个朋友一起玩一个游戏,围成一圈,开始数数,数到某个数字的人自动淘汰.

  • 最后剩下的这个人会获得胜利,请问最后剩下的是原来在哪一个位置上的人?

     

  • 参数:所有参与人的姓名,基于的数字

  • 结果:最终剩下的一人的姓名

思路：假设5为爆炸数字，将5个人依次放入队列中，第一个人数到1后继续添加到队列的后端，第二个人数到2后继续添加到队列的后端，以此类推，到第五个人数5后淘汰，此时剩余4个人，循环到第四个人数4，后面跟着的1号人数5，1号淘汰，3号淘汰，4号淘汰，后2号胜利

步骤：

1. 创建一个队列结构

2. 将所有人依次加入到队列中

3. 循环将没有喊到num的人依次添加到队列后端，喊到num的人淘汰

4. 当队列剩余1个人时输出其name和下标

优先级队列

• 在插入一个元素的时候会考虑该数据的优先级，和其他数据优先级进行比较，比较完成后，可以得出这个元素在队列中正确的位置

• 每个元素不再只是一个数据，而是包含数据的优先级，在添加方式中，根据优先级放入正确的位置

应用

1. 登机顺序，头等舱与商务舱的登机顺序，头等舱的优先级高于商务舱的优先级。

2. 急诊科

3. 计算机中，每个线程的任务重要性不同

四、链表

• 链表中的元素在内存中不必是连续的空间，实现灵活的内存动态管理

• 链表的每个元素由一个存储元素本身的节点和指向下一个元素的引用组成

• 链表不必在创建时就确定大小，并且大小可以无限的延伸下去

• 链表在插入和删除数据时，时间复杂度可以达到O(1)，比数组效率高很多

缺点：

• 链表在访问任何一个元素时，都需要从头开始

• 无法通过下标直接访问元素，需要从头一个个访问，直到找到对应的元素