The javascript language evolves every year, with a new version released almost every year since 2015. We call it ECMAScript

ECMAScript is a scripting language standardized by Ecma International (formerly the European Computer Manufacturers Association) through ECMA-262. This language is widely used on the World Wide Web and is often referred to as JavaScript or JScript, so it can be understood as a standard for JavaScript, but the latter two are actually implementations and extensions of the ECMA-262 standard.

The relationship between ECMAScript and javascript: the former is a specification of the latter, and the latter is an implementation of the former (also called JScript and Actionsrcipt).

Es5 and ES6 refer to ECMAScript 5 and ECMAScript 6 because

Prior to ES6, there was no block-level scope; As long as the scope of this variable can be accessed; Declare a variable, the JS engine will improve the declaration of the variable.

A variable declared by let is only valid in the block-level scope. It is not valid outside the block-level scope and is destroyed after the function is executed. (var is a global variable.) Const can only be declared as a constant and cannot be changed.

Let and const have several characteristics:

Let and const are local variables and are valid only in their respective scope. There is no variable promotion: declared variables can be used only after they are declared. Declaration variables form a closed scope from the beginning. If you use the variable before declaring it, an error will be reported

Javascript has a built-in object called the Arguments object, which is an array containing the arguments passed to a function when it is called. You can dynamically fetch and use the arguments even if you don’t know their names

ES6 function extensions (function parameter defaults)

In traditional javascript, there is no concept of a class, but in ES6 there is a full understanding of the class class in ES6

TypeScript is a free and open source programming language developed by Microsoft. It is a superset of JavaScript, and essentially adds optional static typing and class-based object-oriented programming to the language.

TypeScript offers the latest and evolving JavaScript features, including those from ECMAScript 2015 and future proposals, such as asynchronous functionality and Decorators, to help build robust components. The following diagram shows TypeScript in relation to ES5, ES2015, and ES2016:

Arrays are the simplest in-memory data structures that store a series of values of the same data type (javascript arrays can hold different types of values, but try to avoid this). Arrays are designed to simplify recording multiple data and multi-dimensional arrays

Insert element at the end of array:

Use push method numbers. Push (11);

Native method: numbers[numbers. Length] = 10; In Javascript, arrays are mutable objects that grow dynamically if you want to add elements, so simply assign to the last empty space in the array

2. Insert element at the beginning of array:

Numbers. Unshift (10);

The native method is to create a new array, iterate over the original array, assign the original array to the next bit, copy it to the new array, assign the inserted number to the first position in the new array, and return the new array,

A two-dimensional array is essentially an array of arrays as array elements, that is, “arrays of arrays”, the type specifier array name [constant expression][constant expression]. A two-dimensional array is also called a matrix, and a matrix with the same number of rows and columns is called a square matrix. Symmetric matrix A [I][j] = a[j][I], diagonal matrix: n-order square matrix with zero elements outside the main diagonal

var arr = [[1.2], ['a'.'b']].console.log(arr[1] [0]); // the element in row 1 of column 2 of a
Copy the code

Similarly, a multidimensional array is basically adding quadrants to a two-dimensional array

Because javascript differs from languages like C and Java, javascript arrays are not strongly typed. You can store any type of data so how do you make javascript arrays store a single type of data? So this is the type array. Specific syntax:

let myArray = new TypedArray(length)
// In real use, replace TypedArray with the type required in the list below
Copy the code

In this chapter, we will learn how to create a stack using arrays and objects in javascript

Creating a stack with arrays in javascript involves 7 steps:

Add elements to the stack using push (only from the top of the stack). Remove elements from the stack using pop (remove elements from the top of the stack). Check if the stack isEmpty (method peek) 5. Check if the stack isEmpty (method isEmpty) return true if the stack isEmpty and false otherwise 6. 7. You can start using the stack class after the above six steps, stack has nearly the characteristics of the stack.

Code implementation:

// Create an array-based unit stack
class stack{
	constructor{
		this.items = []; }}// Add elements to the stack using the push method
push () {
	this.items.push();
}
// Use the pop method to remove elements from the top of the stack
pop(){
	reyurn this.items.pop();
}
// After the above two steps, the basic implementation of the stack principle of first in last out
// Check the top element (length-1)
peek{
	return this.items{this.items.length - 1};
}
// use isEmpty to check if the stack isEmptyIsEmpty () {return this.items.length === 0;
}
// After completing the above steps, use the clear method to clear all elements in the stackClear () {return this.items.length;
}
/ / at this point. The stack is completeYou can use the stack method to operate on the stackCopy the code

After we create a stack, other colleagues may also want to use it. We want to protect the elements inside the data structure. Only the elements we expose are allowed to change.

The implementation class using Symbol specifies in ES6 that symbol is immutable and can be used as an attribute of an object

Code implementation:

