1. The stack
The characteristics of
Ordered collections that follow the last in, first out (LIFO) principle.
implementation
Array based implementation
class Stack {
constructor() {
this.items = []
}
// Add elements to the top of the stack
push(element) {
this.items.push(element)
}
// Remove the element from the top of the stack
pop() {
return this.items.pop()
}
// Look at the top of the stack
peek() {
return this.items[this.items.length - 1]}// Check whether the stack is empty
isEmpty() {
return this.items.length === 0
}
// Get the stack length
size() {
return this.items.length
}
// Clear the stack elements
clear() {
this.items = []
}
}
Copy the code
Object-based implementation
Implementing a stack based on an array is the easiest way to do it, but to use it, we need to iterate through the array until we find the element we want, and it takes O(n) time; In addition, an array is an ordered collection of elements. To keep the elements in order, it takes up more memory space. So we can add a count attribute and use an object to implement the stack structure.
class Stack {
constructor() {
this.count = 0
this.items = {}
}
push(element) {
this.items[this.count++] = element
}
pop() {
if (this.isEmpty()) {
return undefined
}
const result = this.items[--this.count]
delete this.items[this.count]
return result
}
peek() {
if (this.isEmpty()) {
return undefined
}
return this.items[this.count - 1]}isEmpty() {
return this.count === 0
}
size() {
return this.count
}
clear() {
this.count = 0
this.items = {}
}
// Customize the toString method
toString() {
if (this.isEmpty()) {
return ' '
}
let result = ' '
for (let i = 0; i < this.count; i++) {
result += `The ${this.items[i]}${i === this.count - 1 ? ' ' : ', '}`
}
return result
}
}
Copy the code
Protect the elements inside the data structure
For stack data structures, make sure that elements are added only to the top of the stack, not to the bottom of the stack or anywhere else. However, the items and count properties declared in the Stack class are not protected and can be modified at will.
const stack = new Stack()
Object.getOwnPropertyNames(stack) // [ 'count', 'items' ]
Object.keys(stack) // [ 'count', 'items' ]
console.log(stack.items, stack.count) / / {}, 0
Copy the code
We want users of the Stack class to have access only to the methods that we expose in the class
Implement the class using ES6’s scoped Symbol
ES6 adds the Symbol primitive data type, which represents a unique value that we use as a property of the object.
const _ items = Symbol('stackItem')
class Stack {
constructor() {
this.count = 0
this[_items] = {}
}
// self-defining function
// Add a print method
print() {
return this[_items]
}
}
Copy the code
This way also can’t avoid attribute is accessed, while using the Symbol type to avoid being Object. The keys () and Object getOwnPropertyNames () method to access, But ES6 provides the same Object. GetOwnPropertySymbols () method to get all the Symbol attributes
const stack = new Stack()
Object.getOwnPropertyNames(stack) // [ 'count' ]
Object.getOwnPropertySymbols(stack) // [ Symbol(stackItem) ]
let objectSymbol = stack[Object.getOwnPropertySymbols(stack)[0]] // Get the _items object
objectSymbol[1] = 2
stack.print() // {'1': 2}
Copy the code
Use ES6 WeakMap implementation class
The idea is to save an array by WeakMap, and the next steps are to use the GET function to take out the array for operation; The disadvantages are that the code is not readable, and you cannot inherit private properties when you extend the class.
const items = new WeakMap(a)class Stack {
constructor() {
items.set(this[])},push(element) {
const s = items.get(this)
s.push(element)
}
pop() {
const s = items.get(this)
const result = s.pop()
return result
}
peek() {
const s = items.get(this)
return s[s.length - 1]}isEmpty() {
const s = items.get(this)
return s.length === 0
}
size() {
const s = items.get(this)
return s.length
}
clear() {
items.set(this[])}},Copy the code
Actual Usage Scenario
Transformation into the system
function baseConverter(decNumber, base = 2) {
const remStack = new Stack()
const digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
let number = decNumber
let baseString = ' '
/ / 2-36 into the system
if (base < 2 || base > 36) {
return ' '
}
// Take the modulo of decNumber
while (number > 0) {
let rem = Math.floor(number % base)
remStack.push(rem)
number = Math.floor(number / base)
}
// Take the reverse operation
while(! remStack.isEmpty()) { baseString += digits[remStack.pop()] }return baseString
}
Copy the code