JavaScript数据结构与算法

前言

面试华为、字节、网易、虾皮等一线大厂，面试官可能会围绕三块去问你：

栈和队列的区别TCP\IP和HTTP协议是什么冒泡排序和归并排序的区别

这三块其实就是：

数据结构网络算法

本文根据本人复习节奏同步更新，没写到的或写错的，请谅解或评论提醒，谢谢~

一、数据结构 栈队列（优先队列）链表（双向链表、循环链表）集合（子集、交集、并集、差集）字典（散列表）树（二叉搜索树、自平衡树、树遍历）图（深度优先、广度优先、最短路径） 1.1、栈 Stack

1.1.1、栈的概念

栈是一种后进先出（LIFO）的数据结构。

比如：羽毛球桶，先放进的羽毛球排在了最下面，以此叠加，最后进的在最上面。放羽毛球的 *** 作叫入栈，拿羽毛球的 *** 作叫出栈，最下面的叫栈底，最上面的叫栈顶。

1.1.2、栈的 *** 作

那么栈都有什么 *** 作呢：

push()         入栈pop()           出栈peek()         检查栈顶的元素isEmpty()    是否为空clear()         清空栈size()          栈元素个数

1.1.3、用JavaScript封装一个栈

var Stack = function() {
  var items = [];
  this.push = function(element) {
    items.push(element);
  };
  this.pop = function() {
    return items.pop();
  };
  this.peek = function() {
    return items[items.length - 1];
  };
  this.isEmpty = function() {
    return items.length === 0
  };
  this.clear = function() {
    items = [];
  };
  this.size = function() {
    return items.length;
  };
  this.getItem = function() {
    return items;
  };
}

1.1.4、栈的思想

利用上面的栈我们来实现一个10进制转换2进制的函数，帮助我们理解栈结构的思想：

var turnTwo = function(num) {
  var stack = new Stack();          // new一个栈
  var remainder;                    // 存放余数
  var res = "";                     // 存放结果
  while(num) {
    remainder = num % 2;            // 取余
    num = Math.floor(num / 2);
    stack.push(remainder);          // 入栈
  };
  while(!stack.isEmpty()) {
    res += stack.pop();             // 出栈后添加到结果中
  };
  return res;                       // 返回结果
}

做到这里，我们发现根本不需要那么复杂，声明一个数组直接就能实现这些 *** 作，但是数组的结构其实根本上就是一个栈，所以上述的一些实现主要是为了学会这个栈的思想，也即后进先出。

理解了这个思想，我们来接着看，栈和函数：

var fun1 = function() {
  console.log('function 1 finished!');
};
var fun2 = function() {
  fun1();
  console.log('function 2 finished!');
};
fun2();         // 先打印 function 1 finished 之后打印 function 2 finished

 在上述代码中，通过先入后出的原则来看，执行fun2()之后进入方法体执行fun1()，所以是fun2()先入栈fun1()后入栈，所以fun1()先出栈fun2()后出栈，结果就是：fun1()先打印出来，fun2()则最后。

1.2、队列 queue

1.2.1、队列的概念

队列是一种先进先出（FIFO）的数据结构。

比如：大学生排队进食堂，先进去的吃完饭先出来。进食堂的 *** 作叫enqueue()，出食堂的 *** 作叫dequeue()，查看列头的 *** 作叫front()。

1.2.2、队列的 *** 作

那么队列有哪些 *** 作呢：

enqueue() 入队dequeue() 出队front() 查看队列头isEmpty() 检查队列是否为空size() 获取队列长度

1.2.3、用JavaScript实现一个队列

var Queue = function() {
  var items = [];
  this.enqueue = function(element) {
    items.push(element);
  };
  this.dequeue = function(element) {
    return items.shift(element);
  };
  this.front = function() {
    return items[0];
  };
  this.isEmpty = function() {
    return items.length === 0;
  };
  this.size = function() {
    return items.length;  
  };
}

1.2.4、用队列的思想完成击鼓传花的需求