cosnt_items = symbol('stacItems');
class  stack {
	constoructor () {
		this[_items] = [];
	}
	// stack method
}
Copy the code

The following string contains parentheses. Write a function to check whether the parentheses in the string are valid

SDF (ds) of (ew) (we re RWQW) QWRWQ legal (sd (qwqe), sd (sd)) legal sd () () () (sd) (dw) is illegalCopy the code

If you use an array to store these parentheses, and then try to find a way to cancel one to one, it seems feasible. But we can’t tell which open parenthesis corresponds to which close parenthesis. It’s a little harder to think about this in terms of arrays. Now, we’re going to use a stack to solve this problem and when we see an open bracket, we’re going to push the closing bracket onto the stack and when we see a close bracket, we’re going to see if the stack is empty, and if it’s empty then there’s no open bracket that corresponds to it, so string parentheses are not valid. If the stack is not empty, the top element is removed and the parentheses cancel out. When the for loop ends, if the stack is empty, all the left and right parentheses cancel out, and if there are elements on the stack, the left and right parentheses are missing, and the string parentheses are invalid.

Code implementation:

function is_leagl_brackets(string){
	var stack = new Stack();
	for (var i = 0; i<string.length; i++) {var item = string[i];
		// do parentheses to the stack
		if(item == '('){
			stack.push(item)
		}else if (item == ') ') {// See if the stack is empty
			if(stack.isEmpty()){
				return false
			}else {
				stack.pop() // Pop open parenthesis}}}// If the stack is empty, string parentheses are valid
	return stack.isEmpty()
}
console.log(is_leagl_brackets('sdf(ds(ew(we)re)rwqw)qwrwq')) // true
console.log(is_leagl_brackets('(sd(qwqe)sd(sd))')) // true
console.log(is_leagl_brackets('()()sd()(sd()dw))(')) // false
Copy the code

1. Concept of a double-endian queue: A double-endian queue is a special queue that allows us to add and remove elements from both the front and back end of the queue

Deque common application in computer is to store a series of undo operation, the user after the cancellation, the operation will be stored in a deque, can click the undo and vexed withdrawn, because the deque and to abide by the principle of first in first out and last in first out, say that he is to put the queue and stack in combination with a data structure.

2. Create a queue with two ends:

Constructor () {this.count = 0; this.lowestCount = 0; this.items = {}; }

AddFront (element) {if (this.isempty ()) {this.addback (element); } else if (this.lowestCount > 0) {// if (this.lowestCount > 0); this.items[this.lowestCount] = element; } else { for (let i = this.count; i > 0; I -) {this.items[I] = this.items[i-1]; } this.count++; this.items[0] = element; }}

AddBack (element) {this.items[this.count] = element; this.count++; }

RemoveFront () {if (this.isempty ()) {return undefined; } const result = this.items[this.lowestCount]; delete this.items[this.lowestCount]; this.lowestCount++; return result; }

RemoveBack () {if (this.isempty ()) {return undefined; } this. Count -; const result = this.items[this.count]; delete this.items[this.count]; return result; }

PeekFront () {if (this.isempty ()) {return undefined; } return this.items[this.lowestCount]; }

PeekBack () {if (this.isempty ()) {return undefined; } return this.items[this.count – 1]; }

Situation: The children circle the city and pass the flowers to the people around them. At a certain point, they stop and the flowers are in the hands of the people around them. Repeat the procedure, and the last person left is the winner. Code implementation:

function hotPotato(elementsList, num) {  const queue = new Queue();  const elimitatedList = [];
  for (let i = 0; i < elementsList.length; i++) {    queue.enqueue(elementsList[i]);  }
  while (queue.size() > 1) {    for (let i = 0; i < num; i++) {      queue.enqueue(queue.dequeue());    }    elimitatedList.push(queue.dequeue());  }
  return {    eliminated: elimitatedList,    winner: queue.dequeue() }; }Copy the code

function LinkedList() {
    var Node = function (val) {// New element construction
        this.val = val;
        this.next = null;
    };
    var length = 0;
    var head = null;
 
    this.append = function (val) {
        var node = newNode(val);// Construct a new element node
        var current;
        if (head === null) {// If the head node is null, the current node is the head node
            head = node;
        } else{ current = head;while(current.next) {// Loop through until next is null and the current node is the last nodecurrent = current.next; } current.next = node;// Point the tail node to the new element, which acts as the tail node} length++;// Update the list length
    };
    this.removeAt = function (position) {
        if (position > -1 && position < length) {
            var current = head;
            var index = 0;
            var previous;
            if (position == 0) {
                head = current.next;
            } else {
                while (index++ < position) {
                    previous = current;
                    current = current.next;
                }
                previous.next = current.next;
            }
            length--;
            return current.val;
        } else {
            return null; }};this.insert = function (position, val) {
        if (position > -1&& position <= length) {// Check the boundary
            var node = newNode(val); current = head;var index = 0;
            var previous;
            if (position == 0) {// As the head node, next of the new node points to the original head node.node.next = current; head = node;// The new node is assigned to the head node
            } else {
                while(index++ < position) { previous = current; current = current.next; }// Get the current node where the current position is located and the previous nodeprevious.next = node;// Next of the previous node points to the new node and the new node points to the current node
                node.next = current;
            }
            length++;
            return true;
        } else {
            return false; }};this.toString = function () {
        var string = head.val;
        var current = head.next;        
        while (current) {
            string += ', ' + current.val;
            current = current.next;
        }
        return string;
    };
    this.indexOf = function (val) {
        var current = head;
        var index = -1;
        while (current) {
            if (val === current.val) { // Start traversal from the beginning node
                return index;
            }
            index++;
            current = current.next;
        }
        return -1;
    };
    this.getLength = function () {
        return length;
    }
    this.getHead = function () {
        returnhead; }}// Create a linked list
var li = new LinkedList();
li.append(1);
li.append(2);
li.append(4);
li.append(4);
li.append(5);
li.insert(2.3);
li.insert(2.3);
console.log(li.toString())  / / 1,2,3,3,4,4,5
console.log(li.getHead())   / / 1 - > 2 - > 3 - > 3 - > 4 - > 4 - > 5
Copy the code

How to create a linked list in JS

Each node of a bidirectional linked list needs to join the previous node and the next node, so we need to define two pointer fields, one pointing to the previous node and the next node.

In a bidirectional list, the prev pointer to the head node points to the tail node, and the next pointer to the tail node points to the head node.



Implementation of the loop list:

Create a bidirectional circular linked list

function DoublyCircularLinkedList(){
	function Node(element){
		this.element=element
		this.next=null
		this.prev=null
	}
	let length=0
	let head=null
	let tail=null
}
Copy the code

2. Insert a new node at the tail

	this.append=function(element){
		let node = new Node(element)
		let current // The current node
		let previous // The previous node
		if(! head){ head=node tail=node head.prev=tail tail.next=head }else{
			current=head
			while(current.next ! == head){ previous = current current = current.next } current.next=node node.next=head node.prev=current } length++return true
	}
Copy the code

3. Insert nodes at any positions

	// Insert a node at any position
	this.insert=function(position,element){
		if(position > 0 && position <= length){
			let node = new Node(element)
			let index = 0
			let current = head
			let previous
			if(position === 0) {// Insert the header
				if(! head){ node.next=node node.prev=node head=node tail=node }else{
					current.prev=node
					node.next=current
				}
			}else if(position === length){ // Insert into the tail
				current=tail
				current.next=node
				node.prev=current
				tail=node
				node.next=head
			}else{
				while(index++ < position){
					previous=current
					current=current.next
				}
				current.prev=node
				node.next=current
				previous.next=node
				node.prev=previous
			}
			length++
			return true
		}else{
			return false}}Copy the code

4. Delete nodes based on their locations

this.removeAt = function(position){ 
	    if(position > -1 && position < length){   
	      let current = head
	      let index = 0
	      let previous; 
	      if(position === 0){   
	        current.next.previous = tail
	        head = current.next;   
	      }else if(position === length - 1){   
	        current = tail;  
	        current.prev.next = head
	        head.prev = current.prev
	        tail = current.prev
	      }else{ 
	        while(index++ < position){ 
	          previous = current
	          current = current.next
	        } 
	        previous.next = current.next
	        current.next.prev = previous
	      } 
	      length--
	      return true
	    }else{ 
	      return false}}Copy the code

5. Delete the node based on the node value

	this.remove = function(element){ 
	  let current = head
	  let  previous
	  let  indexCheck = 0  
	  while(current && indexCheck < length){ 
		if(current.element === element){ 
		  if(indexCheck === 0){ 
			current.next.prev = tail; 
			head = current.next
		  }else{ 
			current.next.prev = previous
			previous.next = current.next
		  } 
		  length--
		  return true
		} 	    
		previous = current
		current = current.next
		indexCheck++
	  }    
	  return false
	}
Copy the code

JAVASCRIPT – Stack functionality via linked lists

First write the sixth chapter, after I review in writing, there are a lot of places in the book I did not fully understand, so in writing this article introduced a lot of related blog, blog looks easier to understand the code word is not easy, click a praise in go!! I wish you a happy May Day!!

Understanding javascript Data Structures and Algorithms (Middle)

Learn javascript Data Structures and Algorithms: an easy-to-understand primer on TypeScript

JavaScript implements bidirectional linked lists

Review of JavaScript data structures (Part 5-4) bidirectional circular linked lists

Use javaScript to implement an ordered linked list