>[success] # 實現一個雙端隊列 ~~~ 1.雙端隊列（deque，或稱 double-ended queue）是一種允許我們同時從前端和后端添加和移除 元素的特殊隊列 2.由于雙端隊列同時遵守了先進先出和后進先出原則，可以說它是把隊列和棧相結合的一種數據結構 ~~~ * 圖解  >[danger] ##### 雙端隊列封裝需要的方法 ~~~ 1.addFront(element)：該方法在雙端隊列前端添加新的元素。 2.addBack(element)：該方法在雙端隊列后端添加新的元素（實現方法和 Queue 類中的enqueue 方法相同）。 3.removeFront()：該方法會從雙端隊列前端移除第一個元素（實現方法和 Queue 類中的dequeue 方法相同）。 4.removeBack()：該方法會從雙端隊列后端移除第一個元素（實現方法和 Stack 類中的pop 方法一樣）。 5.peekFront()：該方法返回雙端隊列前端的第一個元素（實現方法和 Queue 類中的 peek方法一樣）。 6.peekBack()：該方法返回雙端隊列后端的第一個元素（實現方法和 Stack 類中的 peek方法一樣）。 ~~~ >[danger] ##### 代碼實現 ~~~ // 需要兩個標記符號 記錄隊頭 和 隊伍尾 // 需要可以有增刪改查 class Deque{ constructor(){ this.items = {} this.count = 0 // 記錄末尾 this.lowestCount = 0 // 記錄頭部 } size(){ return this.count - this.lowestCount } isEmpty(){ return this.size === 0 } /* 向頭部添加有三種情況 1.當數據為空的時候相當于是在尾部添加 2.當頭部數據索引元素大于0時候 正常向頭部添加重新記錄頭部位置 3.當頭部數據索引為0的時候就需要移動元素留出0索引 */ addFront(ele){ if(this.isEmpty()){ this.addBack(ele) }else if(this.lowestCount>0){ // 先-- 往當前的lowestCount 標記的前一位加 this.lowestCount -- this.items[this.lowestCount] = ele }else{ // 反向循環 for(let i = this.count;i>0;i--){ this.items[i] = this.items[i-1] } // 移位后要更新新的尾部指針 this.count++ this.items[0] = ele } } // 向末尾添加數據 addBack(ele){ this.items[this.count] = ele this.count ++ } // 移除隊伍頭部元素 removeFront(){ if(this.isEmpty()){ return undefined } const res = this.items[this.lowestCount] delete this.items[this.lowestCount] this.lowestCount ++ return res } // 移除隊伍尾部 removeBack() { if (this.isEmpty()) { return undefined; } this.count--; const result = this.items[this.count]; delete this.items[this.count]; return result; } // 返回頭部元素 peekFront() { if (this.isEmpty()) { return undefined; } return this.items[this.lowestCount]; } // 返回尾部元素 peekBack() { if (this.isEmpty()) { return undefined; } return this.items[this.count - 1]; } // 重置 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; } } ~~~ * 使用 ~~~ const deque = new Deque(); deque.addBack('John'); deque.addBack('Jack'); deque.removeFront(); deque.removeBack(); deque.addFront('wang'); deque.addFront('wang'); // 打印結果： {0: "wang", 1: "wang"} ~~~ >[info] ## 回文檢查 ~~~ 1.利用雙端隊列首位都可以進出的原則 ~~~ >[danger] ##### 代碼 ~~~ export function palindromeChecker(aString) { if ( aString === undefined || aString === null || (aString !== null && aString.length === 0) ) { return false; } const deque = new Deque(); const lowerString = aString.toLocaleLowerCase().split(' ').join(''); let firstChar; let lastChar; for (let i = 0; i < lowerString.length; i++) { deque.addBack(lowerString.charAt(i)); } while (deque.size() > 1) { firstChar = deque.removeFront(); lastChar = deque.removeBack(); if (firstChar !== lastChar) { return false; } } return true; } ~~~ * 運行 下面打印都為true ~~~ console.log('a', palindromeChecker('a')); console.log('aa', palindromeChecker('aa')); console.log('kayak', palindromeChecker('kayak')); console.log('level', palindromeChecker('level')); console.log('Was it a car or a cat I saw', palindromeChecker('Was it a car or a cat I saw')); console.log('Step on no pets', palindromeChecker('Step on no pets')); ~~~ >[danger] ##### 總結 ~~~ 1.也可以用已知的api 來做這道題 ~~~ ~~~ var isPalindrome = function(x) { if ( x < 0 ) return false let str = '' + x // 轉成字符串類型 return Array.from(str).reverse().join('') === str }; ~~~