Algorithms and Data Structures in JS — Stack

define

A stack, also known as a stack, is a data structure similar to a list, but more efficient, because elements in the stack can only be accessed through the top of the stack, and data can only be added or removed at the top of the stack, following a last-in-first-out (LIFO) principle.

Stack properties and methods

The realization of the stack

function Stack () {
    this.dataStore = [];    // initialize to null
    this.top = 0;           // Record the top position of the stack
    this.pop = function() { / / out of the stack
    	return this.dataStore[--this.top];
    };         
    this.push = function(element) { / / into the stack
    	this.dataStore[this.top++]=element;
    };               
    this.peek = function() { // View the top element of the stack
     	if( this.top > 0 ) return this.dataStore[this.top-1];
    	return 'Empty';
    };                
    this.length = function() { // Check the total number of elements in the stack
    	return this.top;
    }; 
    this.clear = function() { / / empty stack
    	delete this.dataStore;
    	this.dataStore = [];
    	this.top = 0;
    };
}
Copy the code

Case 1: Conversion between number systems

To convert a number from one number system to another using a stack. For example, to convert the number n to base B, the following algorithm can be used (this algorithm only applies to base 2-9 cases)

1. The highest bit is N % b, directly pressed into the stack;
2. Use math.floor (n/b) instead of n;
3. Repeat the above steps until n is 0 and there is no remainder;
4. By popping the elements on the stack until the stack is empty and placing them in order, you get the transformed form

function baseConversion(num , base) {
	var s = new Stack();
    while(num! = =0) {
    	s.push(num % base);
        num = Math.floor(num/base);
    }
    var converted = ' ';
    while (s.length() > 0){
        converted += s.pop();
    }
    return converted;
}
Copy the code

Case 2: Determine if a string is palindrome

A palindrome is a string that gives the same result when written backwards as when written backwards. For example, the word ‘level’, ‘racecar’ is a palindrome, as is the number 1001. We push the string into the stack from left to right, so that the characters after the string is reversed are stored in the stack, and then we push the string out of the stack. By comparing whether the string after the stack is equal to the original string, we can determine whether the string is a palindrome.

// Palindrome judgment

function isPalindrome ( word ) {
    var s = new Stack();
    for( var i = 0 ; i < word.length ; i ++ ){
        s.push( word[i] );
    }
    var rword = ' ';
    while( s.length() > 0 ){
        rword += s.pop();
    }

    if( word == rword ){
        return true;
    }else{
        return false; }}console.log( isPalindrome('level'))// true
console.log( isPalindrome('1001'))// true
console.log( isPalindrome('word'))// false
Copy the code

Another implementation

function isPalindrome ( word ){
    return String(word).split(' ').reverse().join(' ') == word ? true : false;
}
Copy the code