The stack

01. What is a stack?

  1. Also known as stack.

  2. “Special” linear memory structure.

  3. An efficient data structure.

  4. Restricted operation. Limit it to insert or delete only on one end. The operable end is called the top of the stack and the unoperable end is called the bottom.

  5. The operation of adding an element is also called a push, push, or push; This means to add the element to the top of the stack.

  6. The operation of deleting elements is also called out of the stack, the stack; Remove the element from the top of the stack. The element next to it is called the new top element.

  7. The basic operations of the stack in addition to the top of the stack to insert and delete, there are stack initialization, empty, and the top of the stack element.

A stack is a linear storage structure that can only access data from one end and follows the “first in, last out” (LIFO) principle.

02. Why are stacks created?

If you’re wondering, compared to arrays and lists that we’ve had before, the stack comes with limitations, but it doesn’t have any obvious advantages. Functionally, arrays and lists are completely alternative to stacks.

The reason:

  1. A specific data structure is actually an abstraction of a specific scenario to deal with certain scenarios.

  2. Arrays and linked lists, flexible, but less controllable.

Therefore, if a certain set of data conforms to one end of the insert and delete data, and conforms to the principle of first in, then the stack should be preferred.

03. Concrete implementation of stack

1. Sequential stack: Sequential storage structure

Class Stack {constructor() {this.data = []} push(item) {this.data[this.top++] = Item} pop() {if (this.top === 0) {return null} Return this.data[--this.top]} clear() {this.top = 0} get length() {return this.top}}Copy the code

2. Chain stack: chain storage structure

class StackNode { constructor(data) { this.data = data this.next = false } getData = () => this.data setData = (data) =>  (this.data = data) getNext = () => this.next setNext = (next) => (this.next = next) } class Stack { constructor() { this.head = false this.tail = false } empty() { return this.head === false } push(data) { let temp = new StackNode(data)  if (! this.head) { this.head = this.tail = temp } else { temp.setNext(this.head) this.head = temp } } pop() { if (this.empty()) return false let data = this.head this.head = this.head.getNext() return data.getData() } }Copy the code

04. Time/space complexity

Whether it’s a sequential stack or a chain stack, in the process of pushing and exiting the stack, you are manipulating the top element of the stack, and only one or two temporary variables are needed, so the spatial complexity is O(1); The time complexity is O(1)

Space complexity refers to the storage space required to perform an operation in addition to the original data storage space.

Application 05.

1. Expression evaluation

  1. 3 + 6 * 2-6 =?

  2. Method: This is done with two stacks, one for operands and the other for operators.

  3. How it works: We walk the expression from left to right, and when we encounter a number, we push directly into the operand stack; When an operator is encountered, it is compared to the top element of the operator stack. If the priority is higher than the element at the top of the operator stack, the current operator is pushed onto the stack; If the priority is lower than or equal to that of the top operator, take the top operator from the operator stack, take the two operands from the top of the operand stack, and then calculate, and then push the result of the calculation into the operand stack, and continue the comparison.

2. Match parentheses

Given a only include a '(',') ', '{','} ', '/', ' 'the string s, determine whether a string is effective. A valid string must meet the following requirements: The opening parenthesis must be closed with the same type of closing parenthesis. The opening brackets must be closed in the correct order. ()[]{} ==> true ([)] ==> false ([]) ==> trueCopy the code

Illustration:

Solution:

function validate(str: string): boolean { if (str.length % 2 ! == 0) return false; const stack = []; for (let item of str) { switch (item) { case "{": case "[": case "(": stack.push(item); break; case "}": if (stack.pop() !== "{") return false; break; case "]": if (stack.pop() ! == "[") return false; break; case ")": if (stack.pop() !== "(") return false; break; } } return !stack.length; } console.log('TEST_R', validate('') === true); console.log('TEST_R', validate('[])') === false); console.log('TEST_R', validate('[](){}') === true);Copy the code

3. Function call — JS execution context stack

Several concepts:

Scope: The extent to which variables and functions are accessible. That is, the scope controls the visibility and lifecycle of variables and functions.

Execution context (EC) : An abstraction of the context in which JavaScript code is being parsed and executed. Whenever JS code is executed, it is executed in the execution context. Javascript execution context

