数据结构&算法：JS封装“栈”结构

前言

最近在学习数据结构和算法，虽然前端在实际业务开发中直接用到的一般不多，但学习这些能帮助我们理解一些底层知识，优化代码逻辑、提升代码质量，更重要的是对思维的锤炼，帮助我们朝着大前端的方向迈出更扎实的步伐。

作为一个初涉数据结构和算法的萌新，我将多看多练，尽可能的去系统的学习，并通过js来一一实现。写代码，不含糖，搞起搞起。

数据结构&算法：JS封装“栈”结构

一、【数据结构】栈的介绍

数据结构&算法：JS封装“栈”结构

二、JS封装实现一个栈

js本身提供了数组相关操作的方法，十分方便灵活，那么我们便基于数组来封装一个类，实现简单的栈结构及相关操作。

思路：

创建一个类，在构造实例时创建一个数组类型的变量，来存放相关操作数据
类中提供一些栈相关操作方法和属性
实例化并测试操作

封装如下：

// 封装一个栈类
class Stack {
  constructor() {
    this.data = [] // 存放栈数据的变量
  }
  // 通过length属性 获取栈的长度
  get length () {
    return this.data.length
  }
  // 通过isEmpty属性 判断是否空栈
  get isEmpty () {
    return this.data.length === 0
  }
  // 压栈
  push (item) {
    this.data.push(item)
  }
  // 出栈
  pop () {
    return this.data.pop()
  }
  // 清空栈
  clear () {
    this.data.length = 0
  }
  // 查看栈顶元素
  peek () {
    return this.data[this.data.length - 1]
  }
}

简单的栈结构就封装好了，接下来进行测试：

// 实例化并进行相关操作
const stack = new Stack()

console.log(stack.length)  // 栈长度，打印结果 0
console.log(stack.isEmpty) // 是否空栈 打印结果 true

stack.push(1) // 将数字1压入栈中
stack.push(2) // 将数字2压入栈中
stack.push(3) // 将数字3压入栈中
console.log(stack.peek()) // 获取栈顶元素 打印结果 3

stack.pop() // 出栈
console.log(stack.length)  // 栈长度，打印结果 2
console.log(stack.isEmpty) // 是否空栈 打印结果 false

stack.clear()
console.log(stack.length)  // 栈长度，打印结果 0
console.log(stack.isEmpty) // 是否空栈 打印结果 true

三、栈相关经典题目解法

1、元素出栈、入栈顺序的合理性。

题目：入栈顺序是1、2、3、4、5，那么出栈顺序是4、5、3、2、1是否合理？

// 解：是否合理先从出栈顺序入手，我们可以通过实例化一个栈结构来模拟
const stack = new Stack()
// 第一个出栈是4，那么4必然在栈顶，那么根据入栈顺序，依次如下：
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)

stack.pop() // 出栈 4

stack.push(5)
stack.pop() // 出栈 5

stack.pop() // 出栈 3
stack.pop() // 出栈 2
stack.pop() // 出栈 1

// 因此以上出栈顺序是合理的

2、通过栈结构来实现进制转换

题目，实现十进制整数转换为二进制、八进制、十六进制。

分析：十进制整数转换为二进制整数采用"除2取余，逆序排列"法。具体做法是：用2整除十进制整数，可以得到一个商和余数；再用2去除商，又会得到一个商和余数，如此进行，直到商为小于1时为止，然后把先得到的余数作为二进制数的低位有效位，后得到的余数作为二进制数的高位有效位，依次排列起来。

数据结构&算法：JS封装“栈”结构

转八进制和转十六进制思路同样如此。

下面通过栈结构来实现：

/**
 * 十进制整数转换其他进制方法
 * @param num [Number] 十进制整数
 * @param base [Number] 要转换的进制；可选有：2-二进制（默认）；8-八进制；16-十六进制
 */
const decimalcConversion = (num, base = 2) => {
  // 判断要转换的是哪个进制
  const baseList = [2, 8, 16]
  if (baseList.includes(base)) {
    // 创建一个栈实例
    const stack = new Stack()
    // 向栈内压入余数
    while (num > 0) {
      stack.push(num % base)
      num = Math.floor(num / base)
    }
    // 出栈，存放到字符串中
    let string = ''
    while (!stack.isEmpty) {
      let item = stack.pop()
      // 针对16进制的处理
      if (item >= 10) {
        item = ['a', 'b', 'c', 'd', 'e', 'f'][item - 10]
      }
      string += item
    }
    // 返回转换后的进制字符串值
    return string
  } else {
    throw new Error('请输入正确的进制数')
  }
}
decimalcConversion(100) // 二进制 1100100
decimalcConversion(100, 8) // 八进制 144
decimalcConversion(100, 16) // 十六进制 64
decimalcConversion(300) // 二进制 100101100
decimalcConversion(300, 8) // 八进制 454
decimalcConversion(300, 16) // 十六进制 12c

3、返回栈中元素的最小值

分析：元素入栈后，要直接从栈中寻找最小值是很困难的，因为栈结构主要就是入栈、出栈两个核心操作，因此要获取最小值，可以通过新建一个数组存放。

数据结构&算法：JS封装“栈”结构

可以在上面封装栈的基础上继承，增加一个存放最小值的数组以及获取最小值的方法。

代码如下：

// 继承上面封装的栈
class MinStack extends Stack {
  constructor () {
    super()
    this.minData = [] // 存放栈中最小值
  }
  // 获取栈中最小元素
  get minimum () {
    return this.minData[this.minData.length - 1]
  }
  // 重写压栈push方法
  push (item) {
    let min = 0
    if (this.data.length === 0) {
      // 第一个元素进来时
      min = item
    } else {
      // 否则，对栈顶元素和压入元素进行比较，小的进minData
      const minimum = this.minimum
      min = item <= minimum ? item : minimum
    }
    this.data.push(item)
    this.minData.push(min)
  }
  // 重写出栈pop方法
  pop () {
    this.minData.pop()
    return this.data.pop()
  }
}

const stack = new MinStack()

stack.push(2)
stack.push(30)
stack.push(1)
stack.push(88)
console.log(stack.minimum) // 1
stack.pop()
stack.pop()
console.log(stack.minimum) // 2

当然，上面的实现主要是基于“栈”结构的特点，提供的一种解决问题的方式，目的是为了锤炼思维的多样性和灵活性。

实际上由于我们是通过js的数组来模拟封装栈结构的，所以完全可以直接通过操作原始数组来获取最小值：

// 封装一个栈类
class Stack {
  constructor() {
    this.data = [] // 存放栈数据的变量
  }
  // 获取栈中最小元素
  get minimum () {
    return Math.min(...this.data)
  }
  // 其他属性和方法
  ...
}

除了最小值以外，获取栈结构中最大值的写法也同样如此。