热爱web前端
技术分享平台

javascript数据结构与算法——栈

栈是一种遵从后进先出(LIFO)原则的有序集合。新添加的或待删除的元素都保存在栈的末尾,称作栈顶,另一端就叫栈底。在栈里,新元素都靠近栈顶,旧元素都接近栈底。

在现实生活中也能发现很多栈的例子。例如,下图里的一摞书或者餐厅里堆放的盘子。

栈也被用在编程语言的编译器和内存中保存变量、方法调用等。

创建栈:

我们将创建一个类来表示栈。让我们从基础开始,先声明这个类:

function Stack() {

//各种属性和方法的声明

}

首先,我们需要一种数据结构来保存栈里的元素。可以选择数组:

var items = [];

接下来,要为我们的栈声明一些方法。

push(element(s)):添加一个(或几个)新元素到栈顶。

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

peek():返回栈顶的元素,不对栈做任何修改(这个方法不会移除栈顶的元素,仅仅返回它)。

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

clear():移除栈里的所有元素。

size():返回栈里的元素个数。这个方法和数组的length属性很类似。

我们来实现pop方法。这个方法主要用来移除栈里的元素。栈遵从LIFO原则,因此移出的是最后添加进去的元素。因此,我们可以用上一章讲数组时介绍的pop方法。栈的pop方法可以这样写:rnthis.pop = function(){

return items.pop();

};

栈的全部代码

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

};

}

我们已经学会了如何使用Stack类,现在就用它解决一些计算机科学中的问题。

现实生活中,我们主要使用十进制。但在计算科学中,二进制非常重要,因为计算机里的所有内容都是用二进制数字表示的(0和1)。没有十进制和二进制相互转化的能力,与计算机交流就很困难。

大学的计算机课一般都会先教这个进制转换。下面是对应的算法描述:

function divideBy2(decNumber){

var remStack = new Stack(),

rem,

binaryString = \'\';

while (decNumber > 0){ //{1}

rem = Math.floor(decNumber % 2); //{2}

remStack.push(rem); //{3}

decNumber = Math.floor(decNumber / 2); //{4}

}

while (!remStack.isEmpty()){ //{5}

binaryString += remStack.pop().toString();

}

return binaryString;

}

在这段代码里,当结果满足和2做整除的条件时(行{1}),我们会获得当前结果和2的余数,放到栈里(行{2}、 {3})。然后让结果和2做整除(行{4})。另外请注意: JavaScript有数字类型,但是它不会区分究竟是整数还是浮点数。因此,要使用Math.floor函数让除法的操作仅返回整数部分。最后,用pop方法把栈中的元素都移除,把出栈的元素变成连接成字符串(行{5})。

用刚才写的算法做一些测试,使用以下代码把结果输出到控制台里:

console.log(divideBy2(233)); //输出11101001

console.log(divideBy2(10)); //输出1010

console.log(divideBy2(1000)); //输出1111101000

未经允许不得转载:前端网(w3cvip) » javascript数据结构与算法——栈

分享到:更多 ()

评论 2

评论前必须登录!

 

  1. #2

    不觉明厉

    九歌2周前 (12-19)
  2. #1

    很好

    zuimeiaj2周前 (12-19)