本文共 4518 字，大约阅读时间需要 15 分钟。

一、用栈解决问题的领域

在上一篇文章中，我们了解并学习了JavaScript使用不同的方法来定义栈数据结构，那么本章就是使用JavaScript的栈数据结构来解决一些问题的举例。

栈的实际应用非常广泛。在回溯问题中，它可以存储访问过的任务或路径、撤销的操作(后面的章节会讲述如何应用这个例子)。Java和C#用栈来存储变量和方法调用，特别是处理递归算法时，有可能抛出一个栈溢出异常(后面的章节也会介绍)。

既然我们已经了解了Stack类的用法，不妨用它来解决一些计算机科学问题。本章就介绍如何解决十进制转二进制问题，以及任意进制转换的算法。

二、从十进制到二进制

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

要把十进制转化成二进制，我们可以将该十进制数除以2（二进制是满二进一）并对商取整，直到结果是0为止。

举个例子，把十进制的数10转化成二进制的数字，过程大概是如下这样。

function decimalToBinary(decNumber){
   	// 这里使用上一章节声明的栈类	const remStack = new Stack();	let number = decNumber;	let rem;	let binaryString = '';	while(number > 0){
   	//{1}		rem = Math.floor(number % 2); //{2}		remStack.push(rem); //{3}		number = Math.floor(number / 2); //{4}	}		while(!remStack.isEmpty()){
   	//{5}		binaryString += remStack.pop().toString();	}	return binaryString;}

在这段代码里，当除法的结果不为0时(行{1})，我们会获得一个余数，并放到栈里(行{2}、行{3})。然后让结果继续除以2(行{4})。

另外需注意：JavaScript有数值类型，但是它不会区分整数和浮点数。因此，要使用Math.floor函数仅返回除法运算结果的整数部分。

最后，用pop方法把栈中的元素都移除，把出栈的元素连接成字符串（行{5})。用刚才写的算法做一些测试，使用以下代码把结果输出到控制台里。

完整代码

class Stack {
       constructor() {
           this.count = 0;        this.items = {
   };    }    push (element) {
           this.items[this.count] = element;        this.count++;    }    size () {
           return this.count;    }    isEmpty () {
           return this.count === 0;    }    pop () {
           if (this.isEmpty()) {
   	// {1}            return undefined;        }        this.count--;	//{2}        const result = this.items[this.count]; //{3}        delete this.items[this.count];	//{4}        return result;	//{5}    }    peek () {
           if (this.isEmpty()) {
               return undefined;        }        return this.items[this.count - 1];    }    clear () {
           this.items = {
   };        this.count = 0;        //当然我们也可以遵循LIFO原则，使用下面的逻辑来移除栈中所有的元素。        // while(1this.isEmpty()){
           // 		this.pop();        // }    }    toString () {
           if (this.isEmpty()) {
               return '';        }        let objString = `${
     this.items[0]}`;	//{1}        for (let i = 1; i < this.count; i++) {
    //{2}            objString = `${
     objString},${
     this.items[i]}`; //{3}        }        return objString;    }}function decimalToBinary (decNumber) {
       // 这里使用上一章节声明的栈类    const remStack = new Stack();    let number = decNumber;    let rem;    let binaryString = '';    while (number > 0) {
   	//{1}        rem = Math.floor(number % 2); //{2}        remStack.push(rem); //{3}        number = Math.floor(number / 2); //{4}    }    while (!remStack.isEmpty()) {
   	//{5}        binaryString += remStack.pop().toString();    }    return binaryString;}console.log(decimalToBinary(10));	//1010console.log(decimalToBinary(233));	//11101001console.log(decimalToBinary(1000));	//1111101000

运行一下看看

三、进制转换算法

进制转换算法我们可以修改之前的算法，使之能把十进制转换成基数为2~36的任意进制。除了把十进制数除以2转成二进制数，还可以传入其他任意进制的基数为参数，就像下面的算法这样。

function baseConverter (decNumber, base) {
       // 这里使用上一章节声明的栈类    const remStack = new Stack();    const digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'; //{6}    let number = decNumber;    let rem;    let binaryString = '';    //进制判断，需在范围内    if(!(base >= 2 && base <= 36)){
   		return '';	}        while (number > 0) {
   	        rem = Math.floor(number % base);         remStack.push(rem);         number = Math.floor(number / base);    }    while (!remStack.isEmpty()) {
           binaryString += digits[remStack.pop()];	//{7}    }    return binaryString;}

我们只需要改变一个地方。

在将十进制转成二进制时，余数是0或1；

在将十进制转成八进制时，余数是0 ~ 7；

但是将十进制转成十六进制时，余数是0~9加上A、B、C、D、E和F(对应10、11、12、13、14和15)。

因此，我们需要对栈中的数字做个转化才可以(行{6}和行{7})。因此，从十一进制开始，字母表中的每个字母将表示相应的基数。字母A代表基数11，B代表基数12，以此类推。

console.log(baseConverter(10345, 2));   //10100001101001console.log(baseConverter(10345, 8));  //24151console.log(baseConverter(10345, 16));  //2869console.log(baseConverter(10345, 35));  //8FK

到这里的呢，本章的进制转换应用实例就差不多完了，其实除了本例子还有许多应用的场景，例如平衡圆括号和汉诺塔等。

若看过模板引擎源码，知道编译原理的朋友肯定也在里面看到了栈结构的应用，著名的mustache.js，还有vue的模板也是用到了栈的哦。

四、本章小结

本系列文章主要讲述JavaScript栈数据结构（Stack）类能解决什么问题，数据栈类的文章共三篇，本文也是第三篇。

从1 - 3篇的文章里，讲述了栈这一数据结构的相关知识。我们使用数组和一个JavaScript对象自己实现了栈，还讲解了如何用push和pop往栈里添加和移除元素。我们比较了创建Stack类的不同方法，并分别列举了优点和缺点。我们还学习了用栈来解决计算机科学中最著名的问题之一。

工欲善其事，必先利其器。

五、写在后面

这作为一个JavaScript栈数据结构的第三篇文章，主要目的是使用Stack来解决问题，本系列也会持续进行更新的。

剧透：下一章讲述队列。它和栈有很多相似之处，但有个重要区别：队列里的元素不遵循后进先出原则。

有问题请留言或者@博主,谢谢支持o(￣︶￣)o~

感谢您的阅读,如果此文章或项目对您有帮助，若可以的话请给个一键三连吧！

GitHub有开源项目,需要的小伙伴可以顺手star一下！

GitHub: https://github.com/langyuxiansheng

转载地址：http://spjef.baihongyu.com/