隊列

隊列 雙端隊列數(shù)據(jù)結(jié)構(gòu) 應用 用擊鼓傳花游戲模擬循環(huán)隊列 用雙端對列檢查一個詞是否構(gòu)成回文 生成 1 到 n 的二進制數(shù)

隊列和雙端隊列

隊列遵循先進后出(FIFO, 也稱為先來先服務) 原則的. 日常有很多這樣場景: 排隊購票、銀行排隊等.由對列的特性,銀行排隊為例, 隊列應該包含如下基本操作:

加入隊列(取號) enqueue 從隊列中移除(辦理業(yè)務離開) dequeue 當前排隊號碼(呼叫下一個人) peek 當前隊列長度(當前排隊人數(shù)) size 判斷隊列是不是空 isEmpty

class Queue { constructor() { // 隊列長度, 類數(shù)組 length this.count = 0 // 隊列中所有項 this.items = {} // 記錄對列頭, 類數(shù)組 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 是下標 * 兩者關(guān)系應該 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 }}

雙端隊列(deque 或 double-ended queue)

什么是雙端隊列?

允許從前端(front)和后端(rear)添加元素, 遵循的原則先進先出或后進先出.雙端隊列可以理解為就是棧(后進先出)和隊列(先進先出)的一種結(jié)合體. 既然是結(jié)合那么相應的操作也支持隊列，棧的操作. 下面我們定義一個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 }}

隊列的應用

擊鼓傳花游戲

擊鼓傳花游戲: 簡單描述就是一群人圍成一個圈傳遞花,喊停的時花在誰手上就將被淘汰(每個人都可能在前端,每個參與者在隊列位置會不斷變化)，最后只剩下一個時就是贏者. 更加詳細可以自行查閱.

下面通過代碼實現(xiàn):

function hotPotato(elementsList, num) { // 創(chuàng)建一個容器 const queue = new Queue() const elimitatedList = [] // 把元素(參賽者)加入隊列中 for (let i = 0, len = elementsList.length; i < len; i++) { queue.enqueue(elementsList[i]) } /** * 擊鼓傳花 * 首先隊列規(guī)則: 先進先出 * 那么在傳花過程中,任何一個元素都可能是前端, 在傳花的過程中應該就是前端位置不斷變化. * 當喊停的時(num 循環(huán)完), 也就是花落在誰手(誰在前端)則會被淘汰*（移除隊列） */ 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]}

判斷回文

上一篇棧中也有涉及回文的實現(xiàn), 下面我們通過雙端隊列來實現(xiàn)同樣的功能.

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 當前為回文

生成 1 到 n 的二進制數(shù)

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

到此這篇關(guān)于JS中隊列和雙端隊列實現(xiàn)及應用詳解的文章就介紹到這了,更多相關(guān)JS 雙端隊列 內(nèi)容請搜索好吧啦網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持好吧啦網(wǎng)！