Code前端首页关于Code前端联系我们
首页 后端开发数据结构与算法正文

什么是堆栈？如何用简单的es6代码实现这个？

terry 2年前 (2023-09-27) 阅读数 66 #数据结构与算法

什么是堆栈？

堆栈是一种高效的数据结构（基于 LIFO 原理的有序集合）。由于只能在栈顶添加或删除数据，因此此类操作快速且易于实现。堆栈用于编程语言实现的各个方面。在编程语言中，编译器也使用堆栈，计算机内存也使用堆栈来存储变量和方法调用，以及浏览器的返回函数。除了计算机上的很多堆栈应用之外，现实生活中也有实际的例子。比如我们从书堆里取出书本，从餐边柜里的盘子堆里取出最上面的盘子等等：什么是栈？如何用es6简单的代码实现？

如何轻松使用JS实现栈？

如何用JS模拟一个简单的堆栈？首先，我们创建一个 stack-array.js 文件并声明 StackArray 类。代码如下：

class StackArray {
    constructor() {
        this.items = []; // {1}
    }
}复制代码

接下来做什么？我们需要一个可以存储堆栈元素的数据结构。为此，我们可以使用数组结构。我们还需要在堆栈中添加和删除数据元素。由于堆栈的后进先出原则，我们的添加和删除方法有点特殊。 ，Stack 类实现包括以下方法：

  1. push(element(s))：该方法将新添加的元素添加到堆栈顶部。
  2. pop()：该方法删除栈顶元素，同时返回删除的元素
  3. peek()：返回栈顶元素
  4. isEmpty()：判断是否堆栈为空，如果为空则返回 true ，否则返回 False 。
  5. clear()：清除堆栈中的所有元素。
  6. size()：该方法返回栈中元素的数量，类似于数组的长度。
  7. toArray()：以数组形式返回堆栈的元素。
  8. toString()：将堆栈的内容作为字符串输出。

push()

该方法负责向堆栈添加新元素。最重要的特点是新元素只能添加到栈顶，即栈尾。为了恰好满足这个需求，我们可以使用数组push方法，代码如下： 

push(element) {
    this.items.push(element);
} 复制代码

pop()

接下来我们实现pop()方法。该方法删除栈顶元素。由于它遵循 LIFO 原则，因此最后一个元素被删除。利用数组，我们可以自动弹出如下代码： 

pop() {
    return this.items.pop();
} 复制代码

peek(), isEmpty(), size(), clear()

核心的增删改查就完成了，现在我们实现相关的helper方法，peek() 方法让我们看看堆栈的最后一个元素。实现代码如下： 

peek() {
    return this.items[this.items.length - 1];
} 复制代码

isEmpty()方法也很简单。只需评估栈数组的长度是否为0即可。代码如下： 

isEmpty() {
    return this.items.length === 0;
} 复制代码

size()方法更简单。使用Array的length方法就足够了。代码如下 

size() {
    return this.items.length;
} 复制代码

最后应用最简单的清理方法clear()，将stack变量重置为空并设置值： 

clear() {
    this.items = [];
}复制代码

最终完成的stack-array.js代码如下： 

export default class StackArray {
    constructor() {
        this.items = [];
    }

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

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

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

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

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

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

    toArray() {
        return this.items;
    }

    toString() {
        return this.items.toString();
    }
}复制代码

接下来，我们创建一个文件 stackdemo.js 并导入文件 stack- array.js。让我们练习一下如何使用我们创建的 StackArray 类。代码如下： 

import StackArray from 'stack-array.js';
const stack = new StackArray();

console.log('stack.isEmpty() => ', stack.isEmpty()); // outputs true

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

console.log('stack after push 5 and 8 => ', stack.toString());

console.log('stack.peek() => ', stack.peek()); // outputs 8

stack.push(11);

console.log('stack.size() after push 11 => ', stack.size()); // outputs 3
console.log('stack.isEmpty() => ', stack.isEmpty()); // outputs false

stack.push(15);

stack.pop();
stack.pop();

console.log('stack.size() after push 15 and pop twice => ', stack.size()); // outputs 2复制代码

我们可以新建一个stackdemo.html并导入。 stackdemo.js()，只需打开stackdemo.html。栈的工作图如下：

调用push()方法后的效果：什么是栈？如何用es6简单的代码实现？

执行pop()方法后的效果：什么是栈？如何用es6简单的代码实现？

创建一个更高效的基于对象的栈类

In上一节，我们快速实现了一个基于数组的堆栈。我们知道数组是有序数组。如果存储的数据量很大，内容就太多了。 ，如果长度太大，会消耗更多的计算机内存并增加算法的复杂度（O(n)，我们在后面的文章中介绍）。为了解决这个问题，我们采用更原始的方法来实现。首先，我们在 stack.js 文件中声明 stack 类。代码如下： 

class Stack {
    constructor() {
        this.count = 0;
        this.items = {};
    }
    // methods
} 复制代码

push()

在JS中，对象是一组键值对的集合。我们可以使用枚举变量作为 items 对象的键。元素就是它的值，添加新元素后，count 变量加 1。代码实现如下： 

push(element) {
    this.items[this.count] = element;
    this.count++;
}复制代码

例如我们可以向空栈中添加新元素5和8，代码如下： 

const stack = new Stack();
stack.push(5);
stack.push(8);复制代码

当输出栈对象的项数和数量时，效果为如下：

isEmpty()

为了判断栈是否为空，我们只需要判断count变量是否为0即可 代码如下： 

isEmpty() {
    return this.count === 0;
}复制代码

pop()

