javaScript力扣刷题——简单栈

20. 有效的括号

声明栈let stack=[],注意栈的下标也从0开始

var isValid = function(s) {
    let stack=[],len = s.length;
    if(len%2) return false;
    var map = new Map([[')','('],['}','{'],[']','[']]);
    for(let i of s){
        if(map.get(i)){
           if(stack[stack.length-1]!=map.get(i)) return false;
           else stack.pop();
        }
        else{
            stack.push(i);
        }
    }
    return !stack.length;
};

155. 最小栈

使用辅助栈存储栈的最小值

注意

  • 每当有元素出栈时,要判断出栈的是否是最小元素,如果是,则 min_stack 的栈顶也出栈,原本第二小的元素成了新的栈顶元素,备胎转正!

prototype(JS对象),类函数

不用let var 直接使用this在类之间使用

var MinStack = function() {
    this.stack = [];
    this.min_stack=[];
};

/** 
 * @param {number} val
 * @return {void}
 */
MinStack.prototype.push = function(val) {
    this.stack.push(val);
    if(val<=this.getMin()||this.min_stack.length==0){
        this.min_stack.push(val);
    }
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {    
    if(this.getMin()==this.stack[this.stack.length-1]){
        this.min_stack.pop();}
    this.stack.pop();

};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
     return this.stack[this.stack.length-1];
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
    return  this.min_stack[this.min_stack.length-1];
};

232. 用栈实现队列

empty( )——如果堆栈是空的,则返回true,当堆栈包含元素时,返回false;

stack1.peek() 返回栈顶元素,但不在堆栈中删除它。
Stack2.pop() 返回栈顶元素,并在进程中删除它。

不能直接判断栈是否为,只能判断栈的长度是否为0。

js不能用peek函数,必须用 stack [stack.length-1] 手动检查栈顶。

var MyQueue = function() {
    this.stack1=[];//进栈
    this.stack2=[];//出栈
};

/** 
 * @param {number} x
 * @return {void}
 */
MyQueue.prototype.push = function(x) {
    this.stack1.push(x);
};

/**
 * @return {number}
 */
MyQueue.prototype.pop = function() {   
    if(!this.stack2.length) { 
        while(this.stack1.length){
            this.stack2.push(this.stack1.pop());
        }
    }
 return this.stack2.pop();
};

/**
 * @return {number}
 */
MyQueue.prototype.peek = function() {
     if(!this.stack2.length) { 
        while(this.stack1.length){
            this.stack2.push(this.stack1.pop());
        }
    }
 return this.stack2[this.stack2.length-1];
};

/**
 * @return {boolean}
 */
MyQueue.prototype.empty = function() {
    return !this.stack1.length&&!this.stack2.length;
};

496. 下一个更大元素 I

问题1.没读懂题,本题只与nums2大小有关,与nums1顺序无关

2.第一次碰到简单栈,即栈中数据从大到小排列

var nextGreaterElement = function(nums1, nums2) {
    let stack = [];   
    var map = new Map();
    for(let i of nums2){
        while(stack.length&&i>stack[stack.length-1]){
            map.set(stack.pop(),i);
        }
        stack.push(i);
    }
    while(stack.length){
        map.set(stack.pop(),-1);
    }
    let ans = [];
    for(let j of nums1){
        ans.push(map.get(j));
    }
    return ans;
};

682. 棒球比赛

注意switch的用法,default的拼写

var calPoints = function(ops) {
    let stack=[];
    for(let i of ops){
        switch(i){
            case "C":
            stack.pop();
            break;
            case "D":
            stack.push(stack[stack.length-1]*2);
            break;
            case "+":
            stack.push(Number(stack[stack.length-1])+Number(stack[stack.length-2]));
            // stack.push(+stack[stack.length-1] + +stack[stack.length-2]);
            break;
            default:
            stack.push(i);
        }
    }
    var ans = 0;
    for(let j of stack){
        ans += Number(j);
        //ans += +j; +表示是数字
    }
    return ans;
};

225. 用队列实现栈​​​​​​v

栈数据结构的访问规则是LIFO(后进先出)pop(),push()

队列,FIFO(Fist-In-First-Out,先进先出)。队列在列表的末端添加项,从列表的前端移除项。

push()

shift()方法把数组的第一个元素从其中删除

var MyStack = function() {
    this.que1=[];
    this.que2=[];
};

/** 
 * @param {number} x
 * @return {void}
 */
MyStack.prototype.push = function(x) {
    this.que1.push(x);
};

/**
 * @return {number}
 */
MyStack.prototype.pop = function() {
    if(!this.que1.length){this.que1 = this.que2;this.que2=[];}
    while(this.que1.length>1){
        this.que2.push(this.que1.shift());
    }
    console.log(this.que1);
    
    return this.que1.shift();
};

/**
 * @return {number}
 */
MyStack.prototype.top = function() {
    return this.que1.length ? this.que1[this.que1.length-1]:this.que2[this.que2.length-1];
};

/**
 * @return {boolean}
 */
MyStack.prototype.empty = function() {
    return !this.que1.length&&!this.que2.length;
};

栈:

1.let  stack=[];

2.栈pop()和push(i);队列shift(),push(i)

3.使用辅助栈,简单栈(下大上小),配合哈希表

4.栈顶stack [stack.length-1]

你可能感兴趣的