关于javascript:前端算法系列之一时间复杂度空间复杂度以及数据结构栈队列的实现

一、此系列的原因和打算

前段时间遇到一个理论问题怎么最优取币的问题，数学形容就是如下多元一次方程求解问题：

1x + 5y +10z + 15k + 20*j = 16；刚开始想着如何求解多元方程，王矩阵求解去了，后果越做越简单，前面发现这个和背包问题很像；而后就再重温一下一些算法和数据结构的常识，也就有了这个系列，我打算是把相干数据结构都一一介绍一遍，以及用 JavaScript 实现一遍，而后一些经典用于和实例；话不多说从最根本的开始：复杂度、栈、队列；

二、复杂度

说到算法和数据结构无非就是要解决两个问题：1、是如何更加疾速精确的失去预期后果；2、如何占用尽可能少的资源来失去预期后果；而这两个问题也就是咱们平时说到的性能问题，解决了这两个问题也就解决了大部分的性能问题；那怎么去掂量或者说去取舍这两者呢，有的时候这两者是不可兼得的，要不是为了占用少的资源而舍去工夫的谋求，要不就是为了更疾速的达到预期后果而就义掉肯定的资源存储，这里波及到空间复杂度和工夫复杂度

空间复杂度：这个就是指为实现某个性能或者办法要占用咱们电脑的内存资源，对于很多状况下可能内存资源不是首要的，只有速度快能实现，比方排序中的计数排序它会要定义一个两头数组，数组的长度是要排序数组的最大值，这样无疑是须要更多的内存开销的；

工夫复杂度：工夫复杂度用大 O 来示意，尽管咱们无奈用从代码去精确的计算执行的工夫，这也是不事实因为这个工夫和操作系统、硬件都有关系，所以咱们个别是有预估值来示意；艰深点就是看代码被反复执行的次数 O(n)；

O(1): 这种状况不管这么执行 count 办法，办法外面 ++ n 都只会执行一次，不会随着参数 n 的减少而变动，这种工夫复杂度是一个常数；

function count (n) {return ++n;} count(n);

O(n): 这种状况就是随着参数的变动，代码被执行的次数出现线性化的变动；

function consoleFn(n) {for(let i = 0; i < n; i++){console.log(i) 
    }
}

O(log2n)：这种咱们称为对数复杂程度；像二分法查找之类的；2^i = n => 得出 i = log2n；

function consoleFn(n) { 
    let i = 1;
    while(i < n){
        i = i * 2; 
        console.log(i); 
    } 
}

O(nlog2n)：线性对数；像快排的工夫复杂度

function consoleFn(n) {for(let j = 0; j < n; j++) { 
        let i = 1;
        while(i < n){
            i = i * 2;
            console.log(i);
        }
    }
}

O(n2)：这种状况就是执行次数会随着 n 的减少而呈现倍数的减少；

function consoleFn(n) {for(let i = 0; i < n; i++){for(let j = 0; j < n; j++){console.log(i)
     }
   }
}

数据结构：

1、栈

栈是一种听从先进后出（FILO）准则的有序汇合。新增加或待删除的元素都保留在栈的同一端，称作栈顶，另一端就叫栈底。在栈里，新元素都凑近栈顶，旧元素都靠近栈底。

怎么实现一个栈型数据结构呢？

首先咱们先定一下栈他的一些 api:

push(val)：栈顶减少一个元素；

size()：返回栈的大小；

isEmpty(): 返回栈是否是空

pop()：出栈

clear(): 清空栈

peek(): 返回栈顶元素

export default class Stack {constructor() {this.items = [];
    }
    push(val) {this.items.push(val);
    }
    size() {return this.items.length;}
    isEmpty() {return this.items.length === 0;}
    pop() {return this.items.pop();
    }
    peek() {return this.items[this.items.length - 1]
    }
    clear() {this.items = [];
    }
}

简略操作：

const stack = new Stack();
console.log(stack.isEmpty()); // true
stack.push(5);
stack.push(8);
stack.push(11);
stack.push(15);
console.log(stack.isEmpty()); // false
console.log(stack.size());// 4
console.log(stack.peek());//15
stack.pop();// 15
console.log(stack.size());// 3
console.log(stack.peek());//11

思考：栈的理论利用？

vue 中对模板进行解析的时候判断模板字符是否非法就使用了栈，这和很多编辑器在书写代码时候校验咱们写的 HTML 元素是否闭合一样的原理。

2、队列；

队列是遵循先进先出（FIFO，也称为先来先服务）准则的一组有序的项。队列在尾部增加新元素，并从顶部移除元素。最新增加的元素必须排在队列的开端。在事实中，最常见的队列的例子就是排队。

怎么实现一个队列数据结构呢？

首先咱们也先定一下队列他的一些 api:

enqueue(val)：队列 减少一个元素；

size()：返回队列的大小；

isEmpty(): 返回队列是否是空

dequeue()：出队列

clear(): 清空队列

peek(): 返回队列的首位

export default class Queue {constructor() {this.items = [];
    }
    enqueue(val) {this.items.push(val);
    }
    size() {return this.items.length;}
    isEmpty() {return this.items.length === 0;}
    dequeue() {return this.items.shift();
    }
    peek() {return this.items[0]
    }
    clear() {this.items = [];
    }
}

简略操作：

