Stack、Queue
Stack - 后进先出 First In First Out (FIFO) • Array or Linked List
Queue - 先进先出 First In Last Out (FILO) • Array or Linked List
Common Data Structure operations（通用数据结构操作） 图片来源
实战题目
// 方法一: 用 replace 替换，替换完后字符长度为 0 , 说明是合法的。 时间复杂度很高
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {
var length;
do {
length = s.length;
s = s
.replace("()", "")
.replace("{}", "")
.replace("[]", "");
} while (length !== s.length);
return s.length == 0;
};
// Accepted 64 ms 36.2 MB
// 方法二: 栈 先入先出，键key 左括号入栈， 值value 右括号与栈顶的键 key 比较，
// 如果相等继续循环比较， 如果不相当说明不合法;
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {
var stack = [];
var paren_map = {
")": "(",
"]": "[",
"}": "{"
};
for (let i = 0; i < s.length; i++) {
if (!paren_map.hasOwnProperty(s[i])) {
stack.push(s[i]);
} else if (paren_map[s[i]] != stack.pop()) {
return false;
}
}
return !stack.length;
};
// Accepted 40 ms 33.7 MB