One, foreword

1.1. What is a data structure?

A data structure is a way of storing and organizing data in a computer.

For example: library management, how to place books can not only put a lot of books, but also convenient access?

There are two main issues to consider:

  • Operation 1: How to insert new books?
  • Operation 2: How to find a specific book?

Common data structures:

  • Array (Aarray)
  • The Stack (Stack)
  • Linked Lists
  • Graph (Graph)
  • Hash table
  • Queue
  • A Tree (Tree)
  • Heap (Heap)

Note: Data structures and algorithms are language-independent, and common programming languages make direct or indirect use of the above common data structures.

1.2. What is an algorithm?

Definition of an Algorithm

  • A finite set of instructions, the description of each instruction independent of language;
  • Receive some input (in some cases no input is required);
  • Generate input;
  • Must terminate after finite steps;

Algorithms are commonly known as problem solving/step logic. The realization of data structure is inseparable from algorithm.

Ii. Stack Structure

2.1. Introduction

An array is a linear structure, and you can insert and delete elements anywhere in the array. Stacks and queues are common constrained linear structures. As shown below:

The stack is characterized byFirst in, last out, last in, first out(LIFO: Last in first out).

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 keeps calling itself and pushing the same function onto the Stack, causing Stack Overfloat. For example, if function A is A recursive function, it keeps calling itself and pushing the same function onto the Stack.

3. Exercise: 题目 : 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:

  • Answer: 65 into the stack, 5 out of the stack, 4 into the stack out of the stack, 3 into the stack out of the stack, 6 out of the stack, 21 into the stack, 1 out of the stack, 2 out of the stack (the overall stack order 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, and then 5 to the stack instead of 6.
  • 65432 in, 2 out, 3 out, 4 out, 1 in and out, 5 out, 6 out. In line with the push order;

Common stack operations:

  • Push (Element) : adds 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 true if there are no elements in the stack, false otherwise;
  • Size () : Returns the number of elements in the stack. This method is similar to the length property of an array;
  • ToString () : Returns the contents of the stack as a string.

2.2. Encapsulate the stack class

The ES6 class usage is also available here
function Stack() {
    // Attributes in the stack
    this.items = []

    // Stack related operations
    // 1.push(): pushes elements onto the stack
    // Method 1 (not recommended) : Add methods to objects. Other objects cannot be reused
    // this.push = () => {
    // }

    // Method 2 (recommended) : Add a method to the Stack class to reuse multiple objects
    Stack.prototype.push = function(element) {
        // Use the array item push method to implement the Stack class pop method
        this.items.push(element)
    }

    // 2.pop(): fetching elements from the stack
    Stack.prototype.pop = () = > {
        // Use the pop method of array item to implement the pop method of Stack class
        return this.items.pop()
    }

    // 3.peek(): Look at the top element of the stack
    Stack.prototype.peek = () = > {
        return this.items[this.items.length - 1]}// 4.isEmpty(): checks whether the stack isEmpty
    Stack.prototype.isEmpty = () = > {
        return this.items.length == 0
    }

    // 5.size(): Gets the number of elements in the stack
    Stack.prototype.size = () = > {
        return this.items.length
    }

    // 6.toString(): outputs stack data as a string
    Stack.prototype.toString = () = > {
        // Desired output format: 20, 10, 12, 8, 7
        let resultString = ' '
        for (let i of this.items) {
            resultString += i + ' '
        }
        return resultString
    }
}
Copy the code

Test code:

// Stack usage
let s = new Stack()
s.push(20)
s.push(10)
s.push(100)
s.push(77)
console.log(s.pop());
console.log(s.peek());
console.log(s.isEmpty());
console.log(s.size());
console.log(s.toString());					
Copy the code

Test results:

Simple application of stack structure:

Use the characteristics of the stack structure to encapsulate the decimal to binary function:

// Simple application:
// Encapsulate function: convert decimal to binary
let dec2bin = (decNumber) = > {
    //1. Define a stack object to hold the remainder
    var stack = new Stack();

    // 2
    while (decNumber > 0) {
        Get the remainder and put it on the stack
        stack.push(decNumber % 2);
        // 2.2. Get the divisible result as the number for the next operation (floor: round down)
        decNumber = Math.floor(decNumber / 2);
    }

    // 3. Fetch 0 and 1 from stack
    let binaryString = "";
    let a = stack.items.length;
    while(stack.items.length ! =0) {
        binaryString += stack.pop();
    }
    return binaryString;
};
// Test the code
console.log(dec2bin(10));
console.log(dec2bin(100));
console.log(dec2bin(1000));				
Copy the code

Test results: