This article mainly introduces how to use JavaScript to implement a stack, which has certain reference value. Now I share it with you. Friends in need can refer to it

What is a stack

How to implement a stack in JavaScript

#The stack is an ordered collection that follows the last-in-first-out (LIFO) principle.
Newly added or to be deleted elements are stored at the end of the stack, which is called the top of the stack, and the other end is called the bottom of the stack.
In the stack, new elements are close to the top of the stack, and old elements are close to the bottom of the stack

Real-life examples

You can also find many examples of stacks in life. For example, among the plates stacked in the kitchen, the ones stacked on top are always used first; when the content of the input box is deleted, the last input is always deleted first; the bullets in the magazine are fired first as they are loaded later. ....

Manually implement a stack

First, create a class to represent the stack

function Stack () { }

Copy after login

We need to choose a data structure to save the elements in the stack, you can Select the array

function Stack(){
    var items = [];     //用来保存栈里的元素
}

Copy after login

Next, add some methods to the stack

push(element(s));   //添加新元素到栈顶
pop();              //移除栈顶的元素，同时返回被移除的元素
peek();             //返回栈顶的元素，不对栈做任何修改
isEmpty();          //如果栈里没有任何元素就返回true，否则false
clear();            //移除栈里的所有元素
size();             //返回栈里的元素个数,类似于数组的length属性

Copy after login

The first method we need to implement ispush. Used to add new elements to the stack, one thing is very important: this method only adds to the top of the stack, which is the end of the stack. Therefore, you can write like this:

this.push = function (element) {
    items.push(element);
}

Copy after login

Using the push method of the array, you can add new elements to the end of the top of the stack.

Next, implement the pop method to remove elements from the stack. The stack follows the LIFO (last in, first out) principle. What is removed is the last element added. Therefore, you can use the pop method of the array.

this.pop = function () {
    return items.pop();
}

Copy after login

In this way, this stack naturally follows the LIFO principle

Now, let’s add additional auxiliary methods to this stack.

If you want to know what the last element added to the stack is, you can use the peek method. This method will return the element on the top of the stack

this.peek = function () {
    return items[items.length-1];
}

Copy after login

Because the class uses an array to save the elements, so here to access the last element of the array use length-1

Next The method to be implemented is isEmpty. If the stack is empty, it returns true, otherwise it returns false:

this.isEmpty = function () {
    return items.length == 0;
}

Copy after login

Using the isEmpty method, you can simply determine whether the stack is empty.

Similar to the length property of the array, we can also implement the length of the stack.

this.size = function () {
    return items.length;
}

Copy after login

Because the stack uses an array internally to store elements, the length of the array is the length of the stack.

Implement the clear method. The clear method is used to clear all elements in the stack. The simplest implementation method is:

this.clear = function () {
    items = [];
}

Copy after login

In fact, it is also possible to call the pop method multiple times, but it is not as simple and fast as this method.

Finally, in order to check the contents of the stack, you need to implement an auxiliary method: print. It will output all the elements in the stack to the console:

this.print = function () {
    console.log(items.toString());
}

Copy after login

At this point, we have completely created a stack!

The complete code of the stack

function Stack(){

    var items = [];     //用来保存栈里的元素

    this.push = function (element) {
        items.push(element);
    }

    this.pop = function () {
        return items.pop();
    }

    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 = [];
    }

    this.print = function () {
        console.log(items.toString());
    }
}

Copy after login

Using the Stack class

The stack has been created, let’s test it

First, initialize the Stack class. Then, verify whether the stack is empty

var stack = new Stack();
console.log(stack.isEmpty());         //控制台输出true

Copy after login

Next, add an element to the stack:

stack.push(5);
stack.push(8);

Copy after login

If you call the peek method, it will obviously output 8, because it is on the top of the stack Element:

console.log(stack.peek());            //控制台输出8

Copy after login

Add another element:

stack.push(11);
console.log(stack.size());            //控制台输出3

Copy after login

We added another 11 to the stack. If the size method is called, the output is 3 because there are three elements on the stack (5, 8, and 11). If you call the isEmpty method at this time, you will see false output (because the stack is not empty at this time). Finally, add another element to it:

stack.push(15);

Copy after login

Then, call the pop method twice to remove two elements from the stack:

stack.pop();
stack.pop();
console.log(stack.size());            //控制台输出2
stack.print();                        //控制台输出[5,8]

Copy after login

At this point, the functional test of the entire stack is completed.

Use the stack to solve the problem

Use the stack to complete the hexadecimal conversion.

In real life, we mainly use decimal system, but in computing science, binary system is very important, because all contents in the computer are represented by binary numbers 0 and 1. Computer classes in universities will first teach base conversion. Take binary as an example:

How to implement a stack in JavaScript

function pideBy2 (decNumber) {

    var remStack = new Stack(),
    rem,
    binaryString = '';

    while (decNumber>0) {  //{1}
        rem = Math.floor(decNumber % 2);  //{2}
        remStack.push(rem);  //{3}
        decNumber = Math.floor(decNumber / 2);  //{4}
    }

    while (!remStack.isEmpty()) {  //{5}
        binaryString += remStack.pop().toString();
    }

    return binaryString;
}

Copy after login

In this code, when the result meets the condition of being divisible by 2, (line {1}), we will get the current result and The remainder of 2 is placed on the stack (lines {2}, {3}). Then let the result be evenly divided by 2 (line {4})

Note: JavaScript has a numeric type, but it does not distinguish between integers and floating point numbers. Therefore, use the Math.floor function to make the division operation return only the integer part.

Finally, use the pop method to remove all elements from the stack, and concatenate the popped elements into strings (line {5}).

Test it:

console.log(pideBy2(520));      //输出1000001000
console.log(pideBy2(10));       //输出1010
console.log(pideBy2(1000));     //输出1111101000

Copy after login

Next, you can easily modify the above algorithm so that it can convert decimal to any base. In addition to converting decimal numbers and divisibility by 2 into binary numbers, you can also pass in other arbitrary bases as parameters, just like the following algorithm:

function baseConverter (decNumber, base) {

    var remStack = new Stack(),
    rem,
    baseString = '';
    digits = '0123456789ABCDEF';     //{6}

    while (decNumber>0) {  
        rem = Math.floor(decNumber % base);
        remStack.push(rem);  //{3}
        decNumber = Math.floor(decNumber / base);
    }

    while (!remStack.isEmpty()) {
        baseString += digits[remStack.pop()];  //{7}
    }

    return baseString;
}

Copy after login

在将十进制转成二进制时，余数是0或1；在将十进制转成八进制时，余数时0-8之间的数；但是将十进制转成十六进制时，余数时0-9之间的数字加上A、B、C、D、E、F（对应10、11、12、13、14和15）。因此，需要对栈中的数字做个转化才可以（行{6}、{7}）。

来测试一下输出结果：

console.log(baseConverter(1231,2));      //输出10011001111
console.log(baseConverter(1231,8));      //输出2317
console.log(baseConverter(1231,16));     //输出4CF

Copy after login

显然是正确的。