最近公司內(nèi)部在開始做前端技術(shù)的技術(shù)分享，每周一個主題的 每周一練，以基礎(chǔ)知識為主，感覺挺棒的，跟著團(tuán)隊(duì)的大佬們學(xué)習(xí)和復(fù)習(xí)一些知識，新人也可以多學(xué)習(xí)一些知識，也把團(tuán)隊(duì)內(nèi)部學(xué)習(xí)氛圍營造起來。
我接下來會開始把每周一練的題目和知識整理一下，便于思考和鞏固，就像今天這篇開始。
學(xué)習(xí)的道路，很漫長，要堅(jiān)持，希望大家都能掌握自己喜歡的技術(shù)，和自己需要的技術(shù)。
本周練習(xí)內(nèi)容：數(shù)據(jù)結(jié)構(gòu)與算法 —— Stack
這些都是數(shù)據(jù)結(jié)構(gòu)與算法，一部分方法是團(tuán)隊(duì)其他成員實(shí)現(xiàn)的，一部分我自己做的，有什么其他實(shí)現(xiàn)方法或錯誤，歡迎各位大佬指點(diǎn)，感謝。
一、棧有什么特點(diǎn)，生活中有什么例子?
二、實(shí)現(xiàn)一個棧，并實(shí)現(xiàn)下面方法
方法1：ES6實(shí)現(xiàn)
class Stack { constructor (){ this.items = [] } push( element ){ this.items.push(element) } pop(){ return this.items.pop() } peek(){ return this.items[this.items.length - 1] } isEmpty(){ return this.items.length === 0 } clear(){ this.items = [] } size(){ return this.items.length }}上面實(shí)現(xiàn)的方式雖然簡單，但是內(nèi)部 items 屬性是公共的，為了滿足面向?qū)ο笞兂伤接行缘脑瓌t，我們應(yīng)該讓 items 作為私有屬性，因此我們可以使用 ES6 中 Symbol 或 WeakMap 來實(shí)現(xiàn)：
方法2：使用 ES6 的 Symbol 基本數(shù)據(jù)類型實(shí)現(xiàn)
知識點(diǎn)復(fù)習(xí)：ES6 中的 Symbol 介紹
const _items = Symbol()class Stack { constructor (){ this[_items] = [] } push (element){ this[_items].push(element) } // 剩下方法和第一種實(shí)現(xiàn)的差不多，這里省略 // 只要把前面方法中的 this.items 更改為 this[_items]}方法3：使用 ES6 的 WeakMap 實(shí)現(xiàn)
知識點(diǎn)復(fù)習(xí)：ES6 中的 WeakMap 介紹
const items = new WeakMap()class Stack { constructor (){ items.set(this, []) } push (element){ let item = items.get(this) item.push(element) } // 剩下方法和第一種實(shí)現(xiàn)的差不多，這里省略 // 只要把前面方法中的獲取 this.items 的方式，更改為 items.get(this) 獲取}三、編寫一個函數(shù)，實(shí)現(xiàn)十進(jìn)制轉(zhuǎn)二進(jìn)制
題目意思很簡單，就是十進(jìn)制轉(zhuǎn)二進(jìn)制，但是在實(shí)際工作開發(fā)中，我們更愿意實(shí)現(xiàn)的是任意進(jìn)制轉(zhuǎn)任意進(jìn)制，不過呢，我們還是以解決問題為首要目標(biāo)呀。
當(dāng)然，業(yè)務(wù)需求可以直接使用 toString(2) 方法，但是為了練習(xí)，咱還是不這么用咯。
方法1：使用前面定義的 Stack 類
這里使用前面題目中定義的 Stack 類。
/** * 十進(jìn)制轉(zhuǎn)換為二進(jìn)制 * @param {Number} bit */function bitset (bit){ if(bit == 0) return '0' if(!/^[0-9]+.?[0-9]*$/.test(bit)){ return new Error('請輸入正確的數(shù)值！') } let stack = new Stack(), result = '' while (bit > 0){ stack.push(bit % 2) bit = Math.floor(bit / 2) } while (!stack.isEmpty()){ result += stack.pop().toString() } return result}方法2：簡單實(shí)現(xiàn)
下面這個方法，其實(shí)不太好，因?yàn)闆]有怎么用到這次要練習(xí)的棧方法，哈哈。
/** * 十進(jìn)制轉(zhuǎn)換為二進(jìn)制 * @param {Number} bit */function bitset (bit){ if(bit == 0) return '0' if(!/^[0-9]+.?[0-9]*$/.test(bit)){ return new Error('請輸入正確的數(shù)值！') } let arr = [] while(bit > 0){ arr.push(bit % 2) bit = Math.floor(bit / 2) } return arr.reverse().join('')}另外可以參考：wikiHow - 從十進(jìn)制轉(zhuǎn)換為二進(jìn)制。
四、編寫一個函數(shù)，實(shí)現(xiàn)檢驗(yàn)圓括號順序的有效性
主要目的就是：該函數(shù)接收一個圓括號字符串，判斷里面的括號順序是否有效，如果有效則返回 true 反之 false。
如：
這個題目實(shí)現(xiàn)的主要方法是：遍歷字符串，先排除錯誤情況，然后將 ( 入棧保存，將 ) 入棧匹配前一個元素是否是 ( ，如果是，則 pop() 前一個元素 (，如果不是，則 push() 這個 ) 入棧，最終查看棧是否為空，若是則檢驗(yàn)成功，否則失敗。
方法1：使用前面定義的 Stack 類
這里使用前面題目中定義的 Stack 類。
/** * 檢驗(yàn)圓括號順序的有效性 * @param {String} str */function validParentheses (str){ if(!str || str.length === 0 || str[0] === ')') return false let stack = new Stack() str.split('').forEach(char => { let status = stack.peek() === '(' && char === ')' status ? stack.pop() : stack.push(char) }) return stack.isEmpty()}方法2：出入棧操作
/** * 檢驗(yàn)圓括號順序的有效性 * @param {String} str */function validParentheses (str){ if(!str || str.length === 0 || str[0] === ')') return false let arr = [] for(let i = 0; i < str.length ; i++){ str[i] === '(' ? arr.push(str[i]) : arr.pop() } return arr.length === 0}五、改造題二，添加一個 min 函數(shù)來獲得棧中最小元素
| 步驟 | 數(shù)據(jù)棧 | 輔助棧 | 最小值 |
|---|---|---|---|
| 1.push 3 | 3 | 0 | 3 |
| 2.push 4 | 3, 4 | 0, 0 | 3 |
| 3.push 2 | 3, 4, 2 | 0, 0, 2 | 2 |
| 4.push 1 | 3, 4, 2 ,1 | 0, 0, 2, 3 | 1 |
| 5.pop | 3, 4, 2 | 0, 0, 2 | 2 |
| 6.pop | 3, 4 | 0, 0 | 3 |
| 7.push | 3, 4 ,0 | 0, 0, 2 | 0 |
使用示例如下：
let stack = new Stack();stack.push(3);console.log('After push 3, Min item is', stack.min());stack.push(4);console.log('After push 4, Min item is', stack.min());stack.push(2);console.log('After push 2, Min item is', stack.min());stack.push(1);console.log('After push 1, Min item is', stack.min());stack.pop();console.log('After pop, Min item is', stack.min());stack.pop();console.log('After pop, Min item is', stack.min());stack.push(0);console.log('After push 0, Min item is', stack.min());提示：利用輔助棧（Web 端可利用數(shù)組），每次對棧 push/pop 元素時，也同時更新輔助棧（存儲最小元素的位置）
方法1：小操作
class Stack { constructor() { this.items = []; this.minIndexStack = []; } push(element) { this.items.push(element); let minLen = this.minIndexStack.length; let minItemIndex = this.minIndexStack[minLen - 1]; if(minLen === 0 || this.items[minItemIndex] > item) { this.minIndexStack.push(this.items.length - 1); } else { this.minIndexStack.push(minItemIndex); } } pop() { this.minIndexStack.pop(); return this.items.pop(); } min() { let len = this.minIndexStack.length; return (len > 0 && this.items[this.minIndexStack[len - 1]]) || 0; } peek() { return this.items[this.items.length - 1]; } // 省略其它方法}方法2：與方法1中push實(shí)現(xiàn)的差異
class Stack { constructor (){ this.items = [] // 數(shù)據(jù)棧 this.arr = [] // 輔助棧 } push( element ){ this.items.push(element) let min = Math.min(...this.items) this.arr.push( min === element ? this.size() - 1 : 0) } pop(){ this.arr.pop() return this.items.pop() } peek(){ return this.items[this.items.length - 1] } isEmpty(){ return this.items.length === 1 } clear(){ this.items = [] } size(){ return this.items.length } min (){ let last = this.arr[this.arr.length - 1] return this.items[last] }}以上所述是小編給大家介紹的數(shù)據(jù)結(jié)構(gòu)與算法（Stack）詳解整合，希望對大家有所幫助，如果大家有任何疑問請給我留言，小編會及時回復(fù)大家的。在此也非常感謝大家對VeVb武林網(wǎng)網(wǎng)站的支持！
新聞熱點(diǎn)
疑難解答