var p = ['a', 'b', 'c', 'd', 'e', 'f', 'g'];
var n = 3;
var chuanHua = function(person, nums) {
  const q = new Queue();
  for (let i = 0; i < person.length; i++) {
    q.enqueue(person[i]);
  };
  let numsCopy = nums;
  while(q.size() > 1) {
    if (numsCopy > 1) {
      q.enqueue(q.dequeue());
      numsCopy --;
    } else {
      q.dequeue();
      numsCopy = nums;
    }
  }
  return q.front();
}
chuanHua(p, n);     // 'd'

1.2.5、用优先队列和辅助类，实现vip登机

var PriorityQueue = function() {
  var items = [];
  // 辅助类
  var QueueItem = function(element, priority) {
    this.element = element;
    this.priority = priority;
  };
  // 入队
  this.enqueue = function(element, priority) {
    var queueItem = new QueueItem(element, priority);
    // 是否插入了？是false就是优先级低
    var added = false;
    for (var i = 0; i < items.length; i ++) {
      if (queueItem.priority > items[i].priority) {
        // 如果传入的元素的优先级，比遍历的第i个优先级高则插入元素
        items.splice(i, 0, queueItem);
        added = true;
        break;
      }
    }
    if (!added) {
      items.push(queueItem);
    }
  };
  this.dequeue = function() {
    return items.shift();
  };
};
var test = new PriorityQueue();
test.enqueue('Stefan', 24);
test.enqueue('Edward', 40);    // 最后Edward排在Stefan前面

1.3、链表 Linkedlist

1.3.1、什么是链表？

链表是环环相扣的数据结构，链表的每一节点node都带有自己的元素item和下一节点node的位置next，链表头为head，所以当node.next == null的时候也即这一项node是链表尾。

比如：火车，它的每一节车厢除了箱内货品之外，还连接了下一节车厢。如果你想从A车厢找C车厢的朋友，需要一个个车厢的找下去，链表也一样。

1.3.2、链表的 *** 作

链表是一种局限性很高的数据结构，它的 *** 作只有next，比如一条 1 => 2 => 3 => 4的链表，当我们走到3的时候，是无法得知1的，链表中也没有下标的概念，只有head链表头的概念，比如我们的head是1，那么我们想知道4，就要head.next.next.next。

1.3.3、dummy

在写算法题的时候，dummy的设置异常重要，接下来我们用一道算法题来体验dummy的巧妙性。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function (list1, list2) {
    let curr = new ListNode();
    let dummy = curr;
    while (list1 !== null && list2 !== null) {
        if (list1.val < list2.val) {
            curr.next = list1;
            list1 = list1.next;
        } else {
            curr.next = list2;
            list2 = list2.next;   
        };
        curr = curr.next;
    };
    if (list1 !== null) {
        curr.next = list1;
    };
    if (list2 !== null) {
        curr.next = list2;
    };
    return dummy.next;
};

二、网络 2.1、WWW （World Wide Web）万维网

Internet提供了很多服务，比如www网页服务、FTP文件传输、E-mail电子邮件、Telnet远程登陆等等。随着网站服务类型的增加，不同的二级域名和三级域名对应不同的业务，而业务的处理任务会分配到多个服务器，所以，不再需要使用www来标注主页，很多网站都还会做DNS解析www，原因是尊重用户习惯。

2.2、DNS （Domain Name Server）域名服务器

作用：它的作用是将域名转换为对应的IP地址。

特征：DNS中保存了一张域名和对应IP地址的表，一个域名对应一个IP，一个IP地址可以对应多个域名。

DNS的工作过程：

当客户端输入了url敲击了回车之后，DNS本地服务器查看缓存里有没有这个url域名；如果缓存中有这个域名的对应IP，则返回IP地址。如果没有，DNS则会先询问根服务器，根服务器中一般会让DNS去找 .com服务器；.com域服务器会让DNS直接去找服务商下对应的域服务器；DNS询问服务商对应的域服务器，拿到对应的IP地址之后，先写入DNS本地缓存，再返回给客户端。

2.3、IP （Internet Protocol Address）IP地址

作用：分配给用户上网使用的互联网协议服务。

分类：IPv4 、 IPv6 、 其他。

形式：比如192.168.0.1，长度是32位，4个字节，用十进制表示。

