JavaScript data structure (I) stack

A stack is a lifO data structure

There is no stack in JavaScript, but you can use Array to implement all the functions of a stack

Stack common operations: push, pop, stack[stack.length-1]

Definition 1.

Last in, first out, the equivalent of putting something in a container

USES:

Programming language compilers and memory to hold variables, method calls

Browser history (browser’s back button)

Function stack call

…

2. Specific operations

create

class Stack {
    constructor() {
        this.items = []; }}Copy the code

Methods:

Push (Element (s)) : Add a new element(or elements) to the top of the stack
```
push(element) {
    this.items.push(element);
}
Copy the code
```
Pop () : Removes the element at the top of the stack and returns the removed element
```
pop() {
	return this.items.pop();
}
Copy the code
```
Peek () : Returns the element at the top of the stack without making any changes to the stack (this method does not remove the element at the top of the stack, only returns it)
```
peek() {  // What was the last element added to the stack
	return this.items[this.items.length - 1];
}
Copy the code
```

IsEmpty () : Returns true if there are no elements in the stack, false otherwise

isEmpty() {  // Check whether the length of the internal array is 0
	return this.items.length === 0;
}
Copy the code

Clear () : Removes all elements in the stack

clear() {  // You can also call the pop method several times to remove all elements from the array
	this.items = [];
}
Copy the code

Size () : Returns the number of elements in the stack (similar to length)

size() {  For collections, it is best to use size instead of length
	return this.items.length;
}
Copy the code

Use 3.

const stack = new Stack();  / / create a stack
console.log(stack.isEmpty());  // The stack is empty
stack.push(5);  // Add elements to the top of the stack
console.log(stack.peek());  //5 => The last element added to the stack is 5
console.log(stack.size());    / / 1
console.log(stack.isEmpty());  //false
stack.push(8);
stack.push(11);
stack.pop(); 
stack.pop();  // Called twice to remove two elements
console.log(stack.size());  / / 1
Copy the code

4. Stack classes based on JavaScript objects

Simplest way: Use an array to store its elements

Basic structure:

class xxx {
 constructor() {
     / / structure
	}
 / / write method
}
/ / call
Copy the code

5. Protect elements inside the data structure

Using the prefix “_” and “#” to declare private attributes requires coding logic

Use Symbol in ES6

Use WeakMap in ES6

const items = new WeakMap(a);class Stack {
    construtor() {
        items.set(this[]); }push(element) {
        const s = items.get(this);
        s.push(element);
    }
    pop() {
        const s = items.get(this);
        const r = s.pop();
        returnr; }}Copy the code

6. Application

Decimal –> binary

Through the binary calculation method, it can be known that the binary result is the remainder from the highest to the lowest

decimalToBinary = (decNumber) = > {
    const remStack = new Stack();
    let number = decNumber;
    let rem;
    let binaryString = ' ';

    while (number > 0) {
        rem = Math.floor(number % 2);
        remStack.push(rem);
        number = Math.floor(number / 2);
    }

    while(! remStack.isEmpty()) { binaryString += remStack.pop().toString(); }return binaryString;
}
Copy the code

Other base conversion

function baseConverter(decNumber, base) {  //decNumber Specifies the converted number in base
    const remStack = new Stack();
    const digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';
    let number = decNumber;
    let rem;
    let baseString = ' ';

    if(! (base >=2 && base <= 36)) {
        return ' ';
    }

    while (number > 0) {
    rem = Math.floor(number % base);
    remStack.push(rem);   // Add elements to the stack
    number = Math.floor(number / base);
    }

    while(! remStack.isEmpty()) { baseString += digits[remStack.pop()];// Take the element out of the heap
    }
    return baseString;
}

console.log(baseConverter(1111111.3));
Copy the code

A stack call to a function

const func1 = () = > {
    func2();
}
const func2 = () = > {
    func3();
}
const func3 = () = > {}
Copy the code

We use Node to debug:

As you can see, functions are actually called in lifO order

That is, func3() went in last and func3() was executed first

An LeetCode

/ * * *@param {string} s
 * @return {boolean}* /
var isValid = function(s) {
    const stack = [];
    for(let i = 0; i < s.length; i++) {
        const c = s[i];
        if(c === '(' || c=== '{' || c === '[') {
            stack.push(c);
        } else {
            const t = stack[stack.length - 1]; // Top of stack element
            if(
                (t === '(' && c ===  ') ') ||
                (t === '{' && c ===  '} ') ||
                (t === '[' && c ===  '] ') 
            ) {
                stack.pop();
            } else {
                return false; }}}return stack.length === 0;
};
Copy the code