The concept of the stack

According to the encyclopedia:

As a kind of data structure, stack is a special linear table that can only be inserted and deleted at one end. It stores data in accordance with the principle of “first in, last out”, the first data is pushed to the bottom of the stack, the last data at the top of the stack, when the need to read data from the top of the stack (the last data is read first).

It would look something like this:

Image source: Wikipedia

The stack is a very simple data structure, but it can achieve many key uses, such as browser forward and backward functions, function context in JS and other functions.

Let’s look at how the stack’s data structure is implemented.

Stack data structure

We can use the constructor or class to define the stack structure:

/** *; /**; /**; /**; /**; /**; /**; /**; /**@param {*} MaxSize Maximum stack capacity */
function Stack(maxSize) {
  // Put the element on the stack
  this.elements = [];
  this.maxSize = maxSize || 0;
  // The position of the topIndex element on the stack
  this.topIndex = -1;
}

class Stack {
  constructor(maxSize) {
    this.elements = [];
    this.maxSize = maxSize || 0;
    this.topIndex = -1; }}Copy the code

The underlying algorithm of the stack

There are few basic stack algorithms, mainly including the following four. It should be noted that pop out of the stack algorithm can clear out the stack elements or not. If the storage space requirements are high, it needs to be cleared.

/** * initialize stack *@param {*} MaxSize Stack capacity *@returns Stack* /
function init(maxSize) {
  return new Stack(maxSize);
}

/** * push *@param {*} Stack stack *@param {*} Element The pushed element *@returns 1 - success; 0 - * / failure
function push(stack, element) {
  if (stack.topIndex >= stack.maxSize - 1) {
    return 0;
  }
  stack.topIndex++;
  stack.elements[stack.topIndex] = element;
  return 1;
}

/** * accesses the top element *@param {*} Stack stack *@returns The top element */
function top(stack) {
  return stack.elements[stack.topIndex];
}

/** * back to the top of the stack instead of deleting the original data@param {*} Stack stack *@returns 1 - success; 0 - * / failure
function pop(stack) {
  if (stack.topIndex < 0) {
    return 0;
  }
  stack.topIndex--;
  return 1;
}

// Check whether the stack is empty
function empty(stack) {
  if (stack.topIndex < 0) {
    return 1;
  }
  return 0;
}
Copy the code

As you can see, the basic stack algorithm is fairly simple, so let’s do two problems to reinforce it.

Common algorithms

Use a stack to implement a simple calculator

Source: LeetCode Description

Given an arithmetic expression (excluding parentheses) containing a positive integer, plus (+), minus (-), multiply (), and divide (/), compute the result. The expression contains only the non-negative integer +, -, / operators and Spaces. Integer division preserves only integer parts.

Implementing a simple calculator is the best exercise for stack structure. This problem is solved using two stacks, one for numbers and one for operators.

// The auxiliary function performs the calculation of two numbers
function operate(theta, a, b) {
  if (theta == "+") {
    return a + b;
  } else if (theta === "*") {
    return a * b;
  } else if (theta === "/") {
    return Math.floor(a / b);
  } else if (theta === The '-') {
    return a - b;
  }
  return ' ';
}

// Pull two numbers from the top of the stack to calculate
function calc(numberStack, operatorStack) {
  let a = top(numberStack);
  pop(numberStack);
  let b = top(numberStack);
  pop(numberStack);
  // Pay attention to the order of a and B as they are removed from the top of the stack in reverse order
  push(numberStack, operate(top(operatorStack), b, a));
  pop(operatorStack);
}

/** * Compares the priority of two operators *@param {*} A operator *@param {*} B operator *@returns Returns true */ if a has a higher priority than B
function precede(a, b) {
  if (a === "+" || a === "-") {
    return false;
  }
  if (a === "*" || a === "/") {
    return b === "+" || b === "-";
  }
  return false;
}

/** * uses a stack to implement a simple calculator that contains only addition, subtraction, multiplication, and division *@param {string} s
 * @return {number}* /
function calculate(s) {
  // Initialize two stacks
  let numberStack = new Stack(100);
  let operatorStack = new Stack(100);
  // Process by reading each character in turn from s
  let count = 0;
  while (count < s.length) {
    if (s[count] === ' ') {
      count++;
      continue;
    }
    // Use isNaN to determine if a character is a number
    if (!isNaN(s[count])) {
      // Convert the number to a number stack
      push(numberStack, +s[count]);
      count++;
    } else {
      // If the stack is empty or the current operator has a higher priority than the top-stack operator, the stack is pushed
      if (empty(operatorStack) || precede(s[count], top(operatorStack))) {
        push(operatorStack, s[count]);
        count++;
      } else{ calc(numberStack, operatorStack); }}}// The above logic is mainly to process the expression (push), at this point, we need to continue to process the calculation in both stacks
  while(! empty(operatorStack)) { calc(numberStack, operatorStack); }// You can return top(numberStack) directly, but remember that JS will automatically reclaim memory for both stacks
  const result = top(numberStack);
  numberStack = null;
  operatorStack = null;
  return result;
}

calculate('2 + 4 * 7')
Copy the code

Check for valid parentheses

Given a string containing only parentheses, determine whether the parentheses in the string are valid pairs. Such as: “() ()”, “{} ()”, “{() ()]}” can be effective matching, but: “[} {]” this can’t effective matching.

The standard way to solve this problem is to use a stack structure, and finally, if the stack is empty, you have valid parentheses.

// Define a pair of close parentheses that will return "[" to compare with the top element of the stack, for example, if the parenthesis "]" is reached
function pairs(a) {
  if (a == "}") return "{";
  if (a == "]") return "[";
  if (a == ")") return "(";
  return 0;
}

/** * checks for valid parentheses *@param {string} s
 * @return {boolean}* /
function isValid(s) {
  // Initializes a stack space
  let stack = new Stack(100);
  let count = 0;
  // Process strings in turn
  while (count < s.length) {
    // From the second start the logic will enter, compare the top of the stack with the next character, if the match is correct
    // pop the top element
    if (top(stack) === pairs(s[count])) {
      pop(stack);
    } else {
      // Otherwise keep adding symbols to the stack
      push(stack, s[count]);
    }
    count++;
  }
  // Empty stack indicates valid parentheses
  if (empty(stack)) return true;
  return false;
}
Copy the code