JSImplement stack structure
One, foreword
A stack, also known as a stack, is a linear table with limited operations. A linear table that restricts insertions and deletions to only the end of the table, is a data structure that restricts insertions and deletions to only one end, the end that is allowed is called the top of the stack, the end that is not allowed is called the bottom of the stack. The other end is called the bottom of the stack. Inserting a new element into a stack, also known as a push, push, or push, is to put the new element on top of the top element of the stack, making it a new top element; Removing an element from a stack, also known as making a stack or making a stack, is to remove the top element of the stack so that its adjacent elements become the new top element.
If you want to use JS to implement the stack structure, you need to ensure that the implementation of the stack has the following basic functions:
-
Push new element
-
Pop removes the top element of the stack
-
Peek returns the top element of the stack
-
The clear empty stack
-
Size Size of the stack, that is, the number of elements
-
IsEmpty whether the stack isEmpty
Once you know what you want to implement, you can start implementing the stack
Two, stack implementation
1. Realization of stack basic functions
class Stack {
constructor() {
this.items = []
}
// Add element
push(el) {
this.items.push(el)
}
// Remove the element at the top of the stack and return its value
pop() {
return this.items.pop()
}
// Return the top element of the stack
peek() {
return this.items[this.items.length - 1]}/ / empty stack
clear() {
this.items = []
}
// Stack size
size() {
return this.items.length
}
// Whether the stack is empty
isEmpty() {
return this.items.length === 0}}const stack = new Stack()
stack.push(1)
stack.push(2)
stack.push(3)
console.log(stack)
stack.items.push(4)
console.log(stack)
Copy the codeAlthough the above code implements the basic functions of the stack, it is obvious that the outside world can actually access the items variable directly and then modify it directly. This is obviously unreasonable. Normally, the outside world can only modify the stack through the methods provided by the stack, but not directly access the stack. The items variable (that is, the stack array) needs to be privatized so that the outside world cannot access it directly.
2. SymbolPrivatize stack arrays?
const Stack = (function () {
const _items = Symbol(a)return class {
constructor() {
this[_items] = []
}
// Add element
push(el) {
this[_items].push(el)
}
// Remove the element at the top of the stack and return its value
pop() {
return this[_items].pop()
}
// Return the top element of the stack
peek() {
return this[_items][this[_items].length - 1]}/ / empty stack
clear() {
this[_items] = []
}
// Stack size
size() {
return this[_items].length
}
// Whether the stack is empty
isEmpty() {
return this[_items].length === 0}}}) ()const stack = new Stack()
stack.push(1)
stack.push(2)
stack.push(3)
console.log(stack)
stack[_items].push(4) // Uncaught ReferenceError: _items is not defined
console.log(stack)
Copy the codeYou can see that it is not possible to access the stack array directly through stack[_items]. But that doesn’t mean other methods can’t work:
const key = Object.getOwnPropertySymbols(stack)[0]
stack[key].push(4)
console.log(stack)
Copy the codeThe getOwnPropertySymbols method is provided on the Object. This method retrives the key name of the Object’s property named symbol. This method retrives the stack’s symbol value, thus directly accessing the stack.
3. WeakMapMake the stack array private
const Stack = (function () {
const _items = new WeakMap(a)return class {
constructor() {
_items.set(this[])},// Add element
push(el) {
_items.get(this).push(el)
}
// Remove the element at the top of the stack and return its value
pop() {
return _items.get(this).pop()
}
// Return the top element of the stack
peek() {
return _items.get(this)[_items.get(this).length - 1]}/ / empty stack
clear() {
_items.set(this[])},// Stack size
size() {
return _items.get(this).length
}
// Whether the stack is empty
isEmpty() {
return _items.get(this).length === 0}}}) ()const stack = new Stack()
stack.push(1)
stack.push(2)
stack.push(3)
console.log(stack.size()) / / 3
console.log(stack.isEmpty()) // false
stack.clear()
console.log(stack.size()) / / 0
console.log(stack.isEmpty()) // true
Copy the code4. The stack implements decimal conversion
In js, provides the Number. The prototype. The toString method to convert decimal to other base, we can also use his stack this kind of data structure, the transition of decimal.
1) Convert decimal to binary
10/2 = 5, remainder 0, 5/2 = 2, remainder 1, 2/2 = 1, remainder 0, 1/2 = 0, remainder 1Copy the codeSo the decimal number 10 is converted to binary, so it becomes 1010. You can see that this structure is a stack, and the remainder is pushed one by one, and then the remainder is taken one by one from the top of the stack, and then the combination is done to get the binary, and then the code is used to implement it:
function baseConversionBy2 (num) {
const stack = new Stack()
let res = ' '
while (num > 0) {
stack.push(num % 2)
num = Math.floor(num / 2)}while(! stack.isEmpty()) { res += stack.pop() }return res
}
console.log(baseConversionBy2(10)) / / 1010
Copy the code2) Convert decimal to octal
32/8 is equal to 4, and the remainder is 0. 4/8 is equal to 0, and the remainder is 4Copy the codeConverting to octal is 40 code as follows:
function baseConversionBy8 (num) {
const stack = new Stack()
let res = ' '
while (num > 0) {
stack.push(num % 8)
num = Math.floor(num / 8)}while(! stack.isEmpty()) { res += stack.pop() }return res
}
console.log(baseConversionBy8(32)) / / 40
Copy the code3) Convert from decimal to hexadecimal
960/16 = 60, remainder 0 60/16 = 3, remainder 12 3/16 = 0, remainder 3Copy the codeHexadecimal is different, when the remainder is greater than 9, use letters instead, 10,11,12,13,14,15 correspond to a,b,c,d,e,f respectively, so here converted to hexadecimal 3c0, the code implementation is as follows:
function baseConversionBy16 (num) {
const stack = new Stack()
let res = ' ',
digits = '0123456789abcde'
while (num > 0) {
stack.push(num % 16)
num = Math.floor(num / 16)}while(! stack.isEmpty()) { res += digits[stack.pop()] }return res
}
console.log(baseConversionBy16(960)) // 3c0
Copy the code4) Convert decimal to other bases
As you can see, the decimal conversion to 2, 8, and hexadecimal is regular, so the above methods can be combined into one method. The code is as follows:
function baseConversionByAuto (num, base) {
const stack = new Stack()
let res = ' ',
digits = '0123456789abcde'
while (num > 0) {
stack.push(num % base)
num = Math.floor(num / base)
}
while(! stack.isEmpty()) { res += digits[stack.pop()] }return res
}
console.log(baseConversionByAuto(10.2)) / / 1010
console.log(baseConversionByAuto(32.8)) / / 40
console.log(baseConversionByAuto(960.16)) // 3c0
Copy the code5. Stack judgment balance brackets
Balance bracket
"{[()]}" belongs to balance "{bracket ([)]}" does not belong to balance the brackets "{{/}}" does not belong to balance the brackets "{{([]) (#)} ()}" belongs to balance the open bracket = '{[(' close =')]} 'Copy the codeThe left half of open is pushed on the stack in the same order as the right half of close
Code implementation:
function check(str) {
const stack = new Stack()
const open = "{[("
const close = "})"
let balanced = true
let index = 0
let symbol
let top
while (index < str.length && balanced) {
symbol = str[index]
if (open.includes(symbol)) {
stack.push(symbol)
} else {
top = stack.pop()
if(open.indexOf(top) ! == close.indexOf(symbol)) { balanced =false
}
}
index ++
}
if (balanced && stack.isEmpty()) {
return true
}
return false
}
console.log(check("{[()]}")) // true
console.log(check("{([]}")) // false
console.log(check("{{/}}")) // false
console.log(check("{{([] [])}} ()")) // true
Copy the code