This is the 11th day of my participation in the August Wenwen Challenge.More challenges in August

preface

The data structure of arrays and stacks will be reviewed here. The data structure of arrays and stacks will be reviewed here

A, arrays,

Almost all programming languages natively support array types because arrays are the simplest in-memory data structures. Tip: The first version of JavaScript did not support arrays. An array stores a series of values of the same data type.



Although in JavaScript, you can also store different types of values in arraysBut we need to follow best practices and avoid doing this.

1.1 Creating and initializing arrays

1.1.2 Using the new keyword

let arr1 = new Array(); // Simply declare and initialize an Array let arr2 = new Array(5); Let arr3 = new Array(1,2,3,4,5); // Pass an array element as an argument to its constructorCopy the code

However, using new is not the best way to create an array. If you want to create an array in JavaScript, just use brackets ([]).

1.1.3 Creating arrays using literals

let arr1 = []; Let arr2 = [1, 2, 3, 4, 5]Copy the code

1.2 Accessing elements and iterating through arrays

To access an element at a particular position, simply pass the numeric position in brackets.

1.2.1 Loop through the array and print elements

for(let i = 0; i < arr2.length; i++){ console.log(i) }Copy the code

1.2.2 Find the first 20 Fibonacci numbers

const fibonacci = []; fibonacci[1] = 1; fibonacci[2] = 1; For (let I = 3; i < 20; I ++){Fibonacci [I] = Fibonacci [i-1] + Fibonacci [i-2]} for(let I = 1; i < fibonacci.length; i++){ console.log(fibonacci[i]) }Copy the code

You can copy the above code directly, then press F12, then paste the code, hit Enter and the result is displayed.

1.3 Adding elements to an array

Adding and removing elements to an array is also easy but sometimes tricky.

Let newArr =,1,2,3,4,5 [0]Copy the code

1.3.1 Inserting elements at the end of an array

Add an element (such as 6) to newArr

newArr[newArr.length]=6
Copy the code

In JavaScript, an array is an object that can be modified! If you add elements, it grows dynamically. In other languages like C and Java, we determine the size of an array, and to add new elements we create a new array! You can add any element using the push method

newArr.push(6); NewArr. Push (6, 7)Copy the code

1.3.2 Inserting elements at the beginning of an array

Start by vacating the first element in the array and move all the elements one to the right. Assign the value we want to the first position

Array.prototype.insertFirstPosition = function(value){ for(let i = this.length; i >= 0; i--){ this[i]=this[i-1]; } this[0] = value; };Copy the code

Using the unshift() method the logic behind this method is the same as the behavior of the insertFirstPosition method

newArr.unshift(-1)
newArr.unshift(-2,-1)
Copy the code

1.4 Deleting Elements

1.4.1 Removing elements from the end of an array

newArr.pop(5); NewArr. Pop (4, 5);Copy the code

Arrays can be used to simulate stacks through push and POP methods

1.4.2 Removing an element from the beginning of an array

newArr.shift(0);
Copy the code

1.5 Add or remove elements at any location

Using the splice method, you can delete a specified number of elements at that location simply by specifying a location/index. The first argument accepted by the splice method represents the index value of the element that you want to delete or insert. The second argument is the number of elements removed (or added if it is 0). The third argument, after that, is the value to be added to the array.

1.6 Two-dimensional and multidimensional arrays

JavaScript supports one-dimensional arrays and does not support matrices, but we can implement matrices or any multidimensional array by covering arrays with arrays

let averageTemp = []; AverageTemp [0] = [1, 2, 3]. AverageTemp [1] = (4 and 6);Copy the code

1.6.1 Iterating over the elements of a two-dimensional array

Use a nested for loop to handle this.

function printMatrix(myMatrix){ for(let i = 0; i<myMatrix.length; i++){ for(let j = 0; j<myMatrix[i].length; j++){ console.table(myMatrix[i][j]) } } }Copy the code

1.7 JavaScript array method reference

1.7.1 Array Merging

const zero = 0; Const arr1 = [1, 2, 3]; Const arr2 = (4 and 6); let newArr = arr1.concat(zero,arr1,arr2); The console. The log (newArr) / / the output:,2,3,0,4,5,6 [1]Copy the code