Perform context classification:

1. Global execution context

2. Function execution context

3. Context for executing the Eval function

Execution Context Stack (ECS) : A stack memory (ECS) is formed before the Execution of the code. It is used to store all Execution contexts created during the Execution of the code. During the execution of the code, it will enter a different execution context. After the execution context is created, it will enter the stack. After the execution, it will exit the stack.

🌰 : 【Debug demonstration 】

let a = "global var";

function initPage() {
  console.log("on start");
  initState();
  console.log("end start");
}

function initState() {
  console.log("init state");
}

initPage();

console.log("Inside Global Execution Context");
Copy the code

When the above code loads in the browser, the JavaScript engine creates a global execution context and pushes it onto the current execution stack. When the initPage() function is called, the JavaScript engine creates a new execution context for the function and pushes it to the top of the current execution stack.

When the initState() function is called inside the initPage() function, the Javascript engine creates a new execution context for the function and pushes it to the top of the current execution stack. When the initState() function completes execution, its execution context is ejected from the current execution stack, and context control is moved to the next execution context on the current execution stack, that of the initPage() function.

When the initPage() function completes execution, its execution context is ejected from the current execution stack, and context control is moved to the global execution context. Once all the code is executed, the Javascript engine removes the global execution context from the execution stack.

A more rigorous definition is:

Execution context Stack ===> Call Stack

Execution context ===> Call Frame Call Frame

The implementation principle of onion model of Koa middleware is also a typical practice case.

Github.com/koajs/koa/b…

In development, how to use the call stack?

  • Browser can debug view the current function execution call stack (call relationship), used to debug code.

  • Locate error points based on the collected exception error stack.

4. Browser history stack

Browser history Stack Management case:

After you have visited A sequence of pages A-B-C, click the browser’s back button to view pages B and B that you have visited before. When you go back to page A, click the forward button to revisit pages B and C. However, if you go back to page B and click on a new page D, you will no longer be able to view page C through the forward and backward functions.

The stack is used to complete the history storage of the browsing page, both forward and backward to re-trigger the browser load.

Vue-stack-router Indicates a stack route

The Wue-stack-router implements stack management of front-end routes and is suitable for hybrid scenarios.

The following is an extract from the source code.

private routeStack: Array<IRouteAndConfig<Component>> = []; // Routing stack // https://github.com/luojilab/vue-stack-router/blob/65d3719a1e5b0c7d83c813aef54517981fbd756a/src/lib/Router.ts#L300 private updateRouteRecords(type: RouteActionType, routeInfo: IRouteAndConfig<Component>, transition?: unknown): void { switch (type) { case RouteActionType.PUSH: this.routeStack.push(routeInfo); this.componentChange(type, transition); break; case RouteActionType.REPLACE: const preRoute = this.routeStack.pop(); this.routeStack.push(routeInfo); this.componentChange(type, transition); if (preRoute) { this.emit(RouteEventType.DESTROY, [preRoute.route.id]); } break; case RouteActionType.POP: const index = this.routeStack.findIndex(i => routeInfo.route.id === i.route.id); if (index === -1) { this.routeStack = [routeInfo]; this.componentChange(type, transition); } else { const destroyedIds = this.routeStack .splice(index + 1, this.routeStack.length - index - 1) .map(r => r.route.id); this.componentChange(type, transition); this.emit(RouteEventType.DESTROY, destroyedIds); } break; default: this.componentChange(type, transition); }}Copy the code

6. The stack overflow

1. What is stack overflow?

The call stack (execution context stack) has a size, and when the number of call frames (execution context) pushed into the stack exceeds a certain number, the JavaScript engine will report an error called stack overflow.

The scenarios that lead to stack overflows are analyzed by taking the stack overflows caused by JavaScript long recursion as an example:

Calculate the factorial of 🌰 :

1
2x1
3x2x1
4x3x2x1
5x4x3x2x1
6x5x4x3x2x1
Copy the code

Solution:

// Solution 1: Function factorial (number) {let result = 1 while (number > 1) {result = result * number * (number - 1) Number = number - 2} return result} Function factorial(number) {if (number < 2) {return 1} else {return number * factorial(number-1)}} function factorial(number < 2) {return 1} else {return number * factorial(number-1)}}Copy the code

