栈题目练习

标题末尾序号对应Leedcode题序，解题思路在上篇已提到，这里为具体代码实现，使用JavaScript

1. 有效的括号 20

var isValid = function(s) {
    var arr_stack = [];

    for (var i = 0; i<s.length;i++) {
        var item = s[i];

        if (item === '(' || item === '[' || item === '{') {
            arr_stack.push(item);
        }else{
            var compose_item = arr_stack.pop();
            if (compose_item === '(' && item === ')' || compose_item === '[' && item === ']' ||compose_item === '{' && item === '}' ) {
                continue;
            }
            return false;
        }
    }
    if (arr_stack.length !==0){
        return false;
    }
    return true;
};

2. 最小栈 155

var MinStack = function() {
    this.stackdata = [];
    this.mindata = [];
    this.count = 0;
};

/** 
 * @param {number} val
 * @return {void}
 */
MinStack.prototype.push = function(val) {
    var min = this.mindata[this.count - 1];
    this.stackdata.push(val);
    this.mindata.push(min !== undefined ? (min > val ? val : min) : val);
    this.count++;
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    if (this.count === 0) return null;
    this.count--;
    this.stackdata.pop();
    this.mindata.pop();
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    if (this.count === 0) return null;
    return this.stackdata[this.count - 1];
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
    if (this.count === 0) return null;
    return this.mindata[this.count - 1];
};

3. 用栈实现队列 232

var MyQueue = function() {
    this.instack = [];
    this.outstack = [];
};

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

/**
 * Removes the element from in front of queue and returns that element.
 * @return {number}
 */
MyQueue.prototype.pop = function() {
    if(!this.outstack.length) {
        this.enterdata();
    }
    return this.outstack.pop();
};

/**
 * Get the front element.
 * @return {number}
 */
MyQueue.prototype.peek = function() {
    if(!this.outstack.length) {
        this.enterdata();
    }
    return this.outstack[this.outstack.length - 1];
};

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

MyQueue.prototype.enterdata = function() {
    while(this.instack.length) {
        this.outstack.push(this.instack.pop());
    }
}

4. 比较含退格的字串 844

var backspaceCompare = function(s, t) {
   return getstr(s) === getstr(t);
};

var getstr = function(str) {
    var stack = [];

    for (var i = 0; i < str.length; i++) {
        if (str[i] === '#') {
            stack.pop();
        }else{
            stack.push(str[i]);
        }
    }
    return stack.join('');
}

5. 基本计算器 224

var calculate = function(s) {
    var numstack = [];
    var markstack = [];
    var result = 0;

    for (var i = 0; i < s.length; i++) {
        if (s[i] === ' ') continue;
        if (s[i] === ')') {
            while(markstack[markstack.length-1] !== '(') {
                result += (computed(numstack.pop(),numstack.pop(),markstack.pop()))
            }
            markstack.pop();
            numstack.push(result);
        }
        if (isNaN(Number(s[i]))) {
            markstack.push(s[i]);
        }else{
            numstack.push(Number(s[i]));
        }
    }
    while(markstack.length) {
         result += (computed(numstack.pop(),numstack.pop(),markstack.pop()))
    }
    return result;
};

var computed = function(num1,num2,mark) {
    var result = 0;
    switch (mark) {
        case '+':
            result = num1 + num2;
            break;
        case '-':
            result = num1 - num2;
            break;
        default:
            break;
    }
    return result;
}

6. 棒球比赛 682

var calPoints = function (ops) {
    var arr = [];
    var result = 0;

    for (var index = 0; index < ops.length; index++) {
        var item = ops[index];

        if (isNaN(Number(item))) {
            var len = arr.length;

            if (item === "+" && len > 1) {
                arr.push(arr[len-1]+arr[len-2]);
            }
            if (item === "D" && len > 0) {
                arr.push(arr[len-1]*2);
            }
            if (item === "C" && len >0 ){
                arr.pop();
            }
        }else{{
            arr.push(Number(item));
        }}
    }
    while(arr.length) {
        result += arr.pop();
    }
    return result;
}

7. 下一个更大元素 496

暴力解法：

var nextGreaterElement = function(nums1, nums2) {
    var result = [];

    for (var idx = 0; idx < nums1.length; idx++){
        result.push(compare(nums1[idx],nums2));
    }
    return result;
};

var compare = function (num,nums){
    var flag = false;

    for (var i = 0; i< nums.length; i++) {
        var item = nums[i];

        if (num === item){
            flag = true;
            continue;
        }
        if (flag && num < item) {
            return item;
        }
    }
    return -1;
}

单调栈解法：

var nextGreaterElement2 = function(num1, num2) {
    var stack = [];
    var map = new Map();
    var result =[];

    num2.forEach(element => {
        while(stack.length && stack[stack.length-1]<element){
            map.set(stack.pop(),element);
        }
        stack.push(element);
    });
    stack.forEach(element => {
        map.set(element,-1);
    });
    num1.forEach(element => {
        result.push(map.get(element))
    });
    return result;
};