preface
Recently are learning data structure and algorithm, while the front-end directly used in the actual business development in general is not much, but these can help us understand some underlying learning, optimize the code logic, improving the quality of the code, what is more important to thinking, to help us more solid steps towards large front end. Write code, no sugar, have fun.
Data structure: the introduction of stack
A stack is a special linear table, which can only be operated on one end of the linear table. Operations are allowed at the top of the stack, but not at the bottom of the stack. The characteristics of the stack are: first in first out LIFO(last in first out), the operation of putting an element from the top of the stack is called into the stack, and the operation of removing an element is called out of the stack.
Second, JS package implementation of a stack
Js itself provides the method of array related operations, very convenient and flexible, so we will be based on the array to encapsulate a class, to achieve a simple stack structure and related operations.
Ideas:
- Create a class that creates a variable of array type to hold operation data when constructing the instance
- Class provides stack-related operation methods and properties
- Instantiate and test the action
Encapsulation is as follows:
Encapsulate a stack class
class Stack {
constructor() {
this.data = [] // Stack data variable
}
// Get the stack length using the length attribute
get length () {
return this.data.length
}
// use the isEmpty attribute to determine whether the stack isEmpty
get isEmpty () {
return this.data.length === 0
}
/ / pressure stack
push (item) {
this.data.push(item)
}
/ / out of the stack
pop () {
return this.data.pop()
}
/ / empty stack
clear () {
this.data.length = 0
}
// View the top element of the stack
peek () {
return this.data[this.data.length - 1]}}Copy the codeNow that the simple stack structure is wrapped, let’s test it:
// instantiate and perform related operations
const stack = new Stack()
console.log(stack.length) // Stack length, print 0
console.log(stack.isEmpty) // Whether the empty stack prints the result true
stack.push(1) // Push the number 1 onto the stack
stack.push(2) // push the number 2 onto the stack
stack.push(3) // Push the number 3 onto the stack
console.log(stack.peek()) // Get the print result of the top element on the stack 3
stack.pop() / / out of the stack
console.log(stack.length) // Stack length, print result 2
console.log(stack.isEmpty) // Whether the empty stack prints the result false
stack.clear()
console.log(stack.length) // Stack length, print 0
console.log(stack.isEmpty) // Whether the empty stack prints the result true
Copy the codeThree, stack related classical problem solution
1. The rationality of the order of elements out and onto the stack.
Title: The order of loading is 1, 2, 3, 4, 5, then the order of unloading is 4, 5, 3, 2, 1 is reasonable?
// Solution: Whether it is reasonable to start with the order of the stack, we can simulate by instantiating a stack structure
const stack = new Stack()
// If the first stack is 4, then 4 must be at the top of the stack.
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)
stack.pop() / / stack 4
stack.push(5)
stack.pop() / / the stack 5
stack.pop() / / out 3 stack
stack.pop() / / two stacks
stack.pop() / / 1 stack
// Therefore, the above stack order is reasonable
Copy the code2, through the stack structure to achieve the base conversion
Problem, implement decimal integer conversion to binary, octal, hexadecimal.
Analysis: Decimal integers are converted to binary integers using the “mod 2, reverse order” method. Specific approach is: use 2 to divide decimal integer, can get a quotient and remainder; Then divide the quotient by 2, and another quotient and remainder will be obtained, and so on until the quotient is less than 1. Then, the remainder obtained first as the lowest significant bit of the binary number, and the remainder obtained later as the highest significant bit of the binary number are arranged in order.
The same goes for octal and hexadecimal.
The following is achieved through the stack structure:
/** * Convert decimal integers to other base methods *@param Num [Number] The decimal integer *@param Base [Number] The base to convert; Options are: 2-binary (default); 8-octal; 16-hexadecimal */
const decimalcConversion = (num, base = 2) = > {
// Determine which base to convert to
const baseList = [2.8.16]
if (baseList.includes(base)) {
// Create a stack instance
const stack = new Stack()
// push the remainder into the stack
while (num > 0) {
stack.push(num % base)
num = Math.floor(num / base)
}
// Unstack to a string
let string = ' '
while(! stack.isEmpty) {let item = stack.pop()
// For hexadecimal processing
if (item >= 10) {
item = ['a'.'b'.'c'.'d'.'e'.'f'][item - 10]
}
string += item
}
// Returns the converted base string value
return string
} else {
throw new Error('Please enter the correct base number')
}
}
decimalcConversion(100) // Binary 1100100
decimalcConversion(100.8) // octal 144
decimalcConversion(100.16) // Hexadecimal 64
decimalcConversion(300) // Binary 100101100
decimalcConversion(300.8) // octal 454
decimalcConversion(300.16) // Hexadecimal 12c
Copy the codeReturn the minimum value of the element in the stack
Analysis: After the element is pushed, it is very difficult to find the minimum value directly from the stack, because the stack structure is mainly the two core operations on the stack, so to obtain the minimum value, you can create a new array to store.
You can inherit from the stack above, adding an array to hold the minimum value and a method to get the minimum value.
The code is as follows:
// Inherits the stack encapsulated above
class MinStack extends Stack {
constructor () {
super(a)this.minData = [] // Store the minimum value in the stack
}
// Get the smallest element in the stack
get minimum () {
return this.minData[this.minData.length - 1]}// Override the push method
push (item) {
let min = 0
if (this.data.length === 0) {
// When the first element comes in
min = item
} else {
// Otherwise, the top element is compared with the pushed element, and the smaller element is minData
const minimum = this.minimum
min = item <= minimum ? item : minimum
}
this.data.push(item)
this.minData.push(min)
}
// Override the pop method
pop () {
this.minData.pop()
return this.data.pop()
}
}
const stack = new MinStack()
stack.push(2)
stack.push(30)
stack.push(1)
stack.push(88)
console.log(stack.minimum) / / 1
stack.pop()
stack.pop()
console.log(stack.minimum) / / 2
Copy the codeOf course, the above implementation is mainly based on the characteristics of the “stack” structure, providing a way to solve the problem, in order to exercise the diversity and flexibility of thinking.
In fact, since we simulate the stack structure through the array of JS, we can get the minimum value directly by manipulating the original array:
Encapsulate a stack class
class Stack {
constructor() {
this.data = [] // Stack data variable
}
// Get the smallest element in the stack
get minimum () {
return Math.min(... this.data) }// Other attributes and methods. }Copy the codeIn addition to the minimum, the same is true for obtaining the maximum value in the stack structure.