背景

去年下半年，我在微信书架里加入了许多技术书籍，各种类别的都有，断断续续的读了一部分。

没有计划的阅读，收效甚微。

新年伊始，我准备尝试一下其他方式，比如阅读周。每月抽出1~2个非连续周，完整阅读一本书籍。

这个“玩法”虽然常见且板正，但是有效，已经坚持阅读四个月。

已读完书籍：《架构简洁之道》、《深入浅出的Node.js》、《你不知道的JavaScript（上卷）》、《你不知道的JavaScript（中卷）》、《你不知道的JavaScript（下卷）》。

当前阅读周书籍：《数据结构与算法JavaScript描述》。

栈

对栈的操作

栈是一种特殊的列表，栈内的元素只能通过列表的一端访问，这一端称为栈顶。咖啡厅内的一摞盘子是现实世界中常见的栈的例子。只能从最上面取盘子，盘子洗净后，也只能摞在这一摞盘子的最上面。栈被称为一种后入先出（LIFO, last-in-first-out）的数据结构。

对栈的两种主要操作是将一个元素压入栈和将一个元素弹出栈。入栈使用push()方法，出栈使用pop()方法。

另一个常用的操作是预览栈顶的元素。pop()方法虽然可以访问栈顶的元素，但是调用该方法后，栈顶元素也从栈中被永久性地删除了。peek()方法则只返回栈顶元素，而不删除它。

push()、pop()和peek()是栈的3个主要方法，但是栈还有其他方法和属性。clear()方法清除栈内所有元素，length属性记录栈内元素的个数。我们还定义了一个empty属性，用以表示栈内是否含有元素，不过使用length属性也可以达到同样的目的。

栈的实现

实现一个栈，当务之急是决定存储数据的底层数据结构。这里采用的是数组。

定义Stack类的构造函数：

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

用数组dataStore保存栈内元素，构造函数将其初始化为一个空数组。变量top记录栈顶位置，被构造函数初始化为0，表示栈顶对应数组的起始位置0。如果有元素被压入栈，该变量的值将随之变化。

先来实现push()方法。当向栈中压入一个新元素时，需要将其保存在数组中变量top所对应的位置，然后将top值加1，让其指向数组中下一个空位置。代码如下所示：

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

这里要特别注意++操作符的位置，它放在this.top的后面，这样新入栈的元素就被放在top的当前值对应的位置，然后再将变量top的值加1，指向下一个位置。

pop()方法恰好与push()方法相反——它返回栈顶元素，同时将变量top的值减1：

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

peek()方法返回数组的第top-1个位置的元素，即栈顶元素：

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

如果对一个空栈调用peek()方法，结果为undefined。这是因为栈是空的，栈顶没有任何元素。

length()方法通过返回变量top值的方式返回栈内的元素个数：

function length() {
  return this.top;
}

最后，可以将变量top的值设为0，轻松清空一个栈：

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

Stack类的完整实现：

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

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

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

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

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

function length() {
  return this.top;
}

使用Stack类

数制间的相互转换

可以利用栈将一个数字从一种数制转换成另一种数制。假设想将数字n转换为以b为基数的数字，实现转换的算法如下：

1. 最高位为n%b，将此位压入栈。
2. 使用n/b代替n。
3. 重复步骤1和2，直到n等于0，且没有余数。
4. 持续将栈内元素弹出，直到栈为空，依次将这些元素排列，就得到转换后数字的字符串形式。

使用栈，在JavaScript中实现该算法就是小菜一碟。下面就是该函数的定义，可以将数字转化为二至九进制的数字：

function mulBase(num, base) {
  var s = new Stack();
  do {
    s.push(num % base);
    num = Math.floor((num /= base));
  } while (num > 0);
  var converted = '';
  while (s.length() > 0) {
    converted += s.pop();
  }
  return converted;
}

回文

回文是指这样一种现象：一个单词、短语或数字，从前往后写和从后往前写都是一样的。比如，单词“dad”、“racecar”就是回文；如果忽略空格和标点符号，下面这个句子也是回文，“A man, a plan, a canal: Panama”；数字1001也是回文。

使用栈，可以轻松判断一个字符串是否是回文。我们将拿到的字符串的每个字符按从左至右的顺序压入栈。当字符串中的字符都入栈后，栈内就保存了一个反转后的字符串，最后的字符在栈顶，第一个字符在栈底。

利用前面定义的Stack类，判断给定字符串是否是回文的程序：

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();
  }
  if (word == rword) {
    return true;
  } else {
    return false;
  }
}

var word = 'hello';
if (isPalindrome(word)) {
  print(word + ' is a palindrome.');
} else {
  print(word + ' is not a palindrome.');
}
word = 'racecar';
if (isPalindrome(word)) {
  print(word + ' is a palindrome.');
} else {
  print(word + ' is not a palindrome.');
}

程序的输出为：

hello is not a palindrome.
racecar is a palindrome.

总结

栈就是和列表类似的一种数据结构，它可用来解决计算机世界里的很多问题。栈是一种高效的数据结构，因为数据只能在栈顶添加或删除，所以这样的操作很快，而且容易实现。栈的使用遍布程序语言实现的方方面面，从表达式求值到处理函数调用。

作者介绍
非职业「传道授业解惑」的开发者叶一一。
《趣学前端》、《CSS畅想》等系列作者。华夏美食、国漫、古风重度爱好者，刑侦、无限流小说初级玩家。
如果看完文章有所收获，欢迎点赞👍 | 收藏⭐️ | 留言📝。