概述

栈是一种高效的数据结构，因为数据只能在栈顶添加或删除，所以这样的操作很快，而且容易实现。

栈的实际应用非常广泛。在回溯问题中，它可以存储访问过的任务或路径、撤销的操作（后
面的章节讨论图和回溯问题时，我们会学习如何应用这个例子）。Java 和 C#用栈来存储变量和方
法调用，特别是处理递归算法时，有可能抛出一个栈溢出异常。

最后将学习使用栈的三个最著名的算法示例。首先是十进制转二进制问题，以及任意进制转换的算法；
然后是平衡圆括号问题；最后，我们会学习如何用栈解决汉诺塔问题。

本篇主要讲如何用 JavaScript 描述实现一个栈类。思维导图如下，具体细节见参考书籍，实现及常见使用场景见详述部分。

详述

栈的实现

class Stack {
  constructor() {
    this.dataStore = [];
    this.top = 0;
  }
  push(element) {
    this.dataStore[this.top++] = element;
  }
  pop() {
    return this.dataStore[--this.top];
  }
  peek() {
    return this.dataStore[this.top - 1];
  }
  clear() {
    this.top = 0;
  }
  length() {
    return this.top;
  }
}

// 测试
let s = new Stack();
s.push("ali");
s.push("baidu");
s.push("tengxun");
console.log(s.length()); // 3
let poped = s.pop();
console.log(poped); // tengxun
console.log(s.length()); // 2
let peeked = s.peek();
console.log("peeked: " + peeked); // peeked: baidu

使用 Stack 类

数制间的相互转换

利用栈将一个数字从一种数值转换成另一种数制。

// 十进制整数转成任何进制
function mulBase(num, base) {
  const DIGITS = "0123456789ABCDEF";
  let s = new Stack();
  do {
    s.push(num % base);
    num = Math.floor(num / base);
  } while (num > 0);

  let converted = "";
  while (s.length() > 0) {
    converted += DIGITS[s.pop()];
  }
  return converted;
}

console.log(mulBase(100345, 2)); // 11000011111111001
console.log(mulBase(100345, 8)); // 303771
console.log(mulBase(100345, 16)); // 187F9
console.log(mulBase(5, 2)); // 101

回文判断

回文是指这样一种现象：一个单词、短语或数字，从前往后写和从后往前写都是一样的。例如，“dad”、“racecar”、1001。

// 判断给定字符串是否是回文
function isPalindrome(word) {
  let s = new Stack();
  for (let i = 0; i < word.length; i++) {
    s.push(word[i]);
  }
  let rword = "";
  while (s.length() > 0) {
    rword += s.pop();
  }
  return word === rword;
}
// 实现二
function isPalindrome2(word) {
  word = word + "";
  return (
    word ===
    word
      .split("")
      .reverse()
      .join("")
  );
}

console.log("hello: " + isPalindrome("hello"));
console.log("racecar: " + isPalindrome("racecar"));
console.log("1001: " + isPalindrome(1001));

递归演示

下面是一个递归函数，可以计算任何数字的阶乘：

function factorial(n) {
  if (n === 0) {
    return 1;
  } else {
    return n * factorial(n - 1);
  }
}

function fact(n) {
  let s = new Stack();
  while (n > 1) {
    s.push(n--);
  }
  let product = 1;
  while (s.length() > 0) {
    product *= s.pop();
  }
  return product;
}

console.log("factorial: " + factorial(5));
console.log("fact: " + fact(5));
// factorial: 120
// fact: 120

意外收获

浮点数怎么转换成二进制，怎么转成任意进制？

小数部分计算方法：
乘2取整法，即每一步将十进制小数部分乘以2，所得积的小数点左边的数字（0或1）作为二进制表示法中的数字，直到满足你的精确度为止。
0.874的转换过程（取精度为6位）：
0.874*2＝1.748 小数点左边为 1
0.748*2＝1.496 小数点左边为 1
0.496*2＝0.992 小数点左边为 0
0.992*2＝1.984 小数点左边为 1
0.984*2＝1.968 小数点左边为 1
0.968*2＝1.936 小数点左边为 1
十进制：123.874 二进制：1111011.110111

回文古诗验证？
如下图：

练习

更多练习及实现答案请参考下一篇数据结构——栈（练习题及实现）

参考

《数据结构与算法 JavaScript 描述》
《学习 JavaScript 数据结构与算法（第 2 版）》

写给自己看的博客

数据结构与算法@栈

概述

详述