题目出自LeetCodehttps://leetcode-cn.com

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

var isValid = function(s) {
    var arr = s.split('')
    var stack = []
    for(let i = 0;i<arr.length;i++){
        if(stack.length===0){
            stack.push(arr[i])
        }else{
            let top = stack[stack.length-1]
            if((top=='['&&arr[i]==']') || (top=='('&&arr[i]==')') || (top=='{'&&arr[i]=='}')){
                stack.pop()
            }else{
                stack.push(arr[i])
            }
        }
    }
    if(stack.length==0) return true
    return false
};

两个栈实现一个队列

/**
 * Initialize your data structure here.
 */
var MyQueue = function() {
    this.stack1 = []
    this.stack2 = []
};

/**
 * Push element x to the back of queue. 
 * @param {number} x
 * @return {void}
 */
MyQueue.prototype.push = function(x) {
    this.stack1.push(x)
};

/**
 * Removes the element from in front of queue and returns that element.
 * @return {number}
 */
MyQueue.prototype.pop = function() {
    while(this.stack1.length!==0){
        this.stack2.push(this.stack1.pop())
    }
    let pop =  this.stack2.pop()
    while(this.stack2.length!==0){
        this.stack1.push(this.stack2.pop())
    }
    return pop
};

/**
 * Get the front element.
 * @return {number}
 */
MyQueue.prototype.peek = function() {
    while(this.stack1.length!==0){
        this.stack2.push(this.stack1.pop())
    }
    let pop =  this.stack2.pop()
    this.stack2.push(pop)
    while(this.stack2.length!==0){
        this.stack1.push(this.stack2.pop())
    }
    return pop
};

/**
 * Returns whether the queue is empty.
 * @return {boolean}
 */
MyQueue.prototype.empty = function() {
    return this.stack1.length===0
};

var obj = new MyQueue()
obj.push(1)
var param_2 = obj.pop()
var param_3 = obj.peek()
var param_4 = obj.empty()

两个队列实现一个栈

/**
 * Initialize your data structure here.
 */
var MyStack = function() {
    this.queue1 = []
    this.queue2 = []
};

/**
 * Push element x onto stack. 
 * @param {number} x
 * @return {void}
 */
MyStack.prototype.push = function(x) {
    this.queue1.push(x)
};

/**
 * Removes the element on top of the stack and returns that element.
 * @return {number}
 */
MyStack.prototype.pop = function() {
    while(this.queue1.length>1){
        this.queue2.push(this.queue1.shift())
    }
    let pop = this.queue1.shift()
    while(this.queue2.length!==0){
         this.queue1.push(this.queue2.shift())
    }
    return pop
};

/**
 * Get the top element.
 * @return {number}
 */
MyStack.prototype.top = function() {
    while(this.queue1.length>1){
        this.queue2.push(this.queue1.shift())
    }
    let pop = this.queue1.shift()
    this.queue2.push(pop)
    while(this.queue2.length!==0){
         this.queue1.push(this.queue2.shift())
    }
    return pop
};

/**
 * Returns whether the stack is empty.
 * @return {boolean}
 */
MyStack.prototype.empty = function() {
    return this.queue1.length==0
};

 var obj = new MyStack()
 obj.push(1)
 var param_2 = obj.pop()
 var param_3 = obj.top()
 var param_4 = obj.empty()

优先队列

• 二叉堆
• 二叉搜索树

以小顶堆为例

数据流中的第K大元素

维护一个小顶堆，堆的size为k，堆顶元素即为第K大元素

滑动窗口最大值

1 3 -1 -3 5 3 6 k=3 队列大小固定

• 维护一个最大堆，删除离开的元素，加入新的元素，依次把堆顶元素push进数组即可
• 维护一个窗口大小K的双端队列，首先前K个加入这个队列，然后维护队列 最大值永远在左边 可以剔除新入的值

var maxSlidingWindow = function (nums, k) {
    if(nums.length===0) return []
    let arr = []
    let right = k
    for (let i = 0; i <= nums.length - right; i++, k++) {
        let window = nums.slice(i,k)
        let max = Math.max(...window)
        arr.push(max)
    }
    return arr
};