RE4wwtR.jpg
20. 有效的括号
利用栈先进后出的特性
let isValid = function(s) {
let map = {
'{': '}',
'[': ']',
'(': ')'
}
let stack = []
for (let i = 0; i < s.length; i++) {
if (map[s[i]]) {
stack.push(s[i])
} else if (s[i] !== map[stack.pop()]) {
return false
}
}
return stack.length === 0
}
232. 用栈实现队列
栈的特点是先进后出，队列的特点是先进先出
/**
* Initialize your data structure here.
*/
var MyQueue = function() {
this.input = []
this.output = []
};
/**
* Push element x to the back of queue.
* @param {number} x
* @return {void}
*/
MyQueue.prototype.push = function(x) {
this.input.push(x)
};
/**
* Removes the element from in front of queue and returns that element.
* @return {number}
*/
MyQueue.prototype.pop = function() {
while(this.input.length) {
this.output.push(this.input.pop())
}
var first = this.output.pop()
while(this.output.length) {
this.input.push(this.output.pop())
}
return first
};
/**
* Get the front element.
* @return {number}
*/
MyQueue.prototype.peek = function() {
return this.input[0]
};
/**
* Returns whether the queue is empty.
* @return {boolean}
*/
MyQueue.prototype.empty = function() {
return !this.input.length && !this.output.length
};
844. 比较含退格的字符串
var backspaceCompare = function (S, T) {
// 先进后出 用stack
let filterStr = (str) => {
let stack = [];
for (let p of str) {
p === '#' ? stack.pop() : stack.push(p);
}
return stack.join('');
}
return filterStr(S) === filterStr(T);
};
