用JS实现一个栈

快来打我* 2022-11-05 00:54 163阅读 0赞

我们先来看一道多益网络2021春招的笔试题：

***用JS实现一个栈的类，要求含有push（入栈）、pop（出栈）、getPeek（获取栈顶）、isAmpty（判断是否为空栈）、size（获取栈的元素数量）、reset（清空栈）、print（打印栈）这几种方法***

## 什么是栈（Stack） ##

![preview][]

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

在生活中也能发现很多栈的例子。例如，厨房里堆放的盘子，总是叠在上方的先被使用；输入框内容进行删除时，总是最后输入的先删除；弹夹中的子弹，越后装入的，越先发射......

## 用JS手动实现一个栈 ##

首先，创建一个类来表示栈

function Stack () { }

我们需要选择一种数据结构来保存栈里的元素，可以选择数组

function Stack(){
        var items = [];     //用来保存栈里的元素
    }

接下来，为栈添加一些方法

push(element(s));   //添加新元素到栈顶
    pop();              //移除栈顶的元素，同时返回被移除的元素
    peek();             //返回栈顶的元素，不对栈做任何修改
    isEmpty();          //如果栈里没有任何元素就返回true，否则false
    clear();            //移除栈里的所有元素
    size();             //返回栈里的元素个数,类似于数组的length属性

### push() ###

添加元素到栈顶

`push()`用来往栈里添加新元素，有一点很重要：该方法只添加到栈顶，也就是栈的末尾。所以，可以这样写：

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

利用数组的push方法，就可以实现在栈顶末尾添加新的元素了。

### pop() ###

`pop`方法用来实现移除栈里的元素。栈遵从LIFO（后进先出）原则。移出去的是最后添加进去的元素。因此，可以使用数组的pop方法。

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

这样一来，这个栈自然就遵从了LIFO原则

### peek() ###

如果想知道栈里最后添加的元素是什么，可以用`peek`方法。这个方法将返回栈顶的元素

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

因为类内部是用数组保存元素的，所以这里访问数组最后一个元素用`length-1`

### isEmpty() ###

如果栈为空的话，就返回true，否则返回false

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

使用isEmpty方法，就能简单地判断栈内部是否为空。

### size() ###

类似于数组地length属性，我们也可以实现栈的length

this.size = function () {
        return items.length;
    }

因为栈的内部使用数组保存元素，所以数组的长度就是栈的长度。

### clear() ###

clear方法用来清空栈中所有的元素。最简单的实现方法如下

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

其实多次调用pop方法也可以，但是没有这个方法来的简单快捷。

### print()  ###

为了检查栈里的内容，还需要实现一个辅助方法：`print`。它会把栈里的元素都输出到控制台

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

至此，我们就用JS完整地创建了一个**栈**！

## 栈的完整代码 ##

## 使用Stack类 ##

栈已经创建好了，我们来测试一下

首先，来初始化Stack类。然后，验证一下栈是否为空：

var stack = new Stack();
    console.log(stack.isEmpty());         //控制台输出true

接下来，往栈里面添加一下元素：

stack.push(5);
    stack.push(8);

如果调用peek方法，很显然将会输出8，因为它是栈顶的元素：

console.log(stack.peek());            //控制台输出8

再添加一个元素，获取栈的元素数量：

stack.push(11);
    console.log(stack.size());            //控制台输出3

我们往栈里又添加了11。如果调用size方法，输出为3，因为栈里有三个元素（5，8和11）。如果这时候调用isEmpty方法，会看到输出了false（因为此时栈不为空）。最后，再来往里面添加一个元素：

stack.push(15);

然后，调用两次pop方法从栈里移除两个元素，然后把栈里的元素输出：

stack.pop();
    stack.pop();
    console.log(stack.size());            //控制台输出2
    stack.print();                        //控制台输出5,8

到这里，整个栈的功能测试完成。

## 用栈来解决问题 ##

使用栈来完成进制转换。  
  
现实生活中，我们主要用10进制，但在计算科学中，二进制非常重要，因为计算机里所有的内容都是用二进制数字0和1来表示的。大学的计算机课都会先教进制转换。以二进制为例：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgwNDQ5Ng_size_16_color_FFFFFF_t_70][]

这段代码里，当结果满足和2做整除的条件时，（行\{1\}），我们会获得当前结果和2的余数，放到栈里（行\{2\}、\{3\}）。然后让结果和2做整除（行\{4\}）

注：JavaScript有数字类型，但是它不会区分时整数还是浮点数。因此，要使用Math.floor函数让除法的操作仅返回整数部分（向下取整）。

最后，用pop方法把栈中的元素都移除，把出栈的元素连接成字符串（行\{5\}）。

测试一下：

console.log(pideBy2(520));      //输出1000001000
    console.log(pideBy2(10));       //输出1010
    console.log(pideBy2(1000));     //输出1111101000

接下来，可以很容易的修改上面的算法，使它能够把十进制转化为任何进制。除了让十进制数字和2整除转成二进制数，还可以传入其他任意进制的基数作为参数，就像下面的算法这样：

在将十进制转成二进制时，余数是0或1；在将十进制转成八进制时，余数时0-8之间的数；但是将十进制转成十六进制时，余数时0-9之间的数字加上A、B、C、D、E、F（对应10、11、12、13、14和15）。因此，需要对栈中的数字做个转化才可以（行\{6\}、\{7\}）。  
  
来测试一下输出结果：

console.log(baseConverter(1231,2));      //输出10011001111
    console.log(baseConverter(1231,8));      //输出2317
    console.log(baseConverter(1231,16));     //输出4CF

显然是正确的。

## 总结 ##

我们用JS代码自己实现了栈。并且通过进制转换的例子来实际应用了它。栈的应用实例还有很多，比如平衡圆括号和汉诺塔。

[preview]: /images/20221023/24610443e1cb4e5a99aa873c33dad732.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgwNDQ5Ng_size_16_color_FFFFFF_t_70]: /images/20221023/24d904b9a6254476ab627a52e9708667.png