重写这个方法，首先要检查栈是否为空。如果不是，则返回未定义。如果没有，我们将 count 变量减 1 并删除相应的属性。代码如下： 

pop() {
  if (this.isEmpty()) { 
    return undefined;
  }
  this.count--; 
  const result = this.items[this.count];
  delete this.items[this.count]; 
  return result; 
}复制代码

接下来我们重写其他方法。完整代码如下： 

export default class Stack {
  constructor() {
    this.count = 0;
    this.items = {};
  }

  push(element) {
    this.items[this.count] = element;
    this.count++;
  }

  pop() {
    if (this.isEmpty()) {
      return undefined;
    }
    this.count--;
    const result = this.items[this.count];
    delete this.items[this.count];
    return result;
  }

  peek() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.count - 1];
  }

  isEmpty() {
    return this.count === 0;
  }

  size() {
    return this.count;
  }

  clear() {
    /* while (!this.isEmpty()) {
        this.pop();
      } */
    this.items = {};
    this.count = 0;
  }

  toString() {
    if (this.isEmpty()) {
      return '';
    }
    let objString = `${this.items[0]}`;
    for (let i = 1; i < this.count; i++) {
      objString = `${objString},${this.items[i]}`;
    }
    return objString;
  }
}复制代码

我们的课虽然完成了，但是你觉得有问题吗？由于我们创建的类的属性对所有开发者都是公开的，所以我们希望只能在栈顶添加元素而不希望向其他位置添加元素，但是Stack类中声明的属性和枚举是不受保护。这是一个JS规则问题。难道我们就没有办法改变这一点吗？答案是肯定的，我们可以利用ES6新添加的Symbol数据类型来获取私有属性作为对象属性（关于Symbol数据类型，作者在这篇文章中已经介绍过《【ES6基础】Symbol介绍：独一无二的值》），并在此基础上重写stack-array.js上的代码，代码如下： 

const _items = Symbol('stackItems');

class Stack {
    constructor() {
        this[_items] = [];
    }

    push(element) {
        this[_items].push(element);
    }

    pop() {
        return this[_items].pop();
    }

    peek() {
        return this[_items][this[_items].length - 1];
    }

    isEmpty() {
        return this[_items].length === 0;
    }

    size() {
        return this[_items].length;
    }

    clear() {
        this[_items] = [];
    }

    print() {
        console.log(this.toString());
    }

    toString() {
        return this[_items].toString();
    }
}

const stack = new Stack();
const objectSymbols = Object.getOwnPropertySymbols(stack);
console.log(objectSymbols.length); // 1
console.log(objectSymbols); // [Symbol()]
console.log(objectSymbols[0]); // Symbol()
stack[objectSymbols[0]].push(1);
stack.print(); // 5, 8, 1复制代码

实际应用示例

Pina有各种解决实际问题的应用程序。例如，我们经常使用各种软件的撤消功能，尤其是在Java和C#编程语言中。堆栈用于存储变量和调用方法，可能会引发堆栈溢出异常，尤其是在使用递归算法时。接下来我们就亲自实现一下十进制转二进制的功能。

我们已经熟悉十进制了。然而，二进制表示在计算机科学中非常重要，因为计算机中的所有内容都是由二进制数（0和1）表示的。如果没有十进制数和二进制数之间来回转换的能力，与计算机的通信将会很困难。要将十进制数转换为二进制，我们需要将要转换的数除以2，然后将结果除以2，以此类推，直到结果为0。具体示意图如图：什么是栈？如何用es6简单的代码实现？

根据上图的逻辑解释，完成的功能代码如下： 

function decimalToBinary(decNumber) {
        const remStack = new Stack();
        let number = decNumber;
        let rem;
        let binaryString = '';

        while (number > 0) {
            rem = Math.floor(number % 2); 
            remStack.push(rem); 
            number = Math.floor(number / 2); 
        }

        while (!remStack.isEmpty()) { 
            binaryString += remStack.pop().toString();
        }

        return binaryString;
    }复制代码

从上面的代码中，我们定义了一个栈，使用循环来处理要处理的数字，将模块的剩余部分压入堆栈，然后将其逐个弹出，连接成字符串作为输出。然后我们测试一下十进制到二进制的转换是否符合预期，如下面的测试代码所示： 

console.log(decimalToBinary(233)); // 11101001
console.log(decimalToBinary(10)); // 1010
console.log(decimalToBinary(1000)); // 1111101000”复制代码

练习题

我们只是练习一下十进制到二进制的转换，以使其更加通用，因为在实际应用中，不仅有是二进制转换要求，比如八进制、十六进制等。现在我想给大家留下作业。实现 baseConverter(decNumber, base) 函数。第一个参数是要转换的十进制数，第二个参数是要转换的参数，从十进制2转换为36。欢迎您在留言区发布代码。第

在这篇文章中，我们将了解什么是数据结构，并深入学习堆栈数据结构和堆栈的JS代码实现，并解释不同的实现方法。同时了解堆栈在计算机领域的作用应用并练习用

将十进制数转换为二进制作者：前端专家
链接：https://juejin.im/post/5ce0b01df265da1bb47d33eb
来源：掘金
版权归作者所有。商业转载请联系作者获取授权。非商业转载请注明出处。

版权声明

本文仅代表作者观点，不代表Code前端网立场。
本文系作者Code前端网发表，如需转载，请注明页面地址。

上一篇：阿里巴巴工程师算法与数据四道笔试题及答案 下一篇：Line算法与deepwalk的对比
相关文章
terry

terry

作者文章
浏览更多
热门
最新文章
标签列表
Copyright by code前端网 All Rights Reserved.粤ICP备12067512号-4

Powered By Z-BlogPHP Theme By 编程老白