JS中的栈（含leetcode例题）＜持续更新~＞

栈(stack)

特性

先进后出

实现方式

• 基于数组实现

    // 封装栈类
    function Stack(){
    
      // 栈的属性
      this.items = []

      // 栈的相关操作
      // 1.push压栈
      Stack.prototype.push = function(element){
    
         return this.items.push(element)
      }
      // 2.pop出栈
      Stack.prototype.pop = function(){
    
        return this.items.pop()
      }
      // 3.peek查看栈顶
      Stack.prototype.peek = function(){
    
        return this.items[this.items.length - 1]
      }
      // 4.isEmpty判断栈是否为空
      Stack.prototype.isEmpty = function(){
    
        return this.items.length == 0
      }
      // 5.size获取个数
      Stack.prototype.size = function(){
    
        return this.items.length
      }
      // 6.toString转为字符串
      Stack.prototype.toString = function(){
    
        let res = ''
        for(let i =0;i<this.items.length;i++){
    
          res += this.items[i]+','
        }
        return res
      }
    }
	// 7.getMin获取最小值
	Stack.prototype.toString = function(){
    
    	var min = this.item[0]
    	for(var i = 1 ;i<this.item.length ; i++){
    
     	   if(this.item[i]<min){
    
     	       min = this.item[i]
     	   }
    	}
    	return min
      }

    // 栈的使用
    var s = new Stack()

• 基于链表实现

待补充

---

leetcode例题

20. 有效的括号

**
 * @param {
    string} s
 * @return {
    boolean}
 */
var isValid = function(s) {
    
    var isMatch = function(left,right){
    
        if(left==='(' && right===')') return true
        if(left==='[' && right===']') return true
        if(left==='{' && right==='}') return true
        return false
    }

    const stack = []
    const leftMoudle = "([{"
    const rightMoudle = "}])"
    for(let i = 0 ; i < s.length ; i++){
    
        if(leftMoudle.includes(s[i])){
    
            stack.push(s[i])
        }else if(rightMoudle.includes(s[i])){
    
            if(isMatch(stack[stack.length-1],s[i])){
    
                stack.pop()
            }else{
    
                return false
            }
            
        }
    }
    if(stack.length === 0){
    
        return true
    }else{
    
        return false
    }

};

155. 最小栈

// 求最小值的主要思路是
// 创建另一个min_stack只用来比较当前push的最小值和min_stack的栈顶
// 谁小就把谁push进去
// 最后的最小值就是栈顶
var MinStack = function() {
    
    this.item = []
    this.min_stack = [Infinity]
};

/** * @param {number} val * @return {void} */
MinStack.prototype.push = function(val) {
    
    if(val<this.min_stack[this.min_stack.length-1]){
    
        this.min_stack.push(val)
    }else{
    
        this.min_stack.push(this.min_stack[this.min_stack.length-1])
    }
    return this.item.push(val)
    
};

/** * @return {void} */
MinStack.prototype.pop = function() {
    
    this.min_stack.pop()
    return this.item.pop()
};

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

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

232. 用栈实现队列

// stack1为主栈，代表队列
// stack2辅助
// push功能直接加在stack1
// pop：
// 1.先将stack1出栈，再入栈到stack2中，这样就实现了逆置，再pop掉stack2，实现删除第一个元素。
// 2.此时要注意，删除第一个元素后要再进行一遍将stack2逆置给stack1的操作，避免中间有push使得顺序错乱。
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() {
    
    while(this.stack1.length){
    
        let n = this.stack1.pop()
        this.stack2.push(n)   
    }
    const res =  this.stack2.pop()
    while(this.stack2.length){
    
        let n = this.stack2.pop()
        this.stack1.push(n)   
    }
    return res
};

/** * @return {number} */
MyQueue.prototype.peek = function() {
    
    return this.stack1[0]
};

/** * @return {boolean} */
MyQueue.prototype.empty = function() {
    
    if(this.stack1[0]){
    
        return false
    }else{
    
        return true
    }
};

当然，这种方式复杂度太高，需要优化

496. 下一个更大元素 I

var nextGreaterElement = function(nums1, nums2) {
    
    // Map + Stack
    let map = new Map()
    let stack = []
    let res = []
    // 遍历nums2，找到每一个元素的下一个最大元素
    // 思路为：循环的元素大于栈顶元素，且栈不为空，即找到下一个最大值，将栈顶元素作为key，下一个作为value
    // 存入map，将栈顶元素pop
    nums2.forEach(item=>{
    
        while(stack.length && item>stack[stack.length-1]){
    
            map.set(stack.pop(),item)
        }
        stack.push(item)
    })
    // 剩余元素没有下一个最大值，value为-1
    stack.forEach(item=>map.set(item,-1))
    // 遍历nums1，将符合要求的push到结果中
    nums1.forEach(item=>res.push(map.get(item)))
    return res
};

之后leetcode中遇到求一个更大元素类型的题都是使用map+stack

682. 棒球比赛

// 创建栈，如果默认为数字就直接push进去
// 为C则删除栈顶
// 为D则push栈顶的2倍
// 为+则计算栈顶和栈顶下一个元素之和
// 最后将栈内所有元素求和
var calPoints = function(ops) {
    
    let sum = 0
    const stack = []
    for(let item of ops){
    
       switch(item){
    
           case 'C':
            stack.pop()
            break
           case 'D':
            stack.push(stack[stack.length-1]*2)
            break
           case '+':
            stack.push(stack[stack.length-2]+stack[stack.length-1])
            break
           default:
            stack.push(parseInt(item))
            break
       } 
    }
    for(let i=0;i<stack.length;i++){
    
        sum = sum + stack[i]
    }
    return sum
};

1021. 删除最外层的括号

// 理解题目：将整体想成一个栈，遇到左括号入栈、遇到右括号将左括号出栈；当栈为空的时候，代表找到了一次最外层括号

// 实际代码，设置一个计数器，遇到左括号就++，遇到右括号就--
// 遇到左括号，计数器大于1时，代表不是最外层左括号，加入res字符串
// 遇到右括号，计数器大于0时。代表不是最外层右括号，加入res字符串
var removeOuterParentheses = function(s) {
    
    let num = 0
    let res = ""
    for(let item of s){
    
        if(item=='('){
    
            num++
            if(num>1){
    
                res += item
            }
        }else{
    
            num--
            if(num>0){
    
                res += item
            }
        }
    }
    return res
};

1047. 删除字符串中的所有相邻重复项

类似于匹配问题，一般都会用到栈

// 遍历字符串写入栈
// 如果当前遍历的字母和栈顶字母相等，代表出现相邻相等，就删除栈顶元素
// 如果不等代表没有出现这种情况，继续写入栈
// 最后栈内的元素就是满足要求的，转为字符串即可
var removeDuplicates = function(s) {
    
    const stack = []
    for(let i=0;i<s.length;i++){
    
        if(stack[stack.length-1] == s[i]){
    
            stack.pop()
        }else{
    
            stack.push(s[i])
        }
    }
    return stack.join('')
};

1441. 用栈操作构建数组

// 奇奇怪怪的代码增加了
// 因为list是递增的，我就没有使用n，而是自己使用i计数
// 当target数组的最后一个数小于i的时代表已经完成操作
var buildArray = function(target, n) {
    
    const res = []
    let i=1
    while(target[target.length-1]>=i){
    
        for(let j=0;j<target.length;j++){
    
            if(target[j]==i){
    
                res.push("Push")
                i++
            }else{
    
                res.push("Push","Pop")
                i++
                j--
            }
        }
    }
    return res
};