首页 > 代码库 > 数据结构与算法JavaScript描述——栈的使用

数据结构与算法JavaScript描述——栈的使用

2024-10-31 10:32:39   205人阅读

有一些问题特别适合用栈来解决。本节就介绍几个这样的例子。
 
1） 数制间的相互转换　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
可以利用栈将一个数字从一种数制转换成另一种数制。假设想将数字n 转换为以b 为基数的数字，实现转换的算法如下。
技术分享
使用栈，在JavaScript 中实现该算法就是小菜一碟。下面就是该函数的定义，可以将数字转化为二至九进制的数字：
技术分享 
//============================使用Stack类====================================
/**
*    1.数制间的相互转换
*/
function mulBase(num, base){
    var s = new Stack();
    do{
        s.push(num % base);
        num = Math.floor(num / base);
    }while (num > 0);

    var converted = "";
    while(s.length() > 0){
        converted += s.pop();
    }

    return converted;
}
//下面展示了如何使用该方法将数字转换为二进制和八进制数。
var num = 32;
var base = 2;
var newNum = mulBase(num, base);
console.log(num + " converted to base " + base + " is " + newNum);
num = 125;
base = 8;
var newNum = mulBase(num, base);
console.log(num + " converted to base " + base + " is " + newNum);
View Code

打印如下：

技术分享

 

 

2）回文　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
回文是指这样一种现象：一个单词、短语或数字，从前往后写和从后往前写都是一样的。
比如，单词“dad”、“racecar”就是回文；如果忽略空格和标点符号，下面这个句子也是回文，“A man, a plan, a canal: Panama”；数字1001 也是回文。
 
使用栈，可以轻松判断一个字符串是否是回文。
我们将拿到的字符串的每个字符按从左至右的顺序压入栈。当字符串中的字符都入栈后，栈内就保存了一个反转后的字符串，最后的字符在栈顶，第一个字符在栈底。
字符串完整压入栈内后，通过持续弹出栈中的每个字母就可以得到一个新字符串，该字符串刚好与原来的字符串顺序相反。我们只需要比较这两个字符串即可，如果它们相等，就是一个回文。
 
 代码：
技术分享 
//============================使用Stack类====================================
/**
*    2.判断给定字符串是否是回文
*/
function isPalindrome(word){
    var s = new Stack();
    for(var i=0; i<word.length; ++i){
        s.push(word[i]);
    }

    var rword = "";
    while(s.length() > 0){
        rword += s.pop();
    }

    if(word == rword){
        return true;
    }else{
        return false;
    }
}

//测试代码：
var word = "hello";
if (isPalindrome(word)) {
    console.log(word + " is a palindrome.");
}else {
    console.log(word + " is not a palindrome.");
}
word = "racecar";
if (isPalindrome(word)) {
    console.log(word + " is a palindrome.");
}else {
    console.log(word + " is not a palindrome.");
}
View Code

打印：

技术分享

 
 
3）递归演示　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
这里只用栈来模拟递归过程。
为了演示如何用栈实现递归，考虑一下求阶乘函数的递归定义。首先看看5 的阶乘是怎么定义的：
5! = 5×4×3×2×1 = 120
下面是一个递归函数，可以计算任何数字的阶乘：
技术分享
 
使用栈来模拟计算5! 的过程，首先将数字从5 到1 压入栈，然后使用一个循环，将数字挨个弹出连乘，就得到了正确的答案：120。
代码：
 
技术分享 
//============================使用Stack类====================================
/**
*    3.　使用栈模拟递归过程
*/
function fact(n){
    var s = new Stack();
    while(n > 1){
        s.push(n--);
    }

    var product = 1;
    while(s.length() > 0){
        product *= s.pop();
    }
    return product;
}

console.log(fact(5)); // 显示120
View Code

 

 
 

数据结构与算法JavaScript描述——栈的使用


联系
我们