This album is based on the video “JavaScript data structures and Algorithms”, the author of this article has the notes, source code, test environment hosted on GitHub, welcome students Star and Fork.

It is recommended that you learn the structure of the directory in order, from the simple to the deep, step by step, easy to figure out the data structure and algorithm.

An array is a linear structure, and you can insert and delete elements anywhere in the array. Sometimes, however, we have to limit this arbitrariness in order to implement certain functions. Stacks and queues are common constrained linear structures.

What is a stack

A stack, “stack,” is a linear table with limited operations:

  • LIFO (Last in First Out)Represents the last element to enter, the first to pop out of the stack space. Similar to the automatic meal tray, the last tray, often take out the first use.
  • The limitation is that only one end of the table is allowed for insert and delete operations. This end is called the top of the stack, and the other end is called the bottom of the stack.
  • Adding a new element to a stack is also called pushing, pushing, or pushing. It is done by placing the new element on top of the top element to make it the new top element.
  • To remove an element from a stack is also called to stack or unstack. It is to remove the top element from the stack so that the adjacent element becomes the new top element.

As shown below:

The characteristics of the stack: advanced after out, back in first out.

The stack structure in the program

  • Function call stack: A(B(C(D()))) : A function calls B, B calls C, C calls D; A is pushed as it executes, then B is pushed as it executes, and functions C and D are pushed as well. So the current stack order is: A->B->C->D (top of stack); D->C->B->A;

  • Recursion: Why does recursion without stop conditions cause stack overflow? For example, if function A is A recursive function, it will call itself repeatedly (because the function has not finished executing and will not be ejected from the stack), and it will Queue Overfloat by pushing the same function A onto the stack.

practice

There are 6 elements, 6, 5, 4, 3, 2, 1, which of the following is not a valid order to exit the stack?

  • A: (√)
  • B: 4. 3.
  • C: 3 4 5 5 1 (×)
  • D: 2 3 4 1 5 6 (√)

Instead of all of them being pushed at once, they are pushed in and out in the order of 6 -> 5 -> 4 -> 3 -> 2 -> 1.

Resolution:

  • A: 65 in, 5 out, 4 in and out, 3 in and out, 6 out, 21 in, 1 out, 2 out (the overall order of the stack is 654321).
  • B: 654 in, 4 out, 5 out, 3 in and out, 2 in and out, 1 in and out, 6 out (the overall order of loading is 654321).
  • C) 6543 to the stack, 3 to the stack, 4 to the stack, then 5 to the stack instead of 6
  • 65432 in, 2 out, 3 out, 4 out, 1 in and out, 5 out, 6 out. It fits the order of pushing.

Stack structure implementation

Common operations on the stack

  • push()Add a new element to the top of the stack.
  • pop()Removes the element at the top of the stack and returns the removed element.
  • peek()Returns the element at the top of the stack without making any changes to the stack (this method does not remove the element at the top of the stack, only returns it).
  • isEmpty()Returns if there are no elements in the stacktrueOtherwise returnfalse.
  • size()Returns the number of elements in the stack. The method and the arraylengthProperties are similar.
  • toString()Returns the contents of the stack structure as a string.

The JavaScript code implements the stack structure

// Stack encapsulation
class Map {

  constructor() {
    this.items = [];
  }

  // push(item) adds an element to the stack
  push(item) {
    this.items.push(item);
  }

  // pop() removes an element from the stack and returns the removed element
  pop() {
    return this.items.pop();
  }

  // peek() looks at the top element of the stack
  peek() {
    return this.items[this.items.length - 1];
  }

  // isEmpty() checks whether the stack isEmpty
  isEmpty() {
    return this.items.length === 0;
  }

  // size() gets the number of elements in the stack
  size() {
    return this.items.length;
  }

  // toString() returns the stack element data as a string
  toString() {
    let result = ' ';
    for (let item of this.items) {
      result += item + ' ';
    }
    returnresult; }}Copy the code

Test the stack structure of the package

/ / push () test
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.items); / / -- > [1, 2, 3]

/ / pop () test
console.log(stack.pop()); / / -- > 3

/ / peek () test
console.log(stack.peek()); / / -- > 2

/ / isEmpty () test
console.log(stack.isEmpty()); //--> false

/ / the size () test
console.log(stack.size()); / / -- > 2

/ / the toString () test
console.log(stack.toString()); / / -- > 1. 2
Copy the code

Simple application of stack structure

Using the characteristics of the stack structure to encapsulate the realization of decimal conversion to binary method.

Code implementation

function dec2bin(dec) {
  // new a Map, save the remainder
  const stack = new Map(a);// Use the while loop when the number of loops is uncertain
  while (dec > 0) {
    // Divide by two
    stack.push(dec % 2); // Get the remainder and put it on the stack
    dec = Math.floor(dec / 2); // Divide the divisor by two and round down
  }

  let binaryString = ' ';
  // Constantly fetching elements (0 or 1) from the stack and concatenating them together.
  while(! stack.isEmpty()) { binaryString += stack.pop(); }return binaryString;
}
Copy the code

test

/ / dec2bin () test
console.log(dec2bin(100)); / / -- > 1100100
console.log(dec2bin(88)); / / -- > 1011000
Copy the code

Album series

  • Learn JavaScript data structures and algorithms from 0
  • Learn JavaScript data structures and algorithms from 0 (2) arrays