算法的定义：

• 一个有限指令集，每条指令的描述不依赖与语言。

• 接受一些输入

• 产生输出

• 一定在有限步骤后终止

算法的通俗理解

• 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 = false
   this.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）

本作品采用《CC 协议》，转载必须注明作者和本文链接