Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Recently learned some JS data structure and algorithm knowledge, in this share a wave. This article mainly introduces the contents of the stack structure, there are shortcomings or any suggestions, welcome to give feedback ~

A stack is a common data structure. It is a restricted linear table (a finite sequence of N data elements with the same properties). Unlike an array, which can insert or delete data at any location, the stack only allows insertion or deletion at one end, the top of the stack, following the last in first out rule. LIFO for short) principle, advanced stack (on/off) after stack (off/pop).

Call Stack

The stack structure is used by the JS engine to track the process of function execution, which is called the stack. When multiple functions are called in the execution environment, the call stack keeps track of which function is being executed and which function is being called by that function. For example:

function a() {
  console.log('Function A starts executing')
  b()
  console.log('Function A completes execution')}function b() {
  console.log('Function B is called and executed.')
}

a()
Copy the code

When the code above runs, the declaration of the function is not placed on the call stack at first until line 11, when function A is called, and the function is calleda()Put it on the call stack. Then I start executing the body of function A, and when I get to line 3, I find that function B is called, so I push function B. After executing function B, push function B off the stack. Go back to function A and continue, and then push function A off the stack. The illustration is as follows:

encapsulation

Here is a stack structure wrapped in an array constructor:

function Stack() {
  // Prepare an array
  this.items = []
  
  / / into the stack
  Stack.prototype.push = function (item) {
    this.items.push(item)
  }
  
  / / out of the stack
  Stack.prototype.pop = function () {
    return this.items.pop()
  }
  
  // Check whether the stack is empty
  Stack.prototype.isEmpty = function () {
    return this.items.length === 0}}Copy the code

Function () {this.push = function() {this.push = function() {this.push = function() {} The definition of the prototype is that all instances share the push method.

case

Convert decimal to binary. The principle is that a quotient and remainder can be obtained by removing the decimal number and 2. The remainder is pushed onto the stack and rounded down to remove and 2 until the resulting quotient is rounded down to 0. At this point, the remainder of the stack is removed from the stack and the value of the string assembled is the converted binary value:

function decimalToBinary(num) {
  const stack = new Stack()
  while (num > 0) {
    // Put the remainder on the stack
    stack.push(num % 2)
    // reassign num
    num = Math.floor(num / 2)}// Fetch each item on the stack in turn to get the conversion result
  let result = ' '
  while(! stack.isEmpty()) { result += stack.pop() }return result
}
Copy the code