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(this.toString());
    }
}
//使用
var stack = new Stack();
stack.print(); //输出true
...

function dec2bin(dec){
    var rs = new Stack(), //余数数组
        rem,    //余数
        s = ''; //二进制字符串
    while(dec > 0){
        //由于js的数字类型不区分整数or浮点数
        //所以需要使用Math.floor仅返回除数的整数部分
        rem = Math.floor(dec % 2);
        rs.push(rem);
        dec = Math.floor(dec / 2);
    }
    while(!rs.isEmpty()){
        //将数组中的元素出栈并转换为字符串连接
        s += rs.pop().toString();
    }

    return s;
}

//若需转化为任意进制，则需添加一个参数表示基数
function dec2base(dec,base){
    var rs = new Stack(), //余数数组
        rem,    //余数
        s = '', //二进制字符串
        digits = '0123456789ABCDEF'; //将数字转化为对应字符
    while(dec > 0){
        //由于js的数字类型不区分整数or浮点数
        //所以需要使用Math.floor仅返回除数的整数部分
        rem = Math.floor(dec % base);
        rs.push(rem);
        dec = Math.floor(dec / base);
    }
    while(!rs.isEmpty()){
        //将数组中的元素出栈并转换为字符串连接
        s += digits[rs.pop()];
    }

    return s;
}

function Queue(){
    var items = [];
    this.enqueue = function(element){
        items.push(element);
    }
    this.dequeue = function(){
        return items.shift();
    }
    this.front = function(){
        return items[0];
    }
    this.isEmpty = function(){
        return items.length == 0;
    }
    this.size = function(){
        return items.length;
    }
    this.clear = function(){
        items = [];
    }
    this.print = function(){
        console.log(this.toString());
    }
}
//使用
var q = new Queue();
q.print();

function PriorityQueue(){
    var items = [];
    //内部类，将优先级和元素数值保存为一个类
    function QueueElement(element, priority){
        this.element = element;
        this.priority = priority; //值越大，优先级越低
    }

    this.enqueue = function(element,priority){
        var qe = new QueueElement(element,priority); //新生成一个元素对象，保存数值和优先级
        if(this.isEmpty()){
            items.push(qe); //数组为空则直接添加到数组中
        }else{
            var added = false;
            for(var i =0; i < items.length; ++i){
                //优先级相同的，也是先进先出
                if(qe.priority < items[i].priority){ //比较优先级
                    items.splice(i, 0, qe); //插入到找到元素之前
                    added = true;
                    break;
                }
            }
            if(!added){ //若added还是false，表示当前的元素优先级是最低的，
                items.push(qe);
            }
        }
    }
    //...其他相同
}

//使用
var pq = new PriorityQueue();
pq.enqueue('John',2);
pq.enqueue('Jack',1);
pq.enqueue('Came',1);
pq.print(); //Jack,Came,John

function hotPotato(list, num){
    var q = new Queue();
    for(var i = 0; i < list.length; ++i){
        q.enqueue(list[i]); //将名字数组中的名字加入队列
    }

    var eliminated = '';
    while(q.size() > 1){
        for(i = 0; i < num; ++i){
            q.enqueue(q.dequeue()); //未淘汰则继续加入队列
        }
        eliminated = q.dequeue(); //将淘汰的记录下来
        console.log(eliminated + '淘汰了');
    }
    return q.dequeue(); //最后返回剩下的1个人
}

//测试
var names = ['A','B','C','D','E'];
var win = hotPotato(names, 7);
console.log(win + ' Win'); // A Win

function Dictionary() {
    var items = {};
}

function HashTable() {
    var table = [];
}

var loseloseHashCode = function (key) {
    var hash = 0; //{1}
    for (var i = 0; i < key.length; i++) { //{2}
        hash += key.charCodeAt(i); //{3}
    }
    return hash % 37; //{4}
};

var djb2HashCode = function (key) {
    var hash = 5381; //{1}
    for (var i = 0; i < key.length; i++) { //{2}
        hash = hash * 33 + key.charCodeAt(i); //{3}
    }
    return hash % 1013; //{4}
};

function MinCoinChange(coins){
    var coins = coins; //coins为面额数组，如[1,5,10,25]
    var cache = {}; //保存已经计算过的，不重复计算

    this.makeChange = function(amount){
        var self = this;
        if(!amount){ //若amount非正，则返回空数组
            return [];
        }
        if(cache[amount]){ //若存在缓存，则直接返回缓存
            return cache[amount];
        }
        var min = [], newMin, newAmount;
        for(var i = 0; i < coins.length; ++i){ //对每一面额都计算newAmount
            var coin = coins[i];
            newAmount = amount - coin;
            if(newAmount >= 0){ //若为正，则也计算newAmount的找零结果
                newMin = self.makeChange(newAmount);
            }
            if(newAmount >= 0 &&
            (newMin.length < min.length - 1 || !min.length) &&
            (newMin.length || !newAmount)){ //判断newAmount是否有效
                min = [coin].concat(newMin);
                console.log('new min ' + min + ' for ' + amount);
            }
        }
        return (cache[amount] = min);
    }
}

//使用
var m = new MinCoinChange([1,5,10,25]);
console.log(m.makeChange(36));

function MinCoinChange(coins){
    var coins = coins; //{1}
    this.makeChange = function(amount) {
        var change = [],
        total = 0;
        for (var i=coins.length; i>=0; i--){ //{2}
            var coin = coins[i];
            while (total + coin <= amount) { //{3}
                change.push(coin); //{4}
                total += coin; //{5}
            }
        }
        return change;
    };
}

var minCoinChange = new MinCoinChange([1, 5, 10, 25]);
console.log(minCoinChange.makeChange(36));