数据结构和算法基础(前端方向)
复杂度
渐进复杂度，包括时间复杂度和空间复杂度，用来分析算法执行效率与数据规模之间的增长关系，可以粗略地表示，越高阶复杂度的算法，执行效率越低
从低阶到高阶有：O(1)、O(logn)、O(n)、O(nlogn)、O(n2 )
数组
说到数组大家想必在开发中，是接触最多的一类数量类型，也是最常见的一类线性表。
线性表的分类
静态类型语言（java,c++）
一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
动态类型语言(javaScript)
As JavaScript arrays are implemented as hash-maps（哈希表） or dictionaries(字典) and not contiguous.（非连续）
链表
它并不需要一块连续的内存空间，它通过指针将一组零散的内存块串联起来使用
内存分配
链表通过指针将一组零散的内存块串联在一起。其中，我们把内存块称为链表的结点
单链表
其中有两个结点是比较特殊的，它们分别是第一个结点和最后一个结点。我们习惯性地把第一个结点叫作头结点，把最后一个结点叫作尾结点。其中，头结点用来记录链表的基地址。有了它，我们就可以遍历得到整条链表。而尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址 NULL，表示这是链表上最后一个结点。
循环链表
循环链表的尾结点指针是指向链表的头结点
双向链表
双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以，如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。
链表 VS 数组性能大比拼
数组中随机访问，指的是按下标的随机访问
js实现一个链表(满足CRUD)
大致的结构如下：
size和head为LinkedList构造函数私有属性，size记录链表中有多少个节点，head指向链表的头结点
单向链表的代码实现
/**
* 自定义链表：对外公开的方法有
* append(element) 在链表最后追加节点
* insert(index, element) 根据索引index, 在索引位置插入节点
* remove(element) 删除节点
* removeAt(index) 删除指定索引节点
* removeAll(element) 删除所有匹配的节点
* set(index, element) 根据索引，修改对应索引的节点值
* get(index) 根据索引获取节点信息
* indexOf(element) 获取某个节点的索引位置
* clear() 清空所有节点
* length() 返回节点长度
* print() 打印所有节点信息
* toString() 打印所有节点信息，同print
* */
const LinkedList = function(){
let head = null;
let size = 0; //记录链表元素个数
//Node模型
function LinkNode(element, next){
this.element = element;
this.next = next;
}
//元素越界检查, 越界抛出异常
function outOfBounds(index){
if (index < 0 || index >= size){
throw("抱歉，目标位置不存在！");
}
}
//根据索引，获取目标对象
function node(index){
outOfBounds(index);
let obj = head;
for (let i = 0; i < index; i++){
obj = obj.next;
}
return obj;
}
//新增一个元素
function append(element){
if (size == 0){
head = new LinkNode(element, null);
}
else{
let obj = node(size-1);
obj.next = new LinkNode(element, null);
}
size++;
}
//插入一个元素
function insert(index, element){
if (index == 0){
head = new LinkNode(element, head);
}
else{
let obj = node(index-1);
obj.next = new LinkNode(element, obj.next);
}
size++;
}
//修改元素
function set(index, element){
let obj = node(index);
obj.element = element;
}
//根据值移除节点元素
function remove(element){
if (size < 1) return null;
if (head.element == element){
head = head.next;
size--;
return element;
}
else{
let temp = head;
while(temp.next){
if (temp.next.element == element){
temp.next = temp.next.next;
size--;
return element;
}
else{
temp = temp.next;
}
}
}
return null;
}
//根据索引移除节点
function removeAt(index){
outOfBounds(index);
let element = null;
if (index == 0){
element = head.element;
head = head.next;
}
else{
let prev = node(index-1);
element = prev.next.element;
prev.next = prev.next.next;
}
size--;
return element;
}
//移除链表里面的所有匹配值element的元素
function removeAll(element){
let virHead = new LinkNode(null, head); //创建一个虚拟头结点，head为次节点
let tempNode = virHead, ele = null;
while(tempNode.next){
if (tempNode.next.element == element){
tempNode.next = tempNode.next.next;
size--;
ele = element;
}
else{
tempNode = tempNode.next;
}
}
//重新赋值
head = virHead.next;
return ele;
}
//获取某个元素
function get(index){
return node(index).element;
}
//获取元素索引
function indexOf(element){
let obj = head, index = -1;
for (let i = 0; i < size; i++){
if (obj.element == element){
index = i;
break;
}
obj = obj.next;
}
return index;
}
//清除所有元素
function clear(){
head = null;
size = 0;
}
//属性转字符串
function getObjString(obj){
let str = "";
if (obj instanceof Array){
str += "[";
for (let i = 0; i < obj.length; i++){
str += getObjString(obj[i]);
}
str = str.substring(0, str.length - 2);
str += "], "
}
else if (obj instanceof Object){
str += "{";
for (var key in obj){
let item = obj[key];
str += "\"" + key + "\": " + getObjString(item);
}
str = str.substring(0, str.length-2);
str += "}, "
}
else if (typeof obj == "string"){
str += "\"" + obj + "\"" + ", ";
}
else{
str += obj + ", ";
}
return str;
}
function toString(){
let str = "", obj = head;
for (let i = 0; i < size; i++){
str += getObjString(obj.element);
obj = obj.next;
}
if (str.length > 0) str = str.substring(0, str.length -2);
return str;
}
//打印所有元素
function print(){
console.log(this.toString())
}
//对外公开方法
this.append = append;
this.insert = insert;
this.remove = remove;
this.removeAt = removeAt;
this.removeAll = removeAll;
this.set = set;
this.get = get;
this.indexOf = indexOf;
this.length = function(){
return size;
}
this.clear = clear;
this.print = print;
this.toString = toString;
}
////测试
// let obj = new LinkedList();
// let obj1 = { title: "全明星比赛", stores: [{name: "张飞vs岳飞", store: "2:3"}, { name: "关羽vs秦琼", store: "5:5"}]};
//
// obj.append(99);
// obj.append("hello")
// obj.append(true)
// obj.insert(3, obj1);
// obj.insert(0, [12, false, "Good", 81]);
// obj.print();
// console.log("obj1.index: ", obj.indexOf(obj1));
// obj.remove(0);
// obj.removeAll(obj1);
// obj.print();
////测试2
console.log("\n\n......test2.....")
var obj2 = new LinkedList();
obj2.append(8); obj2.insert(1,99); obj2.append('abc'); obj2.append(8); obj2.append(false);
obj2.append(12); obj2.append(8); obj2.append('123'); obj2.append(8);
obj2.print();
obj2.removeAll(8); //删除所有8
obj2.print();
复制代码链表的简单算法(反转单向链表)
/**
*
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
let prev = null;
let curr = head;//定义"哨兵"
while (curr != null) {
let nextTemp = curr.next;//暂存剩余链表
curr.next = prev;//与剩余链表断开连接，并将指向变更
prev = curr;//两个节点交互位置
curr = nextTemp;//指针下移
}
return prev;
};
复制代码栈
关于栈，有一个非常贴切的例子，就是一摞叠在一起的盘子。我们平时放盘子的时候，都是从下往上一个一个放；取的时候，我们也是从上往下一个一个地依次取，不能从中间任意抽出。后进者先出，先进者后出，这就是典型的“栈”结构。
从栈的操作特性上来看
栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。
实际上，栈既可以用数组来实现，也可以用链表来实现。用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。（这也仅仅针对的是C,C++,JAVA等静态类型语言）
函数调用栈
操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构, 用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。
function main() {
let a = 1;
let ret = 0;
let res = 0;
ret = add(3, 5);
res = a + ret;
console.log(`处理结果为 ${res}`);
reuturn 0;
}
function add( x, y) {
let sum = 0;
sum = x + y;
return sum;
}
复制代码图中显示的是，在执行到 add() 函数时，函数调用栈的情况。
栈在表达式求值中的应用
实际上，编译器就是通过两个栈来实现的。其中一个保存操作数的栈，另一个是保存运算符的栈。我们从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较。
将 3+5*8-6 这个表达式的计算过程画成了一张图,如下：
实现浏览器的前进、后退功能
使用两个栈，X 和 Y，我们把首次浏览的页面依次压入栈 X，当点击后退按钮时，再依次从栈 X 中出栈，并将出栈的数据依次放入栈 Y。当我们点击前进按钮时，我们依次从栈 Y 中取出数据，放入栈 X 中。当栈 X 中没有数据时，那就说明没有页面可以继续后退浏览了。当栈 Y 中没有数据，那就说明没有页面可以点击前进按钮浏览了。
入栈操作
- 比如顺序查看了 a，b，c 三个页面，依次把 a，b，c 压入栈，这个时候，两个栈的数据就是这个样子：
2.当你通过浏览器的后退按钮，从页面 c 后退到页面 a 之后，依次把 c 和 b 从栈 X 中弹出，并且依次放入到栈 Y。这个时候，两个栈的数据就是这个样子：
如此反复如上操作，就可以简单解释浏览器回退和前进的操作步骤。
内存中的堆栈vs数据结构堆栈
内存中的堆栈和数据结构堆栈不是一个概念，可以说内存中的堆栈是真实存在的物理区，数据结构中的堆栈是抽象的数据存储结构。
内存空间
内存空间在逻辑上分为三部分：代码区、静态数据区和动态数据区，动态数据区又分为栈区和堆区。
- 代码区：存储方法体的二进制代码。高级调度（作业调度）、中级调度（内存调度）、低级调度（进程调度）控制代码区执行代码的切换。
- 静态数据区：存储全局变量、静态变量、常量，常量包括final修饰的常量和String常量。系统自动分配和回收。
- 栈区：存储运行方法的形参、局部变量、返回值。由系统自动分配和回收。
- 堆区：new一个对象的引用或地址存储在栈区，指向该对象存储在堆区中的真实数据。
队列
队列跟栈一样，也是一种操作受限的线性表数据结构。
顺序队列和链式队列
队列跟栈一样，也是一种抽象的数据结构。它具有先进先出的特性，支持在队尾插入元素，在队头删除元素。
队列可以用数组来实现，也可以用链表来实现。用数组实现的栈叫作顺序栈，用链表实现的栈叫作链式栈。同样，用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。
代码实现一个顺序队列
// 用数组实现的队列
const ArrayQueue=function(){
// 数组：items，数组大小：n
let items =[];
let n = 0;
// head 表示队头下标，tail 表示队尾下标
let head = 0;
let tail = 0;
// 申请一个大小为 capacity 的数组
function createArrayQueue(capacity) {
items = new Array(capacity);
n = capacity;
}
// 入队操作，将 item 放入队尾
function enqueue(item) {
// tail == n 表示队列末尾没有空间了
if (tail == n) {
// tail ==n && head==0，表示整个队列都占满了
if (head == 0) return false;
// 数据搬移
for (int i = head; i < tail; ++i) {
items[i-head] = items[i];
}
// 搬移完之后重新更新 head 和 tail
tail -= head;
head = 0;
}
items[tail] = item;
++tail;
return true;
}
// 出队
function dequeue() {
// 如果 head == tail 表示队列为空
if (head == tail) return null;
// 为了让其他语言的同学看的更加明确，把 -- 操作放到单独一行来写了
let ret = items[head];
++head;
return ret;
}
this.createArrayQueue = createArrayQueue;
this.enqueue = enqueue;
this.dequeue = dequeue;
}
复制代码循环队列
用数组实现的队列，在 tail==n 时，会有数据搬移操作，这样入队操作性能就会受到影响。
想要避免数据搬移，可以用循环队列来处理。
我们可以看到，图中这个队列的大小为 8，当前 head=4，tail=7。当有一个新的元素 a 入队时，我们放入下标为 7 的位置。但这个时候，我们并不把 tail 更新为 8，而是将其在环中后移一位，到下标为 0 的位置。当再有一个元素 b 入队时，我们将 b 放入下标为 0 的位置，然后 tail 加 1 更新为 1。所以，在 a，b 依次入队之后，循环队列中的元素就变成了下面的样子：
通过这样的方法，我们成功避免了数据搬移操作。
代码实现一个循环队列
const CircularQueue = function {
// 数组：items，数组大小：n
let items;
let n = 0;
// head 表示队头下标，tail 表示队尾下标
let head = 0;
let tail = 0;
// 申请一个大小为 capacity 的数组
function createCircularQueuee(capacity) {
items = new Array(capacity);
n = capacity;
}
// 入队
function enqueue(item) {
// 队列满了
if ((tail + 1) % n == head) return false;
items[tail] = item;
tail = (tail + 1) % n;
return true;
}
// 出队
function dequeue() {
// 如果 head == tail 表示队列为空
if (head == tail) return null;
String ret = items[head];
head = (head + 1) % n;
return ret;
}
this.createCircularQueuee = createCircularQueuee;
this.enqueue = enqueue;
this.dequeue = dequeue;
}作者：北宸南蓁
链接：https://juejin.im/post/5d8c5790f265da5b7a753233
来源：掘金
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
