js数据结构与算法 数组、栈部分

算法的定义:

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

  • 接受一些输入

  • 产生输出

  • 一定在有限步骤后终止

算法的通俗理解

  • 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 协议》,转载必须注明作者和本文链接
讨论数量: 1

欢迎大家发表自己的看法

3周前 评论

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!