Stack in JS (including leetcode examples) < continuous update ~>

Stack (stack)

characteristic

First in, then out

Realization way

• Based on the array implementation

    //  Encapsulate stack classes 
    function Stack(){
    
      //  Stack properties 
      this.items = []

      //  Stack related operations 
      // 1.push Pressing stack 
      Stack.prototype.push = function(element){
    
         return this.items.push(element)
      }
      // 2.pop Out of the stack 
      Stack.prototype.pop = function(){
    
        return this.items.pop()
      }
      // 3.peek Look at the top of the stack 
      Stack.prototype.peek = function(){
    
        return this.items[this.items.length - 1]
      }
      // 4.isEmpty Judge whether the stack is empty 
      Stack.prototype.isEmpty = function(){
    
        return this.items.length == 0
      }
      // 5.size Get the number 
      Stack.prototype.size = function(){
    
        return this.items.length
      }
      // 6.toString To string 
      Stack.prototype.toString = function(){
    
        let res = ''
        for(let i =0;i<this.items.length;i++){
    
          res += this.items[i]+','
        }
        return res
      }
    }
	// 7.getMin Get the minimum 
	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
      }

    //  Use of stack 
    var s = new Stack()

• Based on linked list

To be added

---

leetcode Example

20. Valid parenthesis

**
 * @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. Smallest stack

//  The main idea of finding the minimum is 
//  Create another min_stack Only used to compare the current push The minimum value of and min_stack Top of stack 
//  He who is young will be push go in 
//  The last minimum is the top of the stack 
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. Using stack to realize queue

// stack1 Main stack , On behalf of the queue 
// stack2 auxiliary 
// push Functions are added directly to stack1
// pop：
// 1. First the stack1 Out of the stack , Then enter the stack to stack2 in , In this way, the inversion is realized , Again pop fall stack2, To delete the first element .
// 2. Pay attention to , After deleting the first element, do it again stack2 Reverse feed stack1 The operation of , Avoid having push Make the order out of order .
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
    }
};

Of course , This approach is too complicated , Need to optimize

496. Next bigger element I

var nextGreaterElement = function(nums1, nums2) {
    
    // Map + Stack
    let map = new Map()
    let stack = []
    let res = []
    //  Traverse nums2, Find the next largest element of each element 
    //  The idea is ： The element of the loop is larger than the element at the top of the stack , And the stack is not empty , Find the next maximum value , Use the top of the stack element as key, The next one is value
    //  Deposit in map, Put the top element of the stack pop
    nums2.forEach(item=>{
    
        while(stack.length && item>stack[stack.length-1]){
    
            map.set(stack.pop(),item)
        }
        stack.push(item)
    })
    //  There is no next maximum value for the remaining elements ,value by -1
    stack.forEach(item=>map.set(item,-1))
    //  Traverse nums1, Will meet the requirements of push To the results 
    nums1.forEach(item=>res.push(map.get(item)))
    return res
};

after leetcode When you encounter a problem to find a larger element type, you use map+stack

682. baseball game

//  Create a stack , If the default value is a number, you can push go in 
//  by C Delete the top of the stack 
//  by D be push Top of stack 2 times 
//  by + Then calculate the sum of the top of the stack and the next element on the top of the stack 
//  Finally, sum all the elements in the stack 
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. Remove the outermost bracket

//  Understanding the topic ： Think of the whole as a stack , Encountered left parenthesis in stack 、 When a right bracket is encountered, the left bracket is pushed out of the stack ; When the stack is empty , Represents finding the outermost bracket once 

//  The actual code , Set a counter , When you encounter an open parenthesis, you ++, When you encounter a closing parenthesis --
//  Left parenthesis encountered , The counter is greater than 1 when , Represents not the outermost left parenthesis , Join in res character string 
//  Right parenthesis encountered , The counter is greater than 0 when . Represents not the outermost right parenthesis , Join in res character string 
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. Delete all adjacent duplicates in the string

Similar to the matching problem , Stack is usually used

//  Traverse the string and write to the stack 
//  If the currently traversed letter is equal to the top letter of the stack , Represents the occurrence of adjacent equality , Just delete the top element of the stack 
//  If unequal, it means that this situation does not occur , Continue writing to the stack 
//  Finally, the elements in the stack meet the requirements , Just convert it to a string 
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. Using stack operations to build arrays

//  Weird code added 
//  because list Is increasing , I didn't use n, It's for your own use i Count 
//  When target The last number of the array is less than i The hour of represents that the operation has been completed 
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
};