Wang Wei's Blog

《学习JavaScript数据结构与算法(第3版)》

堆数据结构，也叫二叉堆，是一种特殊的二叉树。由于堆能够高效、快速地找出最大值和最小值，常被应用于优先队列。

二叉堆数据结构

二叉堆是一种特殊地二叉树，有以下两个特性：

1. 它是一棵完全二叉树，表示树的每一层都有左侧和右侧子节点（除了最后一层的叶节点），并且最后一层的叶节点尽可能都是左侧子节点，这叫作结构特性。
2. 二叉堆不是最小堆就是最大堆。最小堆允许你快速导出树的最小值，最大堆允许你快速导出树的最大值。所有的节点都大于等于（最大堆）或小于等于（最小堆）每个它的子节点。这叫作堆特性。

《学习JavaScript数据结构与算法(第3版)》

树是一种分层数据的抽象模型。

一个树结构包含一系列存在父子关系的节点。每个节点都有一个父节点（除了顶部的第一个节点）以及零个或多个子节点：

树的每个元素都叫做节点，节点分为内部节点（有子节点的节点）和外部节点（叶节点，无子节点的节点）。

《学习JavaScript数据结构与算法(第3版)》

递归通常涉及函数调用自身。间接调用自身的函数也是递归函数。

每个递归函数都必须有基线条件，即一个不再递归调用的条件（停止点），以防止无限递归，出现栈溢出错误。

function recursiveFunction(someParam) {
    recursiveFunction(someParam);
}

计算一个数的阶乘

《学习JavaScript数据结构与算法(第3版)》

在字典（或映射）中，我们用[键，值]对的形式来存储数据。在散列表中也是一样（也是以[键，值]对的形式来存储数据）。

字典数据结构

在字典中，存储的是[键，值]对，其中键名是用来查询特定元素的。字典和集合很相似，集合以[值，值]的形式存储元素，字典则是以[键，值]的形式来存储元素。字典也称作映射、符号表或关联数组。

字典经常用来保存对象的引用地址。

《学习JavaScript数据结构与算法(第3版)》

队列是遵循先进先出（FIFO，也称为先来先服务）原则的一组有序的项。队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾。

队列数据结构

export default class Queue {
    constructor() {
        this.count = 0; // 用来控制队列的大小
        this.lowestCount = 0; // 队列的第一个元素
        this.items = {}; // 使用对象存储元素
    }

    // 向队列尾部添加一个新的项
    enqueue(element) {
        // 将新元素加到队列中
        this.items[this.count] = element;
        this.count++;
    }

    // 移除队列的第一项（即排在队列最前面的项）并返回被移除的元素
    dequeue() {
        if (this.isEmpty()) {
            return undefined;
        }
        const result = this.items[this.lowestCount];
        // 删除第一项元素
        delete this.items[this.lowestCount];
        this.lowestCount++; // 队头元素往后移
        return result;
    }

    // 返回队列钟第一个元素，最先被添加，也将是最先被移除的元素。队列不做任何变动（不移除元素，值返回元素信息）
    peek() {
        if (this.isEmpty()) {
            return undefined;
        }
        return this.items[this.lowestCount];
    }

    // 队列是否为空
    isEmpty() {
        return this.size() === 0;
    }

    // 清除队列
    clear() {
        this.items = {};
        this.count = 0;
        this.lowestCount = 0;
    }

    // 返回队列包含的元素个数
    size() {
        return this.count - this.lowestCount;
    }

    // 队列输出
    toString() {
        if (this.isEmpty()) {
            return '';
        }
        let objString = `${this.items[this.lowestCount]}`;
        for (let i = this.lowestCount + 1; i < this.count; i++) {
            objString = `${objString},${this.items[i]}`;
        }
        return objString;
    }
}

双端队列

即Web浏览器与Web服务器之间全双工通信标准

是一种自然的全双工、双向、单套接字(Socket)连接

主要是为了解决 Ajax 和 Comet 里 XMLHttpRequest 附带的缺陷。

WebSocket 是异步的，可以用作高级协议的传输层。

WebSocket 是消息协议、聊天、服务器通知、管道和多路复用协议、自定义协议、紧凑二进制协议和用于与互联网服务器互操作的其他标准协议的很好基础。

Cookie、Session、Token、JWT

引入这些技术主要是为了保持状态。HTTP协议是无状态协议。

Cookie

cookie存储在客户端

cookie 是服务器发送到用户浏览器并保存在本地的一小块数据，它会在浏览器下次向同一服务器再发起请求时被携带并发送到服务器上。浏览器可储存cookie总大小为4095~4097个字节（不同浏览器不同）。

HTTP协议

请求访问文本或图像等资源的一端称为客户端，而提供资源响应的一端称为服务器端。

超文本传输协议。协议时之规则的约定。

HTTP协议出现主要是为了解决文本传输难题。

HTTP协议用于客户端和服务器端之间的通信。Web是建立在HTTP协议上通信的。

UDP

TCP

从根本上讲，HTTP还是半双工的协议，也就是说，在同一时刻流量只能单向流动：客户端向服务器发送请求（单向），然后服务器响应请求（单向）。半双工的效率很低。

所谓套接字( Socket )，就是对网络中不同主机上的应用进程之间进行双向通信的端点的抽象。一个套接字就是网络上进程通信的一端，提供了应用层进程利用网络协议交换数据的机制。从所处的地位来讲，套接字上联应用进程，下联网络协议栈，是应用程序通过网络协议进行通信的接口，是应用程序与网络协议根进行交互的接口

随机数：Math.random() 函数返回一个浮点数, 伪随机数在范围[0, 1)

指定长度随机字符串

const chars = [ '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
  				'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 
               	'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T',
  				'U', 'V', 'W', 'X', 'Y', 'Z' ]
function generateMixed(n) {
  let res = ''
  for (let i = 0; i < n; i++) {
    res += chars[Math.ceil(Math.random() * 35)]
  }
  return res
}

(min, max)

function random(lower, upper) {
	return Math.ceil(Math.random() * (upper - lower)) + lower + 1;
}