栈

本文共--字 阅读约--分钟 | 浏览: -- Last Updated: 2021-04-22

栈是一种特殊的列表，栈内的元素只能通过列表的一端访问，这一端称为栈顶。栈被称为一种后入先出 (LIFO, last-in-first-out) 的数据结构，由于这一点，所有任何不在栈顶的元素都无法访问，为了得到栈底的元素，必须先拿掉上面的元素。

对栈的两种主要操作是将一个元素压入栈和将一个元素弹出栈。入栈使用 push 方法，出栈使用 pop 方法；另一个常用的操作是预览栈顶的元素，pop 方法虽然可以访问栈顶的元素，但是调用该方法后，栈顶元素也从栈中被永久性地删除了，peek 方法则只返回栈顶元素，而不删除它。

为了记录栈顶元素的位置，同时也为了标记哪里可以加入新元素，我们使用变量 top，当向栈内压入元素时该变量增大，从栈内弹出元素时，该变量减小。

除了以上介绍的，栈还有其他方法和属性，clear 方法清除栈内所有元素，length 方法返回栈内元素的个数，还定义了一个 empty 属性，用以表示栈内是否还有元素，不过使用 length 属性也可以达到同样的目的。

栈的实现

function Stack() {
  this.dataStore = [];
  this.top = 0;
  this.push = push;
  this.pop = pop;
  this.peek = peek;
  this.length = length;
  this.clear = clear;
}

function push(element) {
  this.dataStore[this.top++] = element;
}

function pop() {
  return this.dataStore[--this.top]
}

function peek() {
  return this.dataStore[this.top - 1]
}

function length() {
  return this.top
}

function clear() {
  this.top = 0;
}

测试Stack类的实现：

// example 1
var s = new Stack()
s.push('David')
s.push('Raymond')
s.push('Bryan')
console.log('length:  ' + s.length()); // 3
console.log(s.peek()); // Bryan

var popped = s.pop()
console.log('The popped element is: ' + popped); // Bryan
console.log(s.top);
// 此时虽然 dataStore的数据没有被改变 ['David', 'Raymond', 'Bryan']
// 但是 top 的值被改变为2了
// 之后的push就是将 Bryan 替换成新元素，dataStore[top++] = '新值'
// peek就是返回 dataStore[top-1] =  dataStore[1] = 'Raymond'
// 相当于通过暴露出来的方法 是永远无法再次访问到被pop的 'Bryan' 了

console.log(s.peek()); // Raymond
s.push('Cynthia')
console.log(s.peek()); // Cynthia

s.clear()
console.log('length:  ' + s.length()); // 0
console.log(s.peek()); // undefined
s.push('Clayton')
console.log(s.peek()); // Clayton

使用 Stack 类

数制间的相互转换

可以利用栈将十进制数字转换成二至十六进制的数字。

  • 1、最高位为 n % b，将此为压入栈
  • 2、使用 n / b 向下取整代替 n。
  • 3、重复1和2，直到 n = 0。
  • 4、将栈内元素弹出，直到栈为空，依次将这些元素排列，就得到转换后的数字的字符串形式。

原理如下：

实现如下：

function mulBase(num, base) {
  if (base > 16 || base < 2) {
    console.log('暂不支持该进制：' + base);
    return
  }
  var s = new Stack();
  do {
    s.push(num % base)
    num = Math.floor(num / base)
  } while (num > 0)
  var result = ''
  while(s.length() > 0) {
    var tmp = s.pop()
    if (base > 10 && tmp > 9) {
      tmp = String.fromCharCode(tmp + 55) // 10变成65 通过fromCharCode变成 'A'
    }
    result += tmp
  }
  return result
}

console.log(mulBase(32, 2));  // 100000
console.log(mulBase(125, 8)); // 175
console.log(mulBase(255, 16)); // FF
console.log(mulBase(2607, 16)); // A2F
console.log(mulBase(121, 11)); // 100

回文

回文指这样一种现象：一个单词、短语和数字，从前往后写和从后往前写都是一样的，比如，“racecar” 、“1001” 、“A man, a plan, a canal: Panama”

使用栈可以轻松判断一个字符串是否是回文，我们将拿到的字符串的每个字符从左至右的顺序压入栈，当字符串的字符都入栈后，栈内就保存了一个反转后的字符串，第一个字符在栈底，然后持续弹出栈中的每个字符就可以得到一个新的字符串，该字符串与原来的字符串刚好相反，我们只需要比较这两个字符串是否相等即可。

function isPalindrome(word) {
  var s = new Stack();
  for (var i = 0; i < word.length; ++i) {
    s.push(word[i])
  }
  var rword = '';
  while (s.length() > 0) {
    rword += s.pop()
  }
  return word === rword;
}

console.log(isPalindrome('racecar')); // true
console.log(isPalindrome('plan')); // false

使用字符串与数组的转换也可以完成这个功能：

function isPalindrome2(word) {
  return word === word.split('').reverse().join('')
}

递归演示

使用栈来模拟计算 5! 的过程，即5的阶乘，首先将数字从5到1压入栈，然后使用一个循环，将数字挨个弹出连乘，就得到了正确的答案。

function factorial(n) {
  var s = new Stack();
  while (n > 1) {
    s.push(n--)
  }

  var product = 1;
  while (s.length() > 0) {
    product *= s.pop()
  }
  return product;
}