关于javascript:JS中队列和双端队列实现及应用

6次阅读

共计 3932 个字符，预计需要花费 10 分钟才能阅读完成。

队列
双端队列数据结构
利用
- 用击鼓传花游戏模仿循环队列
- 用双端对列查看一个词是否形成回文
- 生成 1 到 n 的二进制数

队列遵循先进后出 (FIFO, 也称为先来先服务) 准则的. 日常有很多这样场景: 排队购票、银行排队等.
由对列的个性, 银行排队为例, 队列应该蕴含如下基本操作:

退出队列(取号) enqueue
从队列中移除(办理业务来到) dequeue
以后排队号码(呼叫下一个人) peek
以后队列长度(以后排队人数) size
判断队列是不是空 isEmpty

class Queue {constructor() {
        // 队列长度, 类数组 length
        this.count = 0
        // 队列中所有项
        this.items = {}
        // 记录对列头, 类数组 index
        this.lowestCount = 0
    }

    enqueue(ele) {this.items[this.count++] = ele
    }

    dequeue() {if (this.isEnpty()) {return undefined}
        const ele = this.items[this.lowestCount]
        delete this.items[this.lowestCount]
        this.lowestCount++
        return ele
    }

    peek() {if (this.isEnpty()) {return}
        return this.items[this.lowestCount]
    }

    size() {
        /**
        * 当队列为非空时:
        * 1. count 是长度
        * 2. lowestCount 是下标
        * 两者关系应该 lowestCount = count - 1
        */
        return this.count - this.lowestCount
    }

    isEnpty() {return this.size() == 0
    }

    clear() {this.items = {}
        this.lowestCount = 0
        this.count = 0
    }

    toString() {if (this.isEnpty()) {return ''}
        let objString = `${this.items[this.lowestCount]}`
        for (let i = this.lowestCount + 1; i < this.count; i++) {objString = `${objString}, ${this.items[i]}`
        }
        return objString
   }

}

什么是双端队列?

容许从前端 (front) 和后端 (rear) 增加元素, 遵循的准则先进先出或后进先出.

双端队列能够了解为就是栈 (后进先出) 和队列 (先进先出) 的一种结合体. 既然是联合那么相应的操作也反对队列，栈的操作. 上面咱们定义一个Deque

addFront
removeFront
addBack
removeBack
clear
isEmpty
peekFront
prekBack
size
toString

class Deque {constructor() {this.items = {}
        this.count = 0
        this.lowestCount = 0
    }

    addFront(ele) {if (this.isEmpty()) {this.items[this.count] = ele
        } else if (this.lowestCount > 0) {
            this.lowestCount -= 1
            this.items[this.lowestCount] = ele
        } else {for (let i = this.count; i > 0; i--) {this.items[i] = this.items[i - 1]
            }
            this.items[0] = ele
        }
            this.count++
            return ele
        }

    removeFront() {if (this.isEmpty()) {return}
        const delEle = this.items[this.lowestCount]
        delete this.items[this.lowestCount]
        this.lowestCount++
        return delEle
    }

    addBack(ele) {this.items[this.count] = ele
        this.count++
    }

    removeBack() {if (this.isEmpty()) {return}

        const delEle = this.items[this.count - 1]
        delete this.items[this.count - 1]
        this.count--
        return delEle
    }

    peekFront() {if (this.isEmpty()) {return}
        return this.items[this.lowestCount]
    }

    peekBack() {if (this.isEmpty()) {return}
        return this.items[this.count - 1]
    }

    size() {return this.count - this.lowestCount}

    isEmpty() {return this.size() === 0
    }

    clear() {this.items = {}
        this.count = 0
        this.lowestCount = 0
    }

    toString() {if (this.isEmpty()) {return ''}
        let objString = `${this.items[this.lowestCount]}`
        for (let i = this.lowestCount + 1; i < this.count; i++){objString = `${objString}, ${this.items[i]}`
        }
        return objString
    }

}

击鼓传花游戏: 简略形容就是一群人围成一个圈传递花, 喊停的时花在谁手上就将被淘汰(每个人都可能在前端, 每个参与者在队列地位会一直变动)，最初只剩下一个时就是赢者. 更加具体能够自行查阅.

上面通过代码实现:

function hotPotato(elementsList, num) {
    // 创立一个容器
    const queue = new Queue()
    const elimitatedList = []
    // 把元素 (参赛者) 退出队列中
    for (let i = 0, len = elementsList.length; i < len; i++) {queue.enqueue(elementsList[i])
    }

    /**
    * 击鼓传花
    * 首先队列规定: 先进先出
    * 那么在传花过程中, 任何一个元素都可能是前端, 在传花的过程中应该就是前端地位一直变动.
    * 当喊停的时 (num 循环完), 也就是花落在谁手(谁在前端) 则会被淘汰 *（移除队列）*/

    while (queue.size() > 1) {for (let j = 0; j < num; j++) {queue.enqueue(queue.dequeue())
        }
        elimitatedList.push(queue.dequeue())
    }
    return {winer: queue.dequeue(),
        elimitatedList
    }
}

代码运行如下:


const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

console.log(hotPotato(arr, Math.ceil(Math.random() * 10))) // {winer: 5, elimitatedList: [4, 8, 2, 7, 3,10, 9, 1, 6]}
console.log(hotPotato(arr, Math.ceil(Math.random() * 10))) // {winer: 5, elimitatedList: [4, 8, 2, 7, 3,10, 9, 1, 6]}
console.log(hotPotato(arr, Math.ceil(Math.random() * 10))) // {winer: 8, elimitatedList: [10, 1, 3, 6, 2,9, 5, 7, 4]}

上一篇栈中也有波及回文的实现, 上面咱们通过双端队列来实现同样的性能.


function palindromeChecker(aString) {if (!aString || typeof aString !== 'string' || !aString.trim().length) {return false}
    const deque = new Deque()
    const lowerString = aString.toLowerCase().split('').join('')

    // 退出队列

    for (let i = 0; i < lowerString.length; i++) {deque.addBack(lowerString[i])
    }

    let isEqual = true
    let firstChar = ''let lastChar =''

    while (deque.size() > 1 && isEqual) {firstChar = deque.removeFront()
        lastChar = deque.removeBack()
        if (firstChar != lastChar) {isEqual = false}
    }

    return isEqual

}

上面通过代码演示下:


console.log(palindromeChecker('abcba')) // true 以后为回文


function generatePrintBinary(n) {var q = new Queue()
    q.enqueue('1')
    while (n-- > 0) {var s1 = q.peek()
        q.dequeue()
        console.log(s1)
        var s2 = s1
        q.enqueue(s1 + '0')
        q.enqueue(s2 + '1')
    }
}

generatePrintBinary(5) // => 1 10 11 100 101

正文完