## Front end algorithm series one: time complexity, space complexity and data structure stack, queue implementation

JasonCloud 2021-01-23 10:28:05
end algorithm series time complexity

## One 、 The reason and plan for this series

Some time ago, I met a practical problem: how to get the best currency , The mathematical description is to solve the problem as follows ：

1x + 5y +10z + 15k + 20*j = 16 ; I started thinking about how to solve multivariate equations , Wang matrix is solved , The result is more complicated , Later, I found that this is very similar to the knapsack problem ; Then I'll go over some knowledge about algorithms and data structures , And there's this series , My plan is to introduce the relevant data structures one by one , And with JavaScript Do it again , Then some classics and examples are used ; Don't say much, start with the most basic ： Complexity 、 Stack 、 queue ;

## Two 、 Complexity

When it comes to algorithms and data structures, there are only two problems to be solved ：1、 How to get the expected results more quickly and accurately ;2、 How to use as few resources as possible to get the expected results ; And these two problems are the performance problems that we usually talk about , Solving these two problems will solve most of the performance problems ; How to measure or choose between the two , Sometimes you can't have both , If it wasn't for less resources and less time , Or in order to achieve the desired results more quickly and sacrifice a certain amount of resource storage , It's about space complexity and time complexity

Spatial complexity ： This means that to achieve a certain function or method to occupy the memory resources of our computer , In many cases, memory resources may not be the first priority , As long as the speed is fast, it can be realized , For example, the count sort in sort will define an intermediate array , The length of the array is the maximum value of the array to be sorted , This will undoubtedly require more memory overhead ;

Time complexity ： Time complexity is large O To express , Although we can't accurately calculate the execution time from the code , It's also unrealistic because of the time and operating system 、 It's all about hardware , So we usually have estimates to express ; Popular point is to look at the number of times the code has been repeatedly executed O(n);

O(1): In this case, no matter how it works count Method , Method inside ++n It's only done once , It doesn't change with the parameters n Change with the increase of , This time complexity is a constant ;

``function count (n) { return ++n; } count(n);``

O(n): This situation is with the change of parameters , The number of times the code is executed changes linearly ;

``````function consoleFn(n) {
for(let i = 0; i < n; i++){
console.log(i)
}
}``````

O(log2n)： This is what we call logarithmic complexity ; Like a dichotomy search or something ;2^i = n => obtain i = log2n;

``````function consoleFn(n) {
let i = 1;
while(i < n){
i = i * 2;
console.log(i);
}
}``````

O(nlog2n)： Linear logarithm ; Like the time complexity of fast scheduling

``````function consoleFn(n) {
for(let j = 0; j < n; j++) {
let i = 1;
while(i < n){
i = i * 2;
console.log(i);
}
}
}``````

O(n2)： In this case, the number of execution will increase with n There is a multiple increase with the increase of ;

``````function consoleFn(n) {
for(let i = 0; i < n; i++){
for(let j = 0; j < n; j++){
console.log(i)
}
}
}``````

## data structure ：

### 1、 Stack

Stack is a kind of following FIFO （FILO） An orderly collection of principles . The newly added or deleted elements are stored at the same end of the stack , It's called the top of the stack , The other end is called the bottom of the stack . In the stack , The new elements are all near the top of the stack , The old elements are close to the bottom of the stack .

How to implement a stack data structure ？

First of all, let's order some of his api:

push(val)： Add an element to the top of the stack ;

size()： Return the stack size ;

isEmpty(): Returns whether the stack is empty

pop()： Out of the stack

clear(): Empty stack

``````export default class Stack {
constructor() {
this.items = [];
}
push(val) {
this.items.push(val);
}
size() {
return this.items.length;
}
isEmpty() {
return this.items.length === 0;
}
pop() {
return this.items.pop();
}
peek() {
return this.items[this.items.length - 1]
}
clear() {
this.items = [];
}
}``````

Simple operation ：

``````const stack = new Stack();
console.log(stack.isEmpty()); // true
stack.push(5);
stack.push(8);
stack.push(11);
stack.push(15);
console.log(stack.isEmpty()); // false
console.log(stack.size());// 4
console.log(stack.peek());//15
stack.pop();// 15
console.log(stack.size());// 3
console.log(stack.peek());//11``````

reflection ： Practical application of stack ？

vue The stack is used to determine whether the template characters are legal when parsing the template in , This is the same as many editors checking what we write when they write code HTML Whether the element is closed or not is the same principle .

### 2、 queue ;

The queue follows the first in, first out （FIFO, Also known as first come, first served ） An ordered set of terms of a principle . The queue adds new elements at the end , And remove the elements from the top . The newly added element must be at the end of the queue . In reality , The most common example of queues is queues .

How to implement a queue data structure ？

First of all, let's set up some of his api:

enqueue(val)： queue Add an element ;

size()： Returns the size of the queue ;

isEmpty(): Returns whether the queue is empty

dequeue()： Outgoing queue

clear(): Clear queue

``````export default class Queue {
constructor() {
this.items = [];
}
enqueue(val) {
this.items.push(val);
}
size() {
return this.items.length;
}
isEmpty() {
return this.items.length === 0;
}
dequeue() {
return this.items.shift();
}
peek() {
return this.items
}
clear() {
this.items = [];
}
}``````

Simple operation ：