Comparison of the two schemes:

  • Loop performance is higher, only one call frame is generated, and memory usage is lower.

  • With recursion, the code is easier to understand, requires many call frames, and takes up a lot of memory.

2. Why does long recursion tend to raise stack overflow?

The essence of recursion is that a function calls itself over and over again. In JS, call frames are always generated in the call stack. Each call frame takes up a certain amount of memory. In addition, JS is single-threaded, and there is only one call stack, and the size of the stack is also limited, so it is easy to produce stack overflow.

The size of the call stack can be calculated using the following method:

function computeMaxCallStackSize () {
  try {
    return 1 + computeMaxCallStackSize()
  } catch (e) {
    // Call stack overflow
    return 1
  }
}
num = computeMaxCallStackSize() // 11385
Copy the code

3. Tail call optimization

1. The tail calls

  1. Concept: When the last step of a function is to call another function, this function is a tail-call function.

  2. Case study:

2. Tail call optimization

  1. Principle: Tail call because the last step of a function is to call another function, so the call location, variable information, scope chain, etc., do not need to continue to store, directly use the inner function call record instead of the outer function call record. In this way, only one call record will be generated for each call, which is extremely memory saving, and there will never be a stack overflow.

3. The tail recursion

  1. Definition: The function call itself, called recursion. If the tail calls itself, it is called tail recursion.

4. Tail recursive optimization

  1. Principle: Tail recursion says that recursion and tail call form, because only one call record, so never “stack overflow” error.

  2. Case study:

5. Schematic diagram:

6. Other

  1. The complexity is reduced from O(n) to O(1). As you can see, tail recursive optimization is important for recursive operations.

  2. Tail recursive optimization is part of the language specification and it is not clear how well other languages support it; Tail recursive optimization is not implemented in JS versions below ES6. ES6 deploys the Proper Tail Calls/PTC optimization.

  3. Support for tail-recursive optimization: ES6 compatibility across platforms

  4. ES6 tail call optimization is only enabled in strict mode, normal mode is invalid.

  5. Tail recursion PTC and STC in JS

References:

  • Call stack (Call stack)

  • Tail recursion

The queue

01. What is a queue?

  1. Linear memory structure

  2. Restricted operation. When data elements are queued, they can only be queued from one end of the table and dequeued from the other.

  3. An insert operation is also called an enqueue, and new elements are always added at the end of the queue. A delete operation is also called a dequeue. You can only remove the first element.

  4. The end of the line is called the end; The end of the queue is the head of the queue.

  5. The principle of storing data from one end of the queue and fetching data from the other end is called the “first in, first out” principle

A queue is an ordered set of items that follow a first-in, first-out (FIFO) principle.

