One, foreword
All three are data structures, and understanding data structures is an essential part of being a technical professional. In the daily interview, you may encounter a series of stack, heap, queue and so on.
- Execution stack and task queue of Event Loop.
- Variable storage heap, stack issues.
- The realization of stack and queue data structure.
- What is stack, heap, queue?
- There is also a list of related handwriting problems.
In the interview, it is common to ask a number of questions related to it.
Second, the stack
2.1 introduction
A stack is an ordered collection that follows the last in, first out (LIFO) principle. Newly added and to be deleted data are stored on the same end of the stack at the top of the stack, and the other end is at the bottom of the stack. The new element is near the top of the stack, and the old element is near the bottom. The stack is automatically allocated by the compiler. The stack uses level 1 caching. When the call is in the storage space, the call is automatically released.
For example: ping-pong boxes/building blocks
2.2 Storage of basic data structures (storage stack)
In javaScript, data types are divided into basic data types and reference data types. Basic data types include string, number, Boolean, undefined, NULL, symbol, and Bigint. In memory these data types are stored in stack space, which we access by value. Prototype types are stored in stack memory and are fixed in size and ordered.
2.3 Execution Stack (function call stack)
Now that we know about the storage of basic data structures, let’s look at how multiple execution contexts are managed in JavaScript via a stack.
- When a program execution enters an execution environment, its execution context is created and pushed onto the execution stack (push).
- When a program completes execution, its execution context is destroyed and pushed off the top of the stack, handing control to the next execution context.
Every executable code in JavaScript creates an executable context before it is interpreted and executed. There are three types of executable contexts by executable code block.
- Global executable context: Every program has one global executable code, and only one. Any code that is not inside a function is in the global execution context.
- Function executable context: Each time a function is called, a new context is created for that function. Each function creates its own execution context when it is called.
- Eval executable context: Eval also has its own execution context.
“The bottom of the stack is always the execution context of the global environment”. On the other hand, “at the top of the stack is the execution context of the currently executing function,” which is pushed off the top of the stack when the function call completes (ideally, closures prevent this operation; more on closures in a future article).
“There is only one global environment, and there is only one global execution context, and it is only pushed out of the execution stack when the page is closed, otherwise it remains at the bottom of the stack.”
Here’s an example:
let name = 'snail';
function sayName(name) {
sayNameStart(name);
}
function sayNameStart(name) {
sayNameEnd(name);
}
function sayNameEnd(name) {
console.log(name);
}
Copy the codeDeclare as the code progresses:
2.4 Creating a stack (implementing the stack method)
We need to create our own stack, and this stack contains some methods.
- Push (element(s)): Add one (or more) new elements to the top of the stack
- Pop (): deletes the element at the top of the stack and returns it
- Peek (): returns the top element of the stack without doing anything to the stack
- IsEmpty (): checks whether the stack isEmpty
- Size (): returns the number of elements in the stack
- Clear () : empty stack
function Stack() {
let items = [];
this.push = function(element) {
items.push(element);
};
this.pop = function() {
let s = items.pop();
return s;
};
this.peek = function() {
return items[items.length - 1];
};
this.isEmpty = function() {
return items.length == 0;
};
this.size = function() {
return items.length;
};
this.clear = function() { items = []; }}Copy the codeHowever, this approach creates multiple copies of items when creating multiple instances. It’s not very appropriate. How to implement Stack class with ES 6. WeakMap can be used to implement this and ensure that the properties are private.
let Stack = (function() {
const items = new WeakMap();
class Stack {
constructor() {
items.set(this, []);
}
getItems() {
let s = items.get(this);
return s;
}
push(element) {
this.getItems().push(element);
}
pop() {
return this.getItems().pop();
}
peek() {
return this.getItems()[this.getItems.length - 1];
}
isEmpty() {
return this.getItems().length == 0;
}
size() {
return this.getItems().length;
}
clear() { this.getItems() = []; }}returnStack; }) ();Copy the code2.5 Using stacks to Solve problems
The stack can solve the decimal to binary problem, the arbitrary base conversion problem, the balance circle bracket problem, the Hanrota problem.
// Example of decimal to binary problemfunction divideBy2(decNumber) {
var remStack = new Stack(),
rem,
binaryString = ' ';
while (decNumber > 0) {
rem = Math.floor(decNumber % 2);
remStack.push(rem);
decNumber = Math.floor(decNumber / 2);
}
while(! remStack.isEmpty()) { binaryString += remStack.pop().toString(); }returnbinaryString; } // Any base conversion algorithmfunction baseConverter(decNumber, base) {
var remStack = new Stack(),
rem,
binaryString = ' ',
digits = '0123456789ABCDEF';
while (decNumber > 0) {
rem = Math.floor(decNumber % base);
remStack.push(rem);
decNumber = Math.floor(decNumber / base);
}
while(! remStack.isEmpty()) { binaryString += digits[remStack.pop()].toString(); }return binaryString;
}
Copy the code2.6 Stack Overflow
2.6.1 Stack size limit
Different browsers have a limit on the size of the call stack, beyond which the stack overflow will occur. The following code verifies that the size of the call stack is not limited by the browser.
var i = 0;
function recursiveFn() { i++; recursiveFn(); } try { recursiveFn(); } catch (ex) {console.log(' my maximum call stack I =${i} errorMsg = ${ex}`);
}
Copy the codeGoogle Chrome:
2.6.2 Stack overflow of recursive call
function Fibonacci (n) {
if ( n <= 1 ) {return 1};
returnFibonacci(n - 1) + Fibonacci(n - 2); } Fibonacci(10) // 89 Fibonacci(100) // timeout Fibonacci(500) // timeoutCopy the codeThe above code is a factorial function that calculates the factorial of n. At most n calls need to be saved. The complexity is O(n). If the limit is exceeded, a stack overflow problem occurs.
2.6.3 Tail recursive call optimization
Recursion is very memory intensive because you need to store hundreds of call frames at the same time, making it easy to get a “stack overflow” error. But for tail-recursion, since only one call frame exists, a stack overflow error never occurs.
function Fibonacci2 (n , ac1 = 1 , ac2 = 1) {
if( n <= 1 ) {return ac2};
return Fibonacci2 (n - 1, ac2, ac1 + ac2);
}
Fibonacci2(100) // 573147844013817200000
Fibonacci2(1000) // 7.0330367711422765e+208
Fibonacci2(10000) // Infinity
Copy the codeAs you can see, “tail-call optimization” is so important for recursive operations that some functional programming languages include it in their language specifications. The same is true for ES6, which for the first time explicitly states that all ECMAScript implementations must deploy “tail-call optimizations.” This means that when tail-recursion is used in ES6, there are no stack overruns (or timeouts due to layer upon layer recursion), which is relatively memory efficient.
2.6.4 Why does tail-recursion in this example increase the stack memory with arguments
EternallyMaybe
Get Started with ECMAScript 6
Three, heap
3.1 introduction
Heap, usually allocated by the operator (programmer) to release, if the operator does not allocate the release, the OS will recover the release. Allocation is similar to a linked list. The heap is stored in a level 2 cache.
3.2 heap memory
In addition to primitive types, JavaScript also has an Object type, which contains:
- Object
- Function
- Array
- Date
- RegExp
All types of objects are stored in the heap and are of variable size and complexity. The pointer to the Object data is stored in the stack memory space, and the actual value to which the pointer points is stored in the heap memory space.
3.3 Why is there heap memory and stack memory
Usually related to garbage collection mechanisms. In order to minimize the memory usage of the program.
When a method is executed, each method builds its own stack. Variables defined in the method are placed in the stack one by one. As the method is executed, the stack of the method is destroyed. Therefore, all variables defined in a method are placed in stack memory;
When we create an object in a program, that object is saved in the run-time data area for reuse (because objects are usually expensive to create), and this run-time data area is the heap memory. Will not end with the method of objects in the heap memory and destruction, even after the method, the object may also be another reference variables referenced (method of parameter passing is common), then the object is not destroyed, only when there is no reference to an object variables refer to it, the system of garbage collection will check the recycling it.
Fourth, the queue
4.1 introduction
A queue is an ordered set that follows the FIFO, first-in, first-out principle. The queue adds elements at the end and removes elements at the top. The most common form of queue in real life is queuing. First in line, first served. (Please line up in a civilized way. Don’t jump the queue.)
4.2 Task Queue
JavaScript is single-threaded, and single-threaded tasks are divided into synchronous and asynchronous tasks. The synchronous task waits for the main thread to execute in turn in the call stack. The asynchronous task registers the callback function in the task queue after it has the result, waits for the main thread to be idle (the call stack is empty), puts it into the execution stack and waits for the main thread to execute.
The Event loop execution is shown below, and the task queue is only part of it.
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 execute the next macro task, and so on. Until the end.
4.3 Creating a Queue (implementing the queue method)
Implement the Queue class that contains the following methods
- Enqueue (Element (s)): Adds one (or more) elements to the end of the queue.
- Dequeue (): removes the first item of the queue and returns the removed element.
- Front (): Returns the first element in the queue — the first element added, the first element removed.
- IsEmpty (): checks whether the queue isEmpty.
- Size (): Returns the length of the queue.
// The Queue class is simple to implementfunction Queue() {
letitems = []; // Add the element this.enqueue =function(element) { items.push(element); }; // Delete the element this.dequeue =function() {
returnitems.shift(); }; // Return the first element of the queue this.front =function() {
returnitems[0]; }; // check whether the queue isEmpty this.isempty =function() {
returnitems.length === 0; }; // Return queue length this.size =function() {
return items.length;
};
}
Copy the codeES6 syntax implements Queue class, uses WeakMap to save the private property items, and uses outer function (closure) to encapsulate Queue class.
let Queue1 = (function() {
const items = new WeakMap();
class Queue1 {
constructor() { items.set(this, []); } // Get the queuegetQueue() {
returnitems.get(this); } // Add element enqueue (element) {this.getqueue ().push(element); } // Delete the elementdequeue() {
returnthis.getQueue().shift(); } // Return the first element in the queuefront() {
returnthis.getQueue()[0]; } // Check whether the queue is emptyisEmpty() {
returnthis.getQueue().length === 0; } // Return the queue lengthsize() {
returnthis.getQueue().length; }}returnQueue1; }) ();Copy the code4.4 Priority Queue
Elements are added and removed based on priority. A common one is the boarding sequence at the airport. First and business class have priority over economy. Implement the priority queue and set the priority.
// Queue firstfunction PriorityQueue() {
letitems = []; // Create the element and its priority (higher priority, lower priority)functionQueueElement(element, priority) { this.element = element; this.priority = priority; } // Add elements (according to priority) this.enqueue =function(element, priority) {
letqueueElement = new QueueElement(element, priority); // Tags whether to add an element with the highest priority valuelet added = false;
for (let i = 0; i < items.length; i++) {
if (queueElement.priority < items[i].priority) {
items.splice(i, 0, queueElement);
added = true;
break; }}if(! added) { items.push(queueElement); }}; // Delete the element this.dequeue =function() {
returnitems.shift(); }; // Return the first element of the queue this.front =function() {
returnitems[0]; }; // check whether the queue isEmpty this.isempty =function() {
returnitems.length === 0; }; // Return queue length this.size =function() {
returnitems.length }; // Print the queue this.print =function() {
for (let i = 0; i < items.length; i++) {
console.log(`${items[i].element} - ${items[i].priority}`); }}; }Copy the code4.5 Circular Queue (Drum pass)
// Loop queue (drum pass)function hotPotato(nameList, num) {
letqueue = new Queue(); //{1} // The constructor is created for 4.3for(let i =0; i< nameList.length; i++) {
queue.enqueue(nameList[i]); // {2}
}
let eliminted = ' ';
while(queue.size() > 1) {// Add items before num to the end of the queue in order of priorityfor(let i = 0; i < num; i++) {
queue.enqueue(queue.dequeue()); // {3}
}
eliminted = queue.dequeue(); // {4}
console.log(eliminted + 'Eliminated from the drum pass.');
}
return queue.dequeue(); // {5}
}
let names = ['John'.'Jack'.'Camila'.'Ingrid'.'Carl'];
let winner = hotPotato(names, 7);
console.log('The winner is:' + winner);
Copy the code
- Using the queue class, create a queue.
- Put in line all current players in the drum pass flower game.
- Given a number, iterate the queue, removing an item from the beginning of the queue and adding it to the end of the queue (as in the game: you pass the flower to the person next to you and you’re safe).
- Once the number of iterations is reached, the person with the flower is eliminated.
- There is only one person left, and that person is the winner.
Reference:
- JavaScript variable — stack memory or heap memory
- JavaScript data structures – queues
- JavaScript data structures – Stacks
- The Event Loop,