欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2024-03-16 15:56:28
...

前言 

  栈是一种遵循后进先出(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