02. Concrete implementation of queues

  • There are many ways to implement data structures that store elements in queues, such as arrays, linked lists, objects, and so on. Here we use an object to hold the element.

  • We also need to declare a count attribute to help us control the size of the queue. In addition, since we are removing elements from the front of the queue, we also need a variable lowestCount to help us track the first element.

    Class Queue {constructor() {this.data = {} this. LowestCount = 0 // this. Count = 0 // this. enqueue(element) { this.data[this.count] = element this.count++ } dequeue() { if (this.isEmpty()) { return undefined } const result = this.data[this.lowestCount] delete this.data[this.lowestCount] this.lowestCount++ return result } peek() { if (this.isEmpty()) { return undefined } return this.data[this.lowestCount] } isEmpty() { return this.count – this.lowestCount === 0 } size() { return this.count – this.lowestCount } clear() { this.data = {} this.count = 0 this.lowestCount = 0 } }

Complexity 03.

Just like the stack, the time and space complexity of the in-queue and out-of-queue operations are both O(1).

04. Circular queue

The above queue model is a simple, inefficient queue.

Reason: In a normal queue, once a queue is full, we cannot insert the next element, even though there is still room at the front of the queue.

A more efficient approach is to use circular queues. Specifically, we can use a fixed-size array and two Pointers to indicate the start and end positions. The goal is to reuse the wasted storage we mentioned earlier.

This.list = new Array(len) // front = 0 // front = 0 // front = 0 If (this.isfull ()) {return false} else {if (this.isfull ()) {return false} else {if (this.isfull ()) {return false} else { This.rear = (this.rear + 1) % this.max return true}} dequeue() {if (! this.isEmpty()) { const result = this.list[this.front] this.list[this.front] = "" this.front = (this.front + 1) % this.max return result } return false } getFront() { if (this.isEmpty()) { return -1 } return this.list[this.front] } getRear() { if (this.isEmpty()) { return -1 } let rear = this.rear - 1 return this.list[rear < 0 ? this.max - 1 : rear] } isEmpty() { return this.front === this.rear && ! this.list[this.front] } isFull() { return this.front === this.rear && !! this.list[this.front] } }Copy the code

05. Dual-end queue data structure

A deque, or double-ended queue, is a special queue that allows us to add and remove elements from both the front end and the back end.

A two-endian queue is a data structure that combines queue and stack, complying with both first-in, first-out and last-in, first-out rules.

  1. Example: A person who has just bought a ticket can go straight back to the head of the line if they just need to ask some more simple information. In addition, if the person at the end of the line is in a hurry, he can just leave the line.

  2. implementation

  3. The two-endian queue has more elements than the queue, so the methods of obtaining queue size, emptying queue, emptying queue and obtaining all elements in queue in the ordinary queue also exist in the two-endian queue and the implementation code is the same.

  4. Since elements can come and go from both ends of the queue, we need to implement the following function:

  • Add the element addFront at the head of the queue

  • Add the element addBack to the end of the queue

  • Gets the team lead element peekFront

  • Gets the tail element peekBack

  • Remove the first element removeFront

  • Remove the tail element removeBack

    // constructor() {this.items = {} this.lowestcount = 0 // constructor() {this.items = {} this.lowestcount = 0

    peekFront() { if (this.isEmpty()) { return undefined } return this.items[this.lowestCount] }

    peekBack() { if (this.isEmpty()) { return undefined } return this.items[this.count] }

    isEmpty() { return this.count – this.lowestCount === 0 }

    size() { return this.count – this.lowestCount }

    clear() { this.items = {} this.count = 0 this.lowestCount = 0 }

    AddFront (element) {if (this.isEmpty()) {this.addback (element)} else if (this.lowestCount > 0) { This.lowestcount — this.items[this.lowestCount] = element} else {// lowestCount = 0, For (let I = this.count; i > 0; i–) { this.items[i] = this.items[i – 1] } this.count++ this.lowestCount = 0 this.items[0] = element // {4} } }

    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 } const result = this.items[this.count] delete this.items[this.count] this.count– return result } }

06. Apply — Javascript task queues

1. Understand task queues

A “task queue” is essentially a queued data structure in which the tasks that are executed are queued in turn, and the first events are read first by the main thread. The reading process of the main thread is basically automatic, as long as the execution stack is cleared, the first event in the queue will automatically enter the main thread for execution.

2. Cause of Javascript task queue

Javascript is single-threaded, and single-threaded means that tasks are queued up so that one task ends before another can begin. If the previous task takes too long, the later task will be blocked.

A time-consuming task may be an I/O task. In this case, the CPU is idle, resulting in low CPU utilization efficiency.

So there is a task queue. Using the main thread makes it possible to suspend tasks in waiting and run the next tasks first, regardless of the I/O device. Wait until the IO device returns the result, then go back and continue the suspended task.

3. Use of Javascript task queues

Task queues are used in Javascript:

  • The task queue is required in the Browser Event Loop

  • The Event Loop in NodeJS also uses the task queue

  • Other scenarios: Thread pools

Take the Event Loop in the browser as an example:

console.log('script start'); setTimeout(function () { console.log('setTimeout'); }, 0); Promise.resolve() .then(function () { console.log('promise1'); }) .then(function () { console.log('promise2'); }); console.log('script end'); // Promise1 // promise2 // setTimeout. // Promise1 // Promise2 // setTimeoutCopy the code

First, let’s review the process of the event loop:

  • JavaScript is single-threaded, and single-threaded tasks are divided into synchronous and asynchronous tasks.

  • Synchronous tasks wait in the call stack for the main thread to execute in turn, and asynchronous tasks will be placed in the specified task queue when encountered.

  • After the asynchronous task has the result, it registers the callback function to the task queue, waits for the main thread to be idle (the call stack is empty), and then puts the callback function into the execution stack from the task queue and waits for the main thread to execute.

  • After the synchronization task is executed, if the stack is empty, the MicroTask queue is checked to see if it is empty. If it is empty, the MacroTask queue is executed.

  • Otherwise, all the microtask queues will be executed at once.

  • Each time a macro task is executed, it checks whether the microtask queue is empty. If it is not empty, the microtask queue is executed on a first-in, first-out basis. Then the next macro task is executed, and so on. Until the end.

Specific implementation process:

  • Step 1: Initial state

  • Step 2: Perform the synchronization task

  • Step 3: setTimeout Callback to the Task queue

  • Step 4: Put the Promise Callback into the Microtasks task queue

  • Step 5: Continue the synchronization task

  • Step 6: Cancel the stack after the synchronization task is completed

  • Step 7: First execute the Microtasks in the Microtasks queue, and push the callback function

  • Step 8: After promisE1 is executed, the next Promise Callback is enqueued as a new microtask

  • Step 9: After the first Promise callback is completed, the callback function frames off the stack, and the first Primise task exits the queue. Continue with the second microtask.

  • Step 10: The second microtask is executed, its callback function is pushed, and the log is printed

  • Eleventh: after the second microtask is completed, the microtask queue is empty and ready to execute the macro task in the next macro task queue

  • Twelfth: macro task execution, callback function pushed

  • Thirteenth: macro task completion, callback function frame out of the stack, macro task out of the queue, the queue empty, the execution is completed.

The thread pool:

Simple check, the traditional thread pool, maintain a shared task queue, and then multiple threads through the lock mutually exclusive way to access the queue, take out the task execution. Libuv, Nginx.

For example :(a step in the next iteration of an iget-icon)

Background: An interface is used to perform build and publish operations.

Preliminary plan:

  • This is done through the child_process child thread of nodeJS.

  • Create a child thread to execute the task, and notify the publisher through wechat when the child thread finishes executing.

  • Of course, we can’t create a child thread on every request, because creating too many threads would add to the burden.

  • A pool of child threads (limited in size) needs to be maintained. Each child thread has its own task queue. Each task is assigned to a child thread to execute. Waiting for execution.

Asynchronous queue:

How to make asynchronous functions execute sequentially. There are many methods, such as callback, promise, generator, async/await, etc., that can fulfill this serialization requirement.

For example, in a certain scenario, multiple asynchronous tasks need to be executed one by one.

task.then(() => task1.then(() => task2.then(...) )) async () => { await task1(); await task2(); await task3(); } / /...Copy the code

If only there was a queue. Add asynchronous tasks to the queue and let the queue run when executing.

const queue = () => { const list = []; // Let index = 0; Const next = () => {if (index >= list.length - 1) return; const cur = list[++index]; cur(next); } const add = (... fn) => { list.push(... fn); } // Const run = (... args) => { const cur = list[index]; typeof cur === 'function' && cur(next); } return {add, run, Const asyncFunc = (x) => {return (next) => {setTimeout(() => {console.log(x); next(); // Asynchronous task completion call}, 1000); } } const q = queue(); const tasks = '123456'.split('').map(x => asyncFunc(x)); q.add(... tasks); q.run();Copy the code

Thoughts and Summary

After all this, we only have a certain understanding of these two data structures, but it is more important to practice.

Although there are not many scenarios that need to use data structures in our daily front-end development, we can still think about problems from multiple perspectives, such as whether a certain data structure can be used to solve problems conveniently.

Usually encountered business scenarios may be relatively simple, the need to use the algorithm is not a lot of scenarios, but there are (such as: e-commerce in the multi-specification selector).

Using apis like Map, Set and Array to solve problems is also one of the most important aspects of our front end. At ordinary times, most of the business scenarios are relatively simple, we want to make this foundation solid, or more to buckle the problem.