初识前端中的栈

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

这便是一个基于数组创建的栈，然后我们要为它声明一些方法。

1、添加元素

• 要注意该方法只添加元素到栈顶，也就是这个数组的末尾。因此我们可以用数组的push方法来实现

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

2、删除元素

• 同样只能从栈顶删除，因为是基于数组创建的，所以可以使用数组的pop方法

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

3、查看栈顶元素

• 利用数组的长度来查看数组最后一个元素

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

4、检查栈是否为空

• 如果数组的长度为零，那它就是空的

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

5、清空栈元素

• 可以直接把数组重置为空

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

这是我举栗创建的几个简单方法，接下来让我使用这个Stack类

const stack = new StackArray();
console.log(stack.isEmpty()) // 此时输出为true
stack.push(5);      // [] ==>[5]
stack.push(8);     //  [5] ==>[5,8]
console.log(stack.peek()); // 输出为8
stack.push(11);    // [5,8] ==>[5,8,11]
console.log(stack.isEmpty()) // 这时的输出为false
stack.pop();  // [5,8,11] ==>[5,8]
复制代码

• 以上便是一个简单的基于数组的栈。创建一个Stack类最简单的方式就是用一个数组来存储元素。在使用数组时，大部分方法的时间复杂度是O(n)。意思是，我们需要迭代整个数组直到找到要找的那个元素，如果它在栈底，就需要迭代数组的所有位置，其中的n代表数组的长度。如果数组元素越多，所需时间就越长。另外，数组是元素的一个有序集合，为了保证元素排列有序，它会占用更多的内存空间。
• 如果我们能直接获取元素，占用较少的内存空间，并且仍然保证所有元素按照我们的需要排列，那不是更好吗？我们可以使用一个javascript对象来存储所有的栈元素。

基于对象的栈

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

这就是一个基于对象的栈，因为对象没有length属性，我们要使用一个count属性来记录栈的大小。下面是对象栈的一些简单的方法。

1、添加元素

• 我们用count变量来作为对象的键名，插入的元素就是它的值，同时在向栈插入元素后，我们递增count变量

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

2、检查栈是否为空

• 这个直接判断count的值就可以了

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

3、删除元素

• 首先要判断它是否为空，(如果为空那还有啥可删的嘛！) ==>然后将count属性减1==>找到栈顶的值并保存==>然后用对象的delete方法将其删除==>最后做一个像数组的pop方法一样的功能，将删除的元素返回

pop() {
   if (this.isEmpty()) { // 判断是否为空
     return undefined;
   }
   this.count--; // 栈的大小减1
   const result = this.items[this.count]; // 保存栈顶值
   delete this.items[this.count]; // 删除栈顶值
   return result; // 返回删除值
 }
复制代码

4、创建toString方法

• 在数组版本中，我们不需要关心toString方法的实现，因为数据结构可以直接使用数组原生的toString方法。对于使用对象的版本，我们来创建一个toString方法来像数组一样打印出栈的内容。首先，判断是否为空==>如果不空就用栈底的第一个元素作为字符串的初始值==>然后迭代整个栈的键==>用上一个相加好的字符串加上当前的字符串，中间用逗号隔开。这样写的好处是如果栈只有一个元素，循环将不会执行（毕竟能不循环最好不要嘛）。

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;
 }
复制代码

• 好了，实现完toString方法后，我们就完成了一个简单的基于对象的栈类。对于使用这个栈的开发者，选择使用基于数组或者基于对象的版本并不重要。两者都可以实现相同的功能，只是内部实现很不一样！！！

除了toString方法，我们创建其它对象栈方法的复杂度均为O(1),代表我们可以直接找到目标元素并对其进行操作（push、pop）
复制代码

最后

• 本文的内容来自本人阅读过《学习Javascript数据结构与算法》后按照个人的理解对第四章的前半部分内容做得一个简单的整理。我是一个努力干活还不磨人的小前端