javascript ·

JavaScript创建栈结构

在数据结构中栈是一种遵从后进先出(LIFO)原则的有序集合。新添加的或待删除的元素都保存在栈的末尾,称作栈顶,另一端就叫栈底。在栈里,新元素都靠近栈顶,旧元素都接近栈底。栈的形象描述可以比作一桶水、我们喝到的始终是最新倒进去的(假设水不存在混合的问题)。

创建栈

我们先来构建一个栈类的基本结构:

function Stack(){
    //属性及方法
}

有了一个基本结构,我们来开始构建栈的功能结构:

  • push(element):添加一个或多个新元素到栈顶
  • pop():返回栈顶元素,同时在栈中将其移除
  • peek():返回栈顶元素,但是不对栈做任何操作
  • isEmpty(): 判断栈是否为空,若是返回true,否则返回false
  • clear():移除栈里面的所有元素。
  • size():返回栈中元素个数。

在这里我们采用数组来作为栈的一个基本保存结构,在构建中我们会首先声明一个items数组,之后的数据操作都会操作这个items。

首先实现的是他的添加功能,添加是像栈顶添加元素,我们默认数组的最右侧为栈顶,于是添加操作如下:

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

然后我们来实现pop方法,其返回栈顶元素,同时将其移除,根据我们的默认规则,我们就产生了如下代码:

this.pop = function(){
    return items.pop()
}

如此这个栈的两个基本功能实现了,符合栈的先进后出特点,不允许他进行其他插入操作。接下来我们继续实现他的剩余功能。

peek的功能是返回栈顶元素,但不影响栈本身,这里我们直接返回数组的最后一个元素即可:

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

下一个要实现的功能是isEmpty,这个也很简单,只需要判断这个数组长度是否为0即可:

this.isEmpyt = function(){
    return items.length==0
}

然后我们再来实现size,这个和上面的原理相同,只需要返回数组的长度即可

this.sise = function(){
    return items.length
}

最后来实现一个清空功能clear,只需要将数组清空即可:

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

我们可以内置一个print方法,来检测查看栈中的数据:

this.print = function(){
    console.log(items.toString());
}

如此,栈的整个结构就已经创建完成了。

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(items.toString());
     };
}

简单应用

栈已经实现了,下面我们对其进行一个简单的应用,使用栈来对十进制向其他进制转换。那么为什么要用栈来实现这个算法呢,我们以二进制为例,看一下二进制转换规则
JavaScript创建栈结构
进制转换的规则是将余数倒序输出,也就是先得到的余数后出来,这完全符合栈的一个结构特点,所以我们采用栈来进行构建算法。

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;
}

在将十进制转成二进制时,余数是0或1;在将十进制转成八进制时,余数是0到8之间的数;但是将十进制转成16进制时,余数是0到8之间的数字加上A、B、C、D、E和F(对应10、11、12、13、14和15),通过循环移出栈顶元素来拼接成字符串,循环完成以后就构成了我们要实现的进制转换。

参与评论