iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 11
0
Modern Web

JavaScript Note系列 第 11

堆疊(Stack) & 佇列(Queue)

當我們碰到大量資料的時候,通常都會用陣列來處理,資料結構中處理陣列有兩種較常見的方式:堆疊(stack)與佇列(queue)。
堆疊(stack)是先進後出(FILO First In Last Out)的資料結構,意思是,先進去的資料最後出來。
可以使用push( )與pop( )來實現。
push( )
新增元素至陣列的尾端,並回傳陣列的新長度。

let ary = [];
console.log(ary.push('a')); //1
console.log(ary); //["a"]
console.log(ary.push('b')); //2
console.log(ary); //["a", "b"]
console.log(ary.push('c')); //3
console.log(ary); //["a", "b", "c"]

pop( )
刪除且回傳陣列的最後一個元素。

let ary = ['a', 'b', 'c'];
console.log(ary.pop()); //c
console.log(ary); //["a", "b"]
console.log(ary.pop()); //b
console.log(ary); //["a"]
console.log(ary.pop()); //a
console.log(ary); //[]

佇列(queue)是先進先出(FIFO First In First Out)的資料結構,意思是,先進去的資料先出來。
可以使用push( )與shift( )來實現。
shift( )
刪除且回傳陣列的第一個元素。

let ary = ['a', 'b', 'c'];
console.log(ary.shift()); //a
console.log(ary); //["b", "c"]
console.log(ary.shift()); //b
console.log(ary); //["c"]
console.log(ary.shift()); //c
console.log(ary); //[]

我們來做個練習,題目取自於LeetCode的第20題。
輸入一個string,內容包括(, ), {,},[,]這6個括號,
必須以相同的類型且正確的順序跟左括號匹配,{}()[]{[()]}都是有效的,但,))(]((是無效的。
https://leetcode.com/problems/valid-parentheses/description/
解題思考:
不論是不是巢狀括號,當遇到),},]字串的時候,就必須得跟它上一個字串元素做比較,我們可以使用堆疊(stack)的特性來完成此題目。

let ParenthesesMap = {
    ')': '(',
    ']': '[',
    '}': '{'
}
let ParenthesesAry = [];

function isValid(s) {
    if (s.length % 2 !== 0 || s.length === 0) return false;
    for (let i = 0; i < s.length; i++) {
        if ((s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{') && (i !== s.length - 1))
            ParenthesesAry.push(s.charAt(i));
        else if (ParenthesesMap[s.charAt(i)] !== ParenthesesAry.pop())
            return false;
    }
    return true;
}
console.log(isValid('))')); //false
console.log(isValid('{}()[]')); //true
console.log(isValid('{()[]()}')); //true
console.log(isValid('){')); //false
console.log(isValid('(]')); //false
console.log(isValid('{)')); //false
console.log(isValid('{}(')); //false
console.log(isValid('')); //false

先設一個物件ParenthesesMap,屬性與屬性值分別為相對應的括號,空陣列ParenthesesAry準備存放字串元素用的,只要字串元素不是偶數,表示有括號落單,所以第一個條件式篩選掉,
接下來,如果括號是左括號,且不是最後一個的話,放入陣列。
重點來了,如果遇到右括號,直接跟剛剛傳入陣列的最後一個元素比對是否為有效括號。
我們用pop方法取得陣列的最後一個元素,使用物件的屬性比對,如果是右括號對到的應該是相同類型的左括號才是有效括號,依此比對直到迴圈結束,若無錯誤,就回傳true。


上一篇
Array 陣列
下一篇
Function 函式
系列文
JavaScript Note31

尚未有邦友留言

立即登入留言