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?

1.2. Common data structures

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

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:

LIFO: 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 (because the function has not finished executing and will not push the function off the Stack), and pushes the same function A onto the Stack repeatedly, finally causing Stack Overflow.

2.1 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 Encapsulating the stack class

Function encapsulation:

Function Stack(){this.items =[]; // 1. // this.push = () => {//} // Add a method to the Stack class, Function (element) {this.items. Push (element)} // Prototype pop = () => {return this.items. Pop ()} return this.items. Pop () Prototype. Peek = () => {return this.items[this.items.length - 1]} // 4.isEmpty(): check if the Stack isEmpty Stack.prototype.isEmpty = () => {this.length = this.length(); Return this.items. Length == 0} // 5.size(): Retrievesthe number of elements in the Stack stack.prototype. size = () => { Prototype. ToString = () => {return this.items.length} // 6. ToString (): toString() => { 20 10 12 8 7 let resultString = '' for (let i of this.items){ resultString += i + ' ' } return resultString } }Copy the code

The test code

// let s = new Stack() s.puff (20) s.puff (10) s.puff (100) s.puff (77) console.log(s) //65 console.log(s.pop()); //68 console.log(s.pop()); //69 console.log(s.peek()); //71 console.log(s.isEmpty()); //72 console.log(s.size()); //74 console.log(s.toString());Copy the code

Test results:

Simple application of stack structure:

Dec2bin = decNumber => {//1; //1; //1; Var stack = new stack () // 2 Loop while(decNumber > 0){// 2.1. Get the remainder and put it on stack. Push (decNumber % 2) // 2.2. DecNumber = math.floor (decNumber / 2)} // 3. Let binaryString = ''; let a = stack.items.length while(stack.items.length ! = 0){ binaryString += stack.pop(); } return binaryString; } // Test code console.log(dec2bin(10)); //103 console.log(dec2bin(100)); //104 console.log(dec2bin(1000));Copy the code

Test results: