轻键快码

在 Javascript 中使用桟

轻键快码 数据结构

堆栈(英语:stack)又称为栈或堆叠,是计算机科学中一种特殊的串列形式的数据结构,其特殊之处在于只能允许在链接串列或阵列的一端(称为堆叠顶端指标,英语:top)进行加入数据(英语:push)和输出数据(英语:pop)的运算。另外栈也可以用一维数组或连结串列的形式来完成。堆叠的另外一个相对的操作方式称为伫列。由于堆叠数据结构只允许在一端进行操作,因而按照后进先出(LIFO, Last In First Out)的原理运作。wiki

在 Javascript 中实现一个桟

要实现一个桟,首先确定它的属性和方法,一个桟需要一个用于存储数据的地方,用数组即可,以及操作桟中数据的方法,这些方法主要有3个。 一个将数据压入的方法 push() ,一个将数据弹出的方法 pop() ,和返回栈顶数据的方法 peek()

class Stack {
  constructor (datas = []) {
    this.datas = datas
    this.top = datas.length
  }
  // 返回桟中所有的数据
  elements () {
    return this.datas.join(', ')
  }
  // 向桟顶压入一个数据
  push (data) {
    if (!data) return
    this.datas[this.top++] = data
    return true
  }
  // 弹出栈顶数据
  pop () {
    return this.datas[--this.top]
  }
  // 返回栈顶数据
  peek () {
    return this.datas[this.top - 1]
  }
  // 返回桟中数据多少
  length () {
    return this.top
  }
  // 清空桟
  clear () {
    this.top = 0
  }
}

使用桟来判断回文

我们可以通过先将单词或数字从左到右依次压入一个桟中,完成后桟中就反转保存的了这个单词或数字,然后在将桟桟中数据弹出组成一个新的单词或数字与原来的进行比较,就可以判断它是否是回文了。

function isPalindrome (data) {
  if (!data) return
  const s = new Stack()
  for (let i = 0; i < data.length; i++) {
    s.push(data[i])
  }
  let temp = ''
  while (s.length()) {
    temp += s.pop()
  }
  return temp === data
}

console.log(isPalindrome('wow')) // true
console.log(isPalindrome('898')) // true
console.log(isPalindrome('abc')) // false

桟的应用