IPv6对比IPv4的优势：

IPv6地址空间更大，有8组128位，用十六进制来表示；路由表更小；组播支持以及对流支持增强；对自动配置的支持；更高的安全性等等。 2.4、Port 端口号

解释：IP地址假使是上海市浦东新区，域名则是迪士尼乐园，Port端口号则是海盗船的入口。

范围：0 ~ 65535（在HTTP协议下默认的端口号是80，HTTPS是443，FTP协议下是20或21）。

总结：每一个端口对应的是一个服务器的一个业务，访问一个服务器的不同端口相当于访问一个服务器的不同业务。

2.5、TCP (Transmission Control Protocol) 传输控制

特点：面向连接（收发数据前，必须建立可靠的连接），也就是说不管是收数据的一方还是发数据的一方，必须都是可靠的安全的。

建立连接的方式：三次握手。

应用场景：数据必须准确无误的收发，比如：HTTP请求、FTP文件传输、邮件收发等等。

优点：稳定、重传机制、拥塞控制机制、断开连接。

缺点：速度慢、效率低、占用资源、容易被攻击（比如：三次握手时候进行DOS、DDOS攻击）。

TCP/IP协议组：提供点对点的连接机制，制定了数据封装、定址、传输、路由、数据接收的标准。

TCP连接建立的前奏：

①标志位（数据包）：

SYN：Synchronize Sequence Number 同步序列编号；ACK：Acknowledgement 确认字符。

②状态：

LISTEN：监听TCP端口的连接请求；SYN-SENT：在发送连接请求后等待匹配的连接请求；SYN-RECEIVED：在收到和发送一个连接请求后等待对连接请求的确认；ESTABLISHED：代表一个打开的连接，数据可以传送给用户。

断开连接的方式：四次挥手。

为什么握手要三次，但是挥手要四次？这里重要的点在第二次挥手的时候，Client第一次发送FIN请求报文的之后，Server端并没有立刻进入关闭状态，而是可以将没有发送完的报文接着输送给Client端，这时Client端进入FIN_WAIT状态，Server端进入CLOSE_WAIT状态，Server端在报文全部输送完毕之后才会将FIN报文发送给客户端，告诉客户端已经可以关闭了，这时Client端接收到这个FIN报文之后，将ACK确认报文传给Server端，并进入TIME_WAIT计时等待状态，如果Server端没有回复，则关闭连接，这样就走完了TCP的四次挥手。

2.6、UDP (User Data Protocol) 用户数据报协议

特点：面向无连接 （不可靠的协议，无状态传输机制），无连接信息发送机制。

应用场景：无需确保通讯质量且要求速度快、无需确保信息完整性的场景，比如：qq聊天、语音通话、游戏等。

优点：安全、快速、漏洞少（UDP flood攻击）。

缺点：不可靠、不稳定、容易丢包。

总结：只要目的源地址、端口号确定，则可以直接发送信息报文，但不能保证一定能收到或收到完整的数据。

2.7、HTTP (Hyper Text Transfer Protocol) & HTTPS (Hyper Text Transfer Protocol Secure)

HTTP：HTTP是超文本传输协议，客户端和服务器端请求和应答的标准，用于从web服务器传输文本到本地浏览器的传输协议。

HTTPS：HTTPS则是按照HTTP协议规则，向web服务器发送的将超文本传输到本地浏览器的请求。HTTPS在HTTP的基础上增加了安全性（安全基础是SSL/TLS）：SSL (Secure Sockets Layer) 安全套接层，TLS (Transport Layer Security) 传输层安全，为网络通信提供安全及数据完整性的一种安全协议，对网络连接提供加密。

区别：

HTTP不安全（监听和中间人攻击等手段，获取账户信息和敏感信息），而HTTPS可以防止被攻击。HTTP协议的传输内容是明文，直接在TCP连接上运行，客户端和服务器都无法验证对方身份，只能通过标志位来判断身份，但是这个身份是可以被篡改的。而HTTPS协议的传输内容都被SSL/TLS加密处理，且运行在SSL/TLS上，SSL/TLC运行在TCP之上，所以数据传输是安全的。