The concat method can pass arrays, objects, or elements to an array. The array concatenates the specified array in the order of the arguments passed in to the method.

1.7.2 Iterator functions

We can handle this with loop statements, such as for statements. JavaScript has a number of built-in iteration methods available for arrays. Example: We need a function and an array: the function returns true if the elements in the array are divisible by 2, false otherwise.

function isEven(x){ console.log(x); return x % 2 === 0 ? Const isEven = x=>x%2 === 0; Let newArr =,4,5,6,8 [2]Copy the code

1. Use the every method to iterate

The every method iterates over each element in the array until it returns false

newArr.every(isEven)
Copy the code

The third element of newArr is odd, isEven returns false, and every completes

2. Iterate with some

It does the opposite of every, iterating through each element of the array until the function returns true.

newArr.some(isEven)
Copy the code

3. Iterate with forEach

If you want to iterate over the entire array, you can use the forEach method. It is the same as using the for loop.

4. Use the Map and filter methods

JavaScript also has two iterative methods that return new arrays. The first is the map method.

const myMap = newArr.map(isEven);
Copy the code

The values in the array myMap is true, true, false, true, true]. It holds the result of the isEven function passed to the map method. So it’s easy to know if an element is even. The second is the filter method. The new array it returns consists of elements that make the function return true.

Const myFilter = newarr. filter(isEven) output:[2,4,6,8]Copy the code

5. Use the Reduce method

The Reduce method accepts a function with four parameters: previousValue, currentValue, index, and array are optional parameters. Because index and array are optional parameters, they are sometimes not passed. This function returns a value that will be added to the accumulator that will be returned when the reduce method stops executing. This is useful if you want to sum all the elements in an array.

newArr.reduce((a,b)=>a+b);
Copy the code

These three methods (map.filter,reduce) are the foundation of JavaScript functional programming

1.7.3 Adding array methods in ES6

In addition to these new methods, there is another way to use… The new practice of iterating through an array with an of loop.

1. Use the for… Of loop iteration

for(const n of newArr){
    console.log(n%2 === 0 ? true : false)
}
Copy the code

2. Use @@iterator

ES6 also adds an @@iterator attribute to the Array class, which needs to be accessed through symbol. iterator.

let iterator = newArr[Symbol.iterator](); console.log(iterator.next().value); //2 console.log(iterator.next().value); / / 4Copy the code

iterator = newArr[Symbol.iterator]();
for（const n of iterator）{
    console.log(n)
}
Copy the code

3. Array entries, keys, and values methods

ES6 also adds three ways to get iterators from arrays. Entries methods The Entries method returns an @@iterator containing key-value pairs

let myEntries = newArr.entries(); The console. The log (myEntries. Next () value) / / [0, 2] the console. The log (myEntries. The next (). The value) / / [1, 4]Copy the code

When working with data structures such as collections, dictionaries, hash tables, etc., it is useful to be able to retrieve key values. This feature will come into play later. The keys method returns an @@iterator containing an array index

const myKeys = newArr.keys();
console.log(myKeys.next())//{value:0,done:false}
console.log(myKeys.next())//{value:1,done:false}
Copy the code

Once there are no iterable values, mykeys.next () returns an object with undefined value and true done. If the done attribute is false, it means there are still iterable values. The values method returns an @@iterator that contains the values of the array.

const myValues = newArr.values();
console.log(myValues.next());
console.log(myValues.next());
Copy the code

4. Use the array. from method

The array. from method creates a new Array from an existing one.

Let newArr2 = array. from(newArr,x=>x % 2 == 0)Copy the code

5. Use the array. of method

The array. of method creates a new Array based on the parameters passed in

let arr1 = Array.of(1); Let arr2 = array. of(1,2,3,4,5,6);Copy the code

We can also use this method to copy an existing array

let newArr = Array.of(... arr2)Copy the code

The effect is the same as array. from(arr2), but with a deconstruction method.

6. Use fill method

The fill method fills an array with static values

Fill (0,1)// [1,2,3,4,5,6] change to [1,0,0,0,0] let newArr3 = Newarr.fill (0,3,5)// Fill 0 with array indexes 3 through 5 (excluding 3 and 5)Copy the code

The fill method is very useful when creating arrays and initializing values

