数据结构

数组结构

• 是一种线性结构
• 可以在数组的任意位置插入和删除数组

栈结构

• 一种受限的线性表，只允许在表的一端进行插入删除操作，这一端被称为栈顶，另一端称为栈底
• 后进先出（LIFO Last In First Out）
• 栈的封装
  
  1.基于数组

    function Stack() {
        this.items = []
    }
    Stack.prototype.push = function (element) {
        this.items.push(element)
    }
    Stack.prototype.pop = function () {
        return this.items.pop()
    }
    Stack.prototype.peek = function () {
        return this.items[this.items.length - 1]
    }
    Stack.prototype.isEmpty = function () {
        return this.items.length === 0
    }
    Stack.prototype.size = function () {
        return this.items.length
    }
    Stack.prototype.toString = function () {
        let str = ‘‘
        for (let i = 0;i < this.items.length;i++){
            str += this.items[i]
        }
        return str
    }

队列结构

• 一种受限的线性表，只允许在表的前端进行删除操作，在表的后端进行插入操作
• 先进先出（FIFO First In First Out）
• 队列的封装
  
  1.基于数组

    function Queue() {
        this.items = []
    }
    Queue.prototype.enqueue = function (element) {
        this.items.push(element)
    }
    Queue.prototype.dequeue = function () {
        return this.items.shift()
    }
    Queue.prototype.front = function () {
        return this.items[0]
    }
    Queue.prototype.isEmpty = function () {
        return this.items.length === 0
    }
    Queue.prototype.size = function () {
        return this.items.length
    }
    Queue.prototype.toString = function () {
        let str = ‘‘
        for (let i = 0;i < this.items.length;i++){
            str += this.items[i]
        }
        return str
    }

面试题：几个朋友一起玩一个游戏，围成一个圈，开始数数，数到规定数字的人自动淘汰，最后剩下的这个人会获得胜利，请问最后剩下的是原来在哪一个位置上的人

    function passGame(nameList,num) { //nameList:玩游戏的人，num:规定的数字
        const queue = new Queue()
        //将nameList的每个人依次放入队列中
        for (let i = 0;i < nameList.length;i++){
            queue.enqueue(nameList[i])
        }
        //直到队列中的人数为1才停止
        while (queue.size() > 1){
            //开始数数，数到num之前的人都安全，依次从前端出来到队列的后端排队
            for (let i = 0;i < num - 1;i++){
                queue.enqueue(queue.dequeue())
            }
            //数到数字num，删除
            queue.dequeue()
        }
        const winner = queue.front()
        return nameList.indexOf(winner)
    }

优先级队列

再插入一个元素的时候会考虑该数据的优先级，与队列中其他数据的优先级进行比较，比较完成后，可以得出该数据在队列中的正确位置

数据结构与算法--JS篇

原文：https://www.cnblogs.com/zhahuhu/p/13520917.html