第3章 栈

栈

function Stack() {

    let 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());
    };

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

more1

 let _items = Symbol();

class Stack2 {

    constructor () {
        this[_items] = [];
    }

    push(element){
        this[_items].push(element);
    }

    pop(){
        return this[_items].pop();
    }

    peek(){
        return this[_items][this[_items].length-1];
    }

    isEmpty(){
        return this[_items].length == 0;
    }

    size(){
        return this[_items].length;
    }

    clear(){
        this[_items] = [];
    }

    print(){
        console.log(this.toString());
    }

    toString(){
        return this[_items].toString();
    }
}

more2

let Stack3 = (function () {

    const items = new WeakMap();

    class Stack3 {

        constructor () {
            items.set(this, []);
        }

        push(element){
            let s = items.get(this);
            s.push(element);
        }

        pop(){
            let s = items.get(this);
            let r = s.pop();
            return r;
        }

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

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

        size(){
            let s = items.get(this);
            return s.length;
        }

        clear(){
            items.set(this, []);
        }

        print(){
            console.log(this.toString());
        }

        toString(){
            return items.get(this).toString();
        }
    }

    return Stack3;
})();

es6

class Stack {

    constructor () {
        this.items = [];
    }

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

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

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

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

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

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

    print(){
        console.log(this.toString());
    }

    toString(){
        return this.items.toString();
    }
}

使用栈

let stack = new Stack3();
 console.log(stack.isEmpty()); //outputs true
 stack.push(5);
 stack.push(8);
 console.log(stack.peek()); // outputs 8
 stack.push(11);
 console.log(stack.size()); // outputs 3
 console.log(stack.isEmpty()); //outputs false
 stack.push(15);
 stack.pop();
 stack.pop();
 console.log(stack.size()); // outputs 2
 stack.print(); // outputs [5, 8]


//how to ensure true privacy
//in case using Stack 2 uncomment code below
/*let objectSymbols = Object.getOwnPropertySymbols(stack);

 console.log(objectSymbols.length); // 1
 console.log(objectSymbols);        // [Symbol()]
 console.log(objectSymbols[0]);     // Symbol()
 stack[objectSymbols[0]].push(1);
 stack.print(); //5, 8, 1*/

BalancedSymbols

 function parenthesesChecker(symbols){

    let stack = new Stack(),
        balanced = true,
        index = 0,
        symbol, top,
        opens = "([{",
        closers = ")]}";

    while (index < symbols.length && balanced){
        symbol = symbols.charAt(index);
        if (opens.indexOf(symbol) >= 0){
            stack.push(symbol);
            console.log(`open symbol - stacking ${symbol}`);
        } else {
            console.log(`close symbol ${symbol}`);
            if (stack.isEmpty()){
                balanced = false;
                console.log('Stack is empty, no more symbols to pop and compare');
            } else {
                top = stack.pop();
                //if (!matches(top, symbol)){
                if (!(opens.indexOf(top) === closers.indexOf(symbol))) {
                    balanced = false;
                    console.log(`poping symbol ${top} - is not a match compared to ${symbol}`);
                } else {
                    console.log(`poping symbol ${top} - is is a match compared to ${symbol}`);
                }
            }
        }
        index++;
    }
    if (balanced && stack.isEmpty()){
        return true;
    }
    return false;
}

console.log(parenthesesChecker('{([])}')); //true
console.log(parenthesesChecker('{{([][])}()}')); //true
console.log(parenthesesChecker('[{()]')); //false

从十进制到二进制

//233 == 11101001
//2x(10x10) + 3x(10) + 3x(1)

function divideBy2(decNumber){

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

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

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

    return binaryString;
}

console.log(divideBy2(233));
console.log(divideBy2(10));
console.log(divideBy2(1000));

/*
    The folow algorithm converts from base 10 to any base
 */
function baseConverter(decNumber, base){

    var remStack = new Stack(),
        rem,
        baseString = '',
        digits = '0123456789ABCDEF';

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

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

    return baseString;
}

console.log(baseConverter(100345, 2));
console.log(baseConverter(100345, 8));
console.log(baseConverter(100345, 16));

汉诺塔

function towerOfHanoi(n, from, to, helper){

    if (n > 0){
        towerOfHanoi(n-1, from, helper, to);
        to.push(from.pop());
        console.log('-----');
        console.log('Source: ' + from.toString());
        console.log('Dest: ' + to.toString());
        console.log('Helper: ' + helper.toString());
        towerOfHanoi(n-1, helper, to, from);
    }
}

var source = new Stack();
source.push(3);
source.push(2);
source.push(1);

var dest = new Stack();
var helper = new Stack();

towerOfHanoi(source.size(), source, dest, helper);

source.print();
helper.print();
dest.print();