Let arr = Array(5).fill(0)Copy the code

Use the copyWithin method

The copyWithin method copies a series of elements in an array to the starting position specified in the same array

Let arr = [6]; Arr. CopyWithin (0,3); 1, arr. CopyWithin (1,3,5)Copy the code

1.7.4 Sorting elements

JavaScript provides a sorting method and a set of search methods.

The reverese method outputs an array in reverse order

Let arr = [1,2,3,4,5,6] arr.reverse()Copy the code

The sort method sorts an array

The sort method compares elements to each other by default as strings when sorting arrays. We can pass in our own comparison function arr.sort((a,b)=>a-b), which implements the ascending sort of arR.

1. Customize sort

We can also sort arrays of any object type, and we can create compareFunctions to compare elements.

Const friends = [{name: "orange", the age: 18}, {name: grapefruit, age: 22}, {name: 'watermelon' age: 17},]; function compareFunction(a,b){ if(a.age<b.age){ return 1 } if(a.age>b.age){ return -1 } return 0 } friends.sort(compareFunction)Copy the code

The output will be sorted in descending order by age

2. String sort

let names = ['Ana','ana','john','John']
console.log(names.sort())
// output:['Ana','John','ana','john']
Copy the code

JavaScript compares characters based on their CORRESPONDING ASCII values. If you pass a function to sort that ignores case, the sort function will have no effect at all. It will sort in the same alphabetical order as it does now. If you want lowercase letters to come first, use the localCompare method.

names.sort((a,b)=>a.localCompare(b))
Copy the code

LocalCompare can also sort accented characters.

1.7.5 search

There are two ways to search: the indexOf method returns the indexOf the first element that matches the argument. LastIndexOf returns the index of the last element that matches the argument. If none is found, -1 is returned

1.ES6– Find and findIndex methods

The find and findIndex methods accept a callback function and search for a value that meets the criteria for the callback function. The find method returns the first value that meets the criteria, and the findIndex method returns the index of that value in the array. If no value meets the criteria, find returns undefined and findIndex returns -1.

2.ES7– Use the includes method

The includes method returns true if an element exists in the array, false otherwise.

arr.includes(15)
Copy the code

If you pass a starting index to the includes method, the search starts at the location specified by the index.

1.7.6 Output array as a string

toString()

If you want to print all the elements of an array as a string, you can use the toString method.

join()

If you want to separate elements with a different separator, use the Join method

Const numberString = arr.join('-') console.log(numberString) // Output: 1-2-3-4-5-6Copy the code

Second, the stack

2.1 Stack data structure

A stack is an ordered collection that follows the lifO principle.

2.1.1 Creating an array-based stack

class Stack{
  constructor() {
    this.items=[]
  }
}
Copy the code

Since the stack follows LIFO principles, you need to restrict the insertion and functionality of elements. Next, you declare some methods for the stack.

2.1.2 Adding elements to the stack

 push(element){
  this.items.push(element)
}
Copy the code

2.1.3 Removing elements from the stack

pop(){
return this.items.pop();
}
Copy the code

2.1.4 Viewing the Top element on the stack

peek(){
    return this.items[this.items.length-1]
}
Copy the code

2.1.5 Checking whether the stack is empty

isEmpty(){
    return this.items.length === 0;
}
Copy the code

2.1.6 Obtaining the stack length

size(){
    return this.items.length;
}
Copy the code

2.1.7 Clearing stack elements

clear(){
    this.items=[];
}
Copy the code

OK! The stack has been completed

Create a Stack class based on JavaScript objects

The easiest way to create a Stack class is to use an array to store its elements. When using arrays, most methods have O(n) time complexity. If the array has many elements, it takes longer. In addition, an array is an ordered collection of elements, which takes up more memory space to keep the elements organized. Wouldn’t it be nice if we could grab the elements directly, take up less memory, and still make sure everything is arranged the way we want it to be? We can use a JavaScript object to store all the stack elements.

class Stack{ constructor() { this.count = 0; this.items = {}; }}Copy the code

In this version of the Stack class, we will use a count attribute to help us keep track of the Stack size (and also to help us add and remove elements from the data structure)

2.2.1 Inserting elements into the stack

  push(element) {
    this.items[this.count] = element;
    this.count++
  }