const queue = new Queue();
queue.enqueue('a');
queue.enqueue('b');
queue.enqueue('c');
queue.enqueue('d');
console.log(queue.isEmpty()); // true
console.log(queue.size());// 4
console.log(queue.peek());// a
console.log(queue.dequeue());;// a
console.log(queue.dequeue());;// b
console.log(queue.dequeue());;// c

队列的利用比拟常见，比方很多工作事件队列、vue 的更新队列、vue 的 mixin 合并队列，都是依据先进先被执行先出队的准则

思考：咱们在下面实现队列和栈有没有更好的实现形式？下面实现有什么问题？

3、双端队列

双端队列是一种容许咱们同时从前端和后端增加和移除元素的非凡队列。他是基于根底队列上的变种

api 接口的定义:

addFront(element)：该办法在双端队列前端增加新的元素。

addBack(element)：该办法在双端队列后端增加新的元素。

removeFront()：该办法会从双端队列前端移除第一个元素。

removeBack()：该办法会从双端队列后端移除第一个元素。

peekFront()：该办法返回双端队列前端的第一个元素。

peekBack()：该办法返回双端队列后端的第一个元素。

代码实现：

import Queue from "./QueueArr";

export class Deque extends Queue{constructor() {super();
    }
    addFront(element){this.items.unshift(element);
    }
    addBack(element) {this.enqueue(element);
    }
    removeFront() {return this.dequeue();
    }
    removeBack() {return this.items.pop();
    }
    peekFront() {return this.items[0];
    }
    peekBack() {return this.items[this.items.length - 1];
    }
}

简略操作：

const deque = new Deque();
deque.addFront('b');
deque.addBack('c');
deque.addFront('a');
deque.addBack('d');
console.log(deque.size()) // 4
console.log(deque.peekFront());;// a
console.log(deque.peekBack());// d
console.log(deque.removeFront());//a
console.log(deque.removeBack());//d

双端队列的利用：

查看回文；

查看一段英文是不是回文，个别比较简单的办法是将其转换成数组，而后倒序一下再转化成字符串看两者是否雷同，来判断是否是回文；比方：ababa 倒序过去还是 ababa；这就是回文了，同样的咱们也能够通过应用双端队列来实现判断是不是回文；大略思路就是将字符串放进一个双端队列，而后别离取出队头和队尾看是否雷同，直到队列出列元素小于等于 1 个元素，代码实现如下：

import {Deque} from "./Deque";

export const palindromeChecked = (str) => {if(!str){return false;}
    const deque = new Deque();
    const strs = str.toLowerCase().split('');
    for (let i = 0; i < strs.length; i++) {deque.addBack(strs[i]);
    }
    let start = '', end ='', isTrue = true;
    while (deque.size() > 1 && isTrue) {start = deque.removeFront();
        end = deque.removeBack();
        if (start != end) {isTrue = false;}
    } 
    return isTrue
}
console.log(palindromeChecked('adfds'));// false
console.log(palindromeChecked('adada'));// true

思考：通过学习了队列和栈，如何使用队列和栈去实现一个四则运算，比方 cal(‘1+2-3+6/3’)失去后果是 16

局部思考解答

判断标签是否闭合

思路：

1、对字符串进行标签解析

2、创立标签栈，遇到开始标签进行压入栈，遇不到闭合标签进行出栈操作

3、匹配到最初，判断栈是否为空，如果为空阐明都闭合了，如果还有阐明有标签未能闭合

队列和栈更好的实现

咱们上面对栈和队列的实现都是使用了数组，对数组进行元素的删除和减少，而对数组的操作实际上比拟耗费的，像其余动态语言一样，其实 JavaScript 对数组操作一样是很简单的只是 js 引擎帮咱们做了这些事件，例如从数组的头部删除或者减少一个元素，其实外部都要进行平移数组其余元素，比方插入一个元素数组要先把长度减少，而后所有元素后移一位空出头部再把要减少的元素放入，所以相比起来使用对象来实现会比数组更加的好

export default class Queue {constructor() {
        this.counter = 0;// 计数器计算队列大小
        this.items = {}; // 队列存储
        this.lowestCount = 0; // 队列头
    }
    // 返回队列首位
    peek() {return this.items[this.lowestCount];
    }
    enqueue(element) {this.items[this.counter] = element;
        this.counter++;
    }
    dequeue() {if (this.isEmpty()) {return undefined;}
        const result = this.items[this.lowestCount];
        delete this.items[this.lowestCount];
        this.lowestCount++;
        return result;
    }
    isEmpty() {return this.size() === 0;
    }
    size() {return this.counter - this.lowestCount;}
    clear() {
        this.counter = 0;
        this.lowestCount = 0;
        this.items = {};}
}

四则运算

思路：

1、实现词法剖析解析出一个词法队列：tokens;

2、拿到 tokens 进行解决，这时候定义一个数字栈，一个操作数栈

3、当遇到数字时候将数字压入数字栈，遇到操作符时候，判断是否执行运算，能运算就从数字栈中出栈 2 个数，而后操作符栈出栈一个操作符，而后做相应的操作运算，并把运算后果压入数字栈，作为下一次的运算数

1+2-3+6/3 => tokens = [

‘{type: ‘number’,value:’1′},

{type: ‘operator’, value: ‘+’},

‘{type: ‘number’,value:’2′},

{type: ‘operator’, value: ‘-‘},

‘{type: ‘number’,value:’3′},

{type: ‘operator’, value: ‘+’},

‘{type: ‘number’,value:’6′},

{type: ‘operator’, value: ‘/’},

‘{type: ‘number’,value:’3′},

]’