算法的定义：

• 一个有限指令集，每条指令的描述不依赖与语言。
• 接受一些输入
• 产生输出
• 一定在有限步骤后终止

算法的通俗理解

• Algorithm 这个单词本意就是解决问题的办法/步骤逻辑
• 数据结构的实现，离不开算法

1.数组

JS的数组API掌握的已经足够熟练了，所以不讲了。

这里只讲一下js与其他语言有关的地方

• 首先常见语言的数组不能存放不同的数据类型，因此封装是通常存放在数组中的是object类型
• 常见的语言的数组的容量不会自动改变，因此需要扩容。扩容在c是极为效率低的一个操作
• 同样低效率的操作还有在数组中间进行插入和删除的操作。因为要移动后面的或者前面的所有节点。
• 优点：
• 在有关于下标的时候，数组方便的很。

2.栈结构

• 数组是可以在任何位置进行增加或者删除的一种线性结构。
• 有时候必须对数据进行限制，对其任意性加以限制。
• 栈和队列就是这种的受限的线性结构。
• 特性：后进先出（last in first out）
• 只允许在一端进行插入和删除操作，这端叫栈顶。相对的其中另一端叫栈低
• 插入叫入栈，进栈或者压栈。
• 删除叫出栈或者退栈。
• 程序中什么是使用栈实现的呢？
• 学了这么久的编程，是否听说过，函数调用栈呢？
• 我们知道函数之间和相互调用：A调用B,B中又调用C,C中又调用D.
• 那样在执行的过程中，会先将A压入栈，A没有执行完，所有不会弹出 栈
• 在A执行的过程中调用了B,会将B压入到栈，这个时候B在栈顶，A在 栈底
• 如果这个时候B可以执行完，那么B会弹出栈，但是B有执行完吗？没有 它调用了C.
• 所以C会压栈，并且在栈顶.而C调用了D,D会压入到栈顶.
• 所以当前的栈顺序是：栈顶A->B->C->D栈顶
• D执行完，弹出栈.C/B/A依次弹出栈.
• 所以我们有函数调用栈的称呼，就来自于它们内部的实现机制.(通过 栈来实现的）

例题

• 有六个元素6,5,4,3,2,1的顺序进栈，问下列哪一个不是合法的出栈序列？(c)
• A.543612 B.453216 C.346521 D.234156

复制
// 栈的封装
function Stack() {// 栈中的属性this.items = []
​
}
// 原型要放在外面，这样不会重复执行。
// 实测放在外面新建五个对象平均0.05ms。放在外面要0.15ms
​
// 1.入栈操作
Stack.prototype.push = function (params) {
    this.items.push(params)
}
// 2.取出栈顶 元素
Stack.prototype.pop = function () {
    return this.items.pop()
}
// 3.查看栈顶 元素
Stack.prototype.peek = function () {
    return this.items[this.items.length - 1]
}
​
// 4.判断栈是否为空
Stack.prototype.isEmpty = function () {
    return this.items.length === 0
}
​
// 5.获取栈中元素个数
Stack.prototype.size = function () {
    return this.items.length
}
// 6.toString方法
Stack.prototype.toString = function () {
    let str = this.items.reduce((pre, cur) => {
        return pre + ' ' + cur
    })
    return str
}
​
console.time('global')
​
// 栈的使用
let s = new Stack()
let s1 = new Stack()
let s2 = new Stack()
let s3 = new Stack()
​
​
console.timeEnd('global')
​
// 栈的操作
// s.push(10)
// s.push(20)
// s.push(30)
// console.log(s); // Stack{ items:[10,20,30]}
// s.pop()
// console.log(s);
// console.log(s.peek());
// console.log(s);
// console.log(s.size());
// s.push(40)
// console.log(s.toString());
​
export default Stack
import Stack from './1_栈的封装.js'
​
// 100
// 计算：100/2余数：0
// 计算：50/2余数：0
// 计算：25/2余数：1
// 计算：12/2余数：0
// 计算：6/2余数：0
// 计算：3/2余数：1
// 计算：1/2余数：1
// 从底下到上面：1100100
​
// 主要是运用队栈的进去再拿出来
// 思路：
// 1.计算主要留下两个有用的数，就是余数和除法的结果。
// 2.结果保存下来接着用
// 3.余数直接放到栈里
// 4.结束条件是当除法结果为0的时候，结束。
// 5.然后把数组捣腾出来组合成字符串就行了
​
function dec2bin(decNumber) {
    let stack = new Stack()
    while (decNumber > 0) {
        stack.push(decNumber % 2)
        decNumber = Math.floor(decNumber / 2)
    }
    let res = ''
    ​
    console.log(stack.isEmpty());
    while (!stack.isEmpty()) {
        res += stack.pop()
    }
    console.log(res);
}
​
dec2bin(1)
// 队列本质还是数组
// 这波用的class 性能和直接构造原型的方法基本一致。
​
class Queue {
    constructor() {
        this.items = []
    }
    // enqueue
    emqueue(element) {
        this.items.push(element)
    }
    // dequeue
    dequeue() {
        return this.items.shift()
    }
    // front
    front() {
        return this.items[this.items.length - 1]
    }
    // isEmpty
    isEmpty() {
        return this.items.length === 0
    }
    // size
    size() {
        return this.items.length
    }
    // toString
    toString() {
        let str = this.items.reduce((pre, cur) => {
            return pre + ' ' + cur
        })
        return str
    }
}
​
​
console.time('global')
let queue = new Queue()
console.timeEnd('global')
queue.emqueue(10)
queue.emqueue(20)
queue.emqueue(30)
queue.dequeue()
console.log(queue);
​
// 导出，供2用
export default Queue
// 击鼓传花是一个常见的面试算法题.使用队列可以非常方便的实现最终的结果.
​
// 原游戏规则：
// 口 班级中玩一个游戏，所有学生围成一圈，从某位同学手里开始向旁边的同学传一束花.
// 口 这个时候某个人（比如班长）,在击鼓，鼓声停下的一颗，花落在谁手里，谁就出来表演节目.
​
// 修改游戏规则：
// 口 我们来修改一下这个游戏规则.
// 口几个朋友一起玩一个游戏，围成一圈，开始数数，数到某个数字的人自动淘汰
// 口最后剩下的这个人会获得胜利，请问最后剩下的是原来在哪一个位置上的人？
​
// 封装一个基于队列的函数
// 口 参数：所有参与人的姓名，基于的数字
// 口结果：最终剩下的一人的姓名
​
​
// 解决思路
// 1.队列里不断循环，队列外加一个计数器。
// 2.出队一个计数器+1，看计数器等不等于5，不过不等于，则证明不是第五个，所以不淘汰。
// 3.不淘汰的元素出队，然后再加入到队尾，计数器加1
// 4.淘汰的直接出队，不加入到队尾，计数器归为1
// 5.这样人越来越少，判断结束的条件是队列的元素是否等于一个
​
import Queue from './1_封装队列.js'
​
let q1 = new Queue()
​
let arr = ['小李', 'bill']
​
for (let item of arr) {
    q1.emqueue(item)
}
let i = 1
// console.log(typeof q1.size());
while (q1.size() > 1) {
    console.log(111);let tmp = q1.dequeue()
    if (i != 5) {
        q1.emqueue(tmp)
        i++
    } else if (i == 5) {
        i = 1
    }
}
​
console.log(q1);
// 优先级队列的特点：
// 口 我们知道，普通的队列插入一个元素，数据会被放在后端.并且需要前面所有的元素都处理完成后才会处理前面的数据.
// 口 但是优先级队列，在插入一个元素的时候会考虑该数据的优先级.
// 口 和其他数据优先级 进行比较.
// 口 比较完成后，可以得出这个元素在队列中正确的位置
// 口 其他处理方式，和基本队列的处理方式一样.
​
// 二优先级队列主要考虑的问题：
// 口每个元素不再只是一个数据，而且包含数据的优先级
// 口在添加方式中，根据优先级放入正确的位置.
​
// 现实中的优先级队列
// 1. 机场登机 老人和小孩，或者商务舱的多
// 2. 医院的急诊室和普通病房
import Queue from './1_封装队列.js'
​
// 优先级队列的封装
// 优先级队列和普通队列的区别仅在于 优先级队列的插入与普通的不同
// 所以可以仅仅通过定义一个插入队列，然后剩下的直接通过extends继承下来就可以了。
class PriorityQueue extends Queue {
    ​
    constructor() {
        // 要继承的话必须执行super()方法，因为super是调用原来的父类，将方法和值赋值到this上。  
        // 和原先老的es5写法是不一样的，原来的es5是通过原型链来实现的.super()  
        this.items = []
    }
    ​
    emqueue(element, priority) {
        let queueElement = new QueueElement(element, priority)
        if (this.items.length === 0) {
            this.items.push(queueElement)
        } else {
            let added = falsethis.items.every((item, index) => {
                if (queueElement.priority < item.priority) {
                    this.items.splice(index, 0, queueElement)
                    added = true;
                    // 这里用every 或者 some 都可以break。  
                    // break的方法就是 every中用return false  
                    // some中用return true  
                    return false
                }
            })
            if (!added) {
                this.items.push(queueElement)
            }
        }
    }
}
​
​
// es6 class 没有内部类的概念，所以不推荐用function写在里面这种写法
// 直接在外面写就行，性能高。
// 内部类的写法就是重复的去新建QueueElement，写在里面没有任何意义。
class QueueElement {
    constructor(element, priority) {
        this.element = element
        this.priority = priority
    }
}
​
let pq = new PriorityQueue()
​
pq.emqueue(111, 1)
pq.emqueue(222, 2)
pq.emqueue(333, 0)
pq.dequeue()
## 优先级队列
## 例题
## 实现

- 只能在前端进行删除

- 只能在后盾进行插入

先进先出（fifo first in first out）