Copy the code

To add an element to the stack, we use the count variable as the key name of the Items object, and the inserted element is its value. After inserting elements into the stack, we increment the count variable.

2.2.2 Verify whether a stack is empty and its size

  size() {
    return this.count
  }
  isEmpty() {
    return this.count === 0
  }
Copy the code

2.2.3 Popping elements from the stack

Since we are not storing the elements in arrays, we need to implement the logic to remove the elements manually. First, we need to check if the stack is empty and return undefined if it is. If not empty, count–, saves the top of the stack, removes the top of the stack and returns the top of the stack. Since we are working with a JavaScript object, we can use the JavaScript delete operator to remove a specific value from the object

  pop() {
    if (this.isEmpty()) {
      return undefined
    }
    this.count--;
    const result = this.items[this.count];
    delete this.items[this.count];
    return result;
  }
Copy the code

2.2.4 Viewing the top element of the stack and clearing the stack

  peek() {
    return this.items[this.count - 1]
  }
  clear() {
    this.items = {}
    this.count = 0
  }
Copy the code

2.2.5 Creating the toString method

In the array version, we don’t need to worry about the implementation of the toString method, because the data structure can just use the toString method that the array already provides. For the version that uses objects, we’ll create a toString method that prints out the contents of the stack like an array.

toString() { if (this.isEmpty()) { return '' } let objString = `${this.items[0]}` for (let i = 1; i < this.count; i++ ){ objString=`${objString},${this.items[i]}` } return objString }Copy the code

With the toString method implemented, we are done with this version of the Stack class. With the exception of the toString method, the other methods we created have a complexity of O(1), which means we can directly find the target element and manipulate it (push, POP, or peek).

2.3 Protecting Data inside data Structures

When creating data structures or objects that other developers can use, we want to protect the internal elements, and only the methods we expose can modify the internal structure. Unfortunately, the items and count properties we declare in the Stack class are not protected and we can access them directly, Object. GetOwnPropertyNames (stack) Object. Keys (stack) because JavaScript class work that way. The ES6 class is prototype-based. Although prototype-based classes save memory and are better at scaling than function-based classes, they cannot declare private properties (variables) or methods in this way. Here’s a look at some other ways to implement private properties using JavaScript.

2.3.1 Naming conventions for underscores

class Stack{ constructor(){ this._count = 0; this._items = {}; }}Copy the code

However, this method is only a convention and does not protect the data.

2.3.2 Implement the class with ES6 scoped Symbol

ES6 adds a basic type called Symbol, which is immutable and can be used as an attribute of an object.

const _items = Symbol(); class Stack{ constructor() { this[_items] = []; }}Copy the code

This method creates a false private attribute, because ES6’s new Object. getownProperty-symbol method fetches all Symbol attributes declared in the class.

const stack = new Stack();
stack.push(5);
stack.push(8);
let objectSymbols = Object.getOwnPropertySymbols(stack);
console.log(objectSymbols.length);
console.log(objectSymbols);
console.log(objectSymbols[0]);
stack[objectSymbols[0]].push(1);
console.log(stack);
Copy the code

output:
1
[ Symbol() ]
Symbol()
Stack { [Symbol()]: [ 5, 8, 1 ] }

Copy the code

We can do whatever we want with arrays, but we’re dealing with stacks, and that shouldn’t happen.

2.3.3 Implement the class with ES2015 WeakMap

A data type that ensures that properties are private is WeakMap. WeakMap can store key-value pairs, where keys are objects and values can be of any data type.

const items = new WeakMap();
class Stack{
  constructor() {
    items.set(this,[])
  }
  push(element) {
    const s = items.get(this);
    s.push(element)
  }
  pop() {
    const r = items.get(this);
    r.pop()
    return r
  }
}
Copy the code

Items are now truly private properties in the Stack class, but with this approach the code is less readable and cannot inherit private properties when extending the class.

The last

⚽ This article introduces arrays and stacks in JavaScript data structures, and we believe you have a deeper understanding of them. ⚾ If this article helped you, please like it. 🏉 I have other columns, please read ~ 🏐 play the beauty of CSS 🎱Vue from giving up to getting started 🎳 simple JavaScript