JavaScript数据结构和算法----栈

前言　

　　栈是一种遵循后进先出（LIFO）原则的有序集合，新添加的或待删除的元素都保存在栈的末尾，称作栈顶，另外一端就叫栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。可以想象桌上的一叠书，或者厨房里的堆放的盘子。

一、栈的创建

可以创建一个类来表示栈

//1、创建一种数据结构来保存栈里面的数据，这里选择数组

//2、声明一些栈的方法

    // push(element(s)) ： 添加一个或一些元素到栈顶

    // pop() : 移除栈顶的元素，同时返回被移除的元素。

    // peek() : 返回栈顶的元素，仅仅是返回，不做任何修改。

    // isEmpty() : 如果栈里面没有任何元素就返回true,否者为false。

    // clear() : 清除栈里面的元素。

    // size() : 返回栈里面的个数。

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.clear = function(){

        items = [];

    }

    this.size = function(){

        return items.length;

    }

    this.print = function(){

        console.log(items.toString());

    }

}

//使用栈

var stack = new Stack();

console.log(stack.isEmpty());//true

stack.push(100);

stack.push(200);

console.log(stack.isEmpty());//false

console.log(stack.size());//2

console.log(stack.peek());

stack.pop();

stack.print();//100

二、栈的应用

十进制转二进制

//算法描述：将该十进制的数和2整除，或者每次的余数（0或1），直到结果为0位置。比图10的二进制为：

    // 10/2 = 5 ,余数 0

    // 5/2 = 2  ,余数 1

    // 2/2 = 1  ,余数 0

    // 1/2 = 0  ,余数 1

    // 10的二进制表示为：0101

function diviceBy2(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(diviceBy2(10));   //1010

console.log(diviceBy2(520));  //1000001000

console.log(diviceBy2(1000)); //1111101000

十进制转成其他进制

function diviceByBase(decNumber, base){

    var remStack = new Stack(),

        rem,

        baseString = '',

        digits = '0123456789ABCDEF';//8进制是余数是（0-7）16进制是（0-9A-F）

    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(diviceByBase(100345, 2));  // 11000011111111001

console.log(diviceByBase(100345, 8));  // 303771

console.log(diviceByBase(100345, 16)); // 187F9

巴特西

JavaScript数据结构和算法----栈

最新文章

热门文章