如果你是科班生上大学时候光想着回寝室玩游戏，又或者是非科班去了培训班学习编程，你使用JS、JQuery、Vue、React得心应手比大部分人写的都要好，你肯定可以在社会上找到一个不错的工作，但是如果面试华为、字节、网易、虾皮等一线大厂，这些技术类的框架反而不是第一考点，一个面试官可能会围绕三块去问你：
- 栈和队列的区别
- TCPIP和HTTP协议是什么
- 冒泡排序和归并排序的区别
这三块其实就是：
- 数据结构
- 网络
- 算法
这三块内容，可能不耽误日常的开发，但是却决定了我们程序员的上限。
2022年我已经进行了2年的前端开发工作，打开Leetcode却磨蹭半天写不出一题，于是我下定决心复习基础学习算法，同时通过这篇文章记录下来，如果你看到了这篇文章，你跟我的情况一样，那么就也开始你的复习或学习吧。
本文根据本人复习节奏同步更新，没写到的或写错的，请谅解或评论提醒，谢谢~
一、数据结构- 栈
- 队列（优先队列）
- 链表（双向链表、循环链表）
- 集合（子集、交集、并集、差集）
- 字典（散列表）
- 树（二叉搜索树、自平衡树、树遍历）
- 图（深度优先、广度优先、最短路径）
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、队列 queue1.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前面
二、网络
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本地缓存，再返回给客户端。
作用：分配给用户上网使用的互联网协议服务。
分类：IPv4 、 IPv6 、 其他。
形式：比如192.168.0.1，长度是32位，4个字节，用十进制表示。
IPv6对比IPv4的优势：
- IPv6地址空间更大，有8组128位，用十六进制来表示；
- 路由表更小；
- 组播支持以及对流支持增强；
- 对自动配置的支持；
- 更高的安全性等等。
解释：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：代表一个打开的连接，数据可以传送给用户。
特点：面向无连接 （不可靠的协议，无状态传输机制），无连接信息发送机制。
应用场景：无需确保通讯质量且要求速度快、无需确保信息完整性的场景，比如：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之上，所以数据传输是安全的。