``````const queue = new Queue();
queue.enqueue('a');
queue.enqueue('b');
queue.enqueue('c');
queue.enqueue('d');
console.log(queue.isEmpty()); // true
console.log(queue.size());// 4
console.log(queue.peek());// a
console.log(queue.dequeue());;// a
console.log(queue.dequeue());;// b
console.log(queue.dequeue());;// c``````

Queue applications are common , For example, many task event queues 、vue The update queue for 、vue Of mixin Merge queues , It's all based on the first in, first out principle

reflection ： Is there a better way to implement queue and stack on it ？ What's wrong with the implementation above ？

### 3、 deque

A double ended queue is a special queue that allows us to add and remove elements from both the front end and the back end . He's a variant based on the basic queue

api Definition of interface :

addFront(element)： This method adds new elements to the front end of the double ended queue .

addBack(element)： This method adds new elements to the back end of the two end queue .

removeFront()： This method removes the first element from the front end of the double ended queue .

removeBack()： This method removes the first element from the back end of the double ended queue .

peekFront()： This method returns the first element of the front end of the double ended queue .

peekBack()： This method returns the first element of the back end of the double ended queue .

Code implementation ：

``````import Queue from "./QueueArr";
export class Deque extends Queue{
constructor() {
super();
}
this.items.unshift(element);
}
this.enqueue(element);
}
removeFront() {
return this.dequeue();
}
removeBack() {
return this.items.pop();
}
peekFront() {
return this.items;
}
peekBack() {
return this.items[this.items.length - 1];
}
}``````

Simple operation ：

``````const deque = new Deque();
console.log(deque.size()) // 4
console.log(deque.peekFront());;// a
console.log(deque.peekBack());// d
console.log(deque.removeFront());//a
console.log(deque.removeBack());//d``````

Application of two terminal queue ：

Check whether a paragraph in English is palindrome , Generally, the simpler way is to convert it into an array , Then reverse the order and convert it to a string to see if they are the same , To determine whether it is palindrome ; such as ：ababa In reverse order or ababa; This is palindrome , Similarly, we can judge whether it is palindrome by using two terminal queue ; The idea is to put the string into a double ended queue , Then take out the head and tail of the team to see if they are the same , Until the queued element is less than or equal to 1 Elements , The code implementation is as follows ：

``````import {Deque} from "./Deque";
export const palindromeChecked = (str) => {
if(!str){
return false;
}
const deque = new Deque();
const strs = str.toLowerCase().split('');
for (let i = 0; i < strs.length; i++) {
}
let start = '', end = '', isTrue = true;
while (deque.size() > 1 && isTrue) {
start = deque.removeFront();
end = deque.removeBack();
if (start != end) {
isTrue = false;
}
}
return isTrue
}

reflection ： By learning about queues and stacks , How to use queue and stack to realize a four arithmetic operation , such as cal('1+2-3+6/3') The result is 16

## Part of the thinking answers

### Judge whether the label is closed or not

Ideas ：

1、 Tag parsing of strings

2、 Create a label stack , Press the start tag into the stack , When the closed tag is not found, the stack will be pulled out

3、 Match to the end , Judge whether the stack is empty , If it's empty, it means it's all closed , If there is any indication that there is a label that cannot be closed

### Better implementation of queues and stacks

The stack and queue implementation above all use arrays , Delete and add elements to the array , And the operation on array is actually more expensive , Like other static languages , Actually JavaScript It's also very complicated for array operations, just js The engine does these things for us , For example, delete or add an element from the head of the array , In fact, you have to translate the other elements of the array inside , For example, to insert an element array, you need to increase the length first , Then move all the elements back one bit, empty the head, and put the elements to be added into , So it's better to use objects than arrays

``````export default class Queue {
constructor() {
this.counter = 0;// The counter calculates the size of the queue
this.items = {}; // Queue storage
this.lowestCount = 0; // Queue header
}
peek() {
return this.items[this.lowestCount];
}
enqueue(element) {
this.items[this.counter] = element;
this.counter++;
}
dequeue() {
if (this.isEmpty()) {
return undefined;
}
const result = this.items[this.lowestCount];
delete this.items[this.lowestCount];
this.lowestCount++;
return result;
}
isEmpty() {
return this.size() === 0;
}
size() {
return this.counter - this.lowestCount;
}
clear() {
this.counter = 0;
this.lowestCount = 0;
this.items = {};
}
}``````

### arithmetic

Ideas ：

1、 Achieve lexical analysis, parsing a lexical queue ：tokens;

2、 Get tokens To deal with , At this point, define a number stack , A stack of operands

3、 When it comes to numbers, push them into the number stack , When it comes to operators , Determine whether the operation can be performed , If you can calculate, you can get out of the digital stack 2 Number , And then the operators stack out an operator , And then do the corresponding operations , And push the result into the digital stack , As the next operation number

1+2-3+6/3 => tokens = [

'{type: 'number',value:'1'},

{type: 'operator', value: '+'},

'{type: 'number',value:'2'},

{type: 'operator', value: '-'},

'{type: 'number',value:'3'},

{type: 'operator', value: '+'},

'{type: 'number',value:'6'},

{type: 'operator', value: '/'},

'{type: 'number',value:'3'},

]'

https://javamana.com/2021/01/20210123102541844d.html