跳到主要内容

4. 栈

栈数据结构​

栈是一种遵从后进先出（LIFO）原则的有序集合。新添加或待删除的元素都保存在栈的同一端，称作栈顶，另一端就叫栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。

栈也被用在编程语言的编译器和内存中保存变量、方法调用等，也被用于浏览器历史记录（浏览器的返回按钮）。

// 创建一个栈
class Stack {
  constructor() {
    this.items = []; // {1}
  }
}

我们需要一种数据结构来保存栈里的元素。可以选择数组（行{1}）。数组允许我们在任何位置添加或删除元素。由于栈遵循 LIFO 原则，需要对元素的插入和删除功能进行限制。接下来，要为栈声明一些方法。

  • push(element(s))：添加一个（或几个）新元素到栈顶。
  • pop()：移除栈顶的元素，同时返回被移除的元素。
  • peek()：返回栈顶的元素，不对栈做任何修改（该方法不会移除栈顶的元素，仅仅返回它）。
  • isEmpty()：如果栈里没有任何元素就返回 true，否则返回 false。
  • clear()：移除栈里的所有元素。
  • size()：返回栈里的元素个数。该方法和数组的 length 属性很类似。
class Stack {
  constructor() {
    this.items = []; // 定义一个栈
  }

  // 往栈里添加新的元素，该方法只添加元素到栈顶，也就是栈的末尾。
  push(element) {
    this.items.push(element);
  }

  // 移除栈里的元素，栈遵从LIFO原则，因此移出的是最后添加进去的元素。
  pop() {
    return this.items.pop();
  }

  // 查看栈顶元素，因为类内部是用数组保存元素的，所以访问数组的最后一个元素可以用length -1。
  peek() {
    return this.items[this.items.length - 1];
  }

  // 检查栈是否为空
  isEmpty() {
    return this.items.length === 0;
  }

  // 返回栈的长度
  size() {
    return this.items.length;
  }

  // 清空栈元素
  clear() {
    this.items = [];
  }
}

使用 Stack 类​

// 首先需要初始化Stack类，然后验证一下栈是否为空
const stack = new Stack();
console.log(stack.isEmpty()); // 输出为true
// 接下来，往栈里添加一些元素
stack.push(5); // [5]
stack.push(8); // [8, 5]

// 查看栈顶元素
console.log(stack.peek()); // 输出8

// 再添加一个元素
stack.push(11); // [11, 8, 5]
console.log(stack.size()); // 输出3
console.log(stack.isEmpty()); // 输出false

// 添加元素
stack.push(15); // [15, 11, 8, 5]
// 移除元素
stack.pop(); // [11, 8, 5]
stack.pop(); // [8, 5]
console.log(stack.size()); // 输出2

创建一个基于 JavaScript 对象的 Stack 类​

创建一个 Stack 类最简单的方式是使用一个数组来存储其元素。在处理大量数据的时候（这在现实生活中的项目里很常见），我们同样需要评估如何操作数据是最高效的。在使用数组时，大部分方法的时间复杂度是 O(n)。第 15 章我们将学习到更多有关算法复杂度的知识。O(n)的意思是，我们需要迭代整个数组直到找到要找的那个元素，在最坏的情况下需要迭代数组的所有位置，其中的 n 代表数组的长度。如果数组有更多元素的话，所需的时间会更长。另外，数组是元素的一个有序集合，为了保证元素排列有序，它会占用更多的内存空间。

如果我们能直接获取元素，占用较少的内存空间，并且仍然保证所有元素按照我们的需要排列，那不是更好吗？对于使用 JavaScript 语言实现栈数据结构的场景，我们也可以使用一个 JavaScript 对象来存储所有的栈元素，保证它们的顺序并且遵循 LIFO 原则。我们来看看如何实现这样的行为。

class Stack {
  constructor() {
    this.count = 0;
    this.items = {};
  }
  // 方法
}

在这个版本的 Stack 类中，我们将使用一个 count 属性来帮助我们记录栈的大小（也能帮助我们从数据结构中添加和删除元素）。

向栈中插入元素​

在基于数组的版本中，我们可以同时向 Stack 类中添加多个元素。由于现在使用了一个对象，这个版本的 push 方法只允许我们一次插入一个元素。下面是 push 方法的代码。

push(element) {
  this.items[this.count] = element;
  this.count++;
}

在 JavaScript 中，对象是一系列键值对的集合。要向栈中添加元素，我们将使用 count 变量作为 items 对象的键名，插入的元素则是它的值。在向栈插入元素后，我们递增 count 变量。

可以延用之前的示例来使用 Stack 类，并向其中插入元素 5 和 8。

const stack = new Stack();
stack.push(5);
stack.push(8);

在内部，items 包含的值和 count 属性如下所示。

items = {
  0: 5,
  1: 8,
};
count = 2;

验证一个栈是否为空和它的大小​

count 属性也表示栈的大小。因此，我们可以简单地返回 count 属性的值来实现 size 方法。

要验证栈是否为空，可以像下面这样判断 count 的值是否为 0。

// 获取栈的大小
size() {
    return this.count;
}
// 验证栈是否为空
isEmpty() {
    return this.count === 0;
}

从栈中弹出元素​

由于我们没有使用数组来存储元素，需要手动实现移除元素的逻辑。pop 方法同样返回了从栈中移除的元素，它的实现如下。

// 从栈中弹出元素
pop() {
    if (this.isEmpty()) { // {1}
        return undefined;
    }
    this.count--; // {2}
    const result = this.items[this.count]; // {3}
    delete this.items[this.count]; // {4}
    return result; // {5}
}

首先，我们需要检验栈是否为空（行{1}）。如果为空，就返回 undefined。如果栈不为空的话，我们会将 count 属性减 1（行{2}），并保存栈顶的值（行{3}），以便在删除它（行{4}）之后将它返回（行{5}）。

由于我们使用的是 JavaScript 对象，可以用 JavaScript 的 delete 运算符从对象中删除一个特定的值。我们使用如下内部的值来模拟 pop 操作。

我们使用如下内部的值来模拟 pop 操作。

items = {
  0: 5,
  1: 8,
};
count = 2;

要访问到栈顶的元素（即最后添加的元素 8），我们需要访问键值为 1 的位置。因此我们将 count 变量从 2 减为 1。这样就可以访问 items[1]，删除它，并将它的值返回了。

查看栈顶的值并将栈清空​

上一节我们学习了，要访问栈顶元素，需要将 count 属性减 1。那么我们来看看 peek 方法的代码。

peek() {
  if (this.isEmpty()) {
    return undefined;
  }
  return this.items[this.count -1];
}

要清空该栈，只需要将它的值复原为构造函数中使用的值即可。

clear() {
  this.items = {};
  this.count = 0;
}

我们也可以遵循 LIFO 原则，使用下面的逻辑来移除栈中所有的元素。

while (!this.isEmpty()) {
  this.pop();
}

创建 toString 方法​

在数组版本中，我们不需要关心 toString 方法的实现，因为数据结构可以直接使用数组已经提供的 toString 方法。对于使用对象的版本，我们将创建一个 toString 方法来像数组一样打印出栈的内容。

    toString() {
      if (this.isEmpty()) {
        return '';
      }
      let objString = `${this.items[0]}`; // {1}
      for (let i = 1; i < this.count; i++) { // {2}
        objString = `${objString}, ${this.items[i]}`; // {3}
      }
      return objString;
    }

如果栈是空的，我们只需返回一个空字符串即可。如果它不是空的，就需要用它底部的第一个元素作为字符串的初始值（行{1}），然后迭代整个栈的键（行{2}），一直到栈顶，添加一个逗号（,）以及下一个元素（行{3}）。如果栈只包含一个元素，行{2}和行{3}的代码将不会执行。

实现了 toString 方法后，我们就完成了这个版本的 Stack 类。这也是一个用不同方式写代码的例子。对于使用 Stack 类的开发者，选择使用基于数组或是基于对象的版本并不重要，两者都提供了相同的功能，只是内部实现很不一样。

保护数据结构内部元素​

在创建别的开发者也可以使用的数据结构或对象时，我们希望保护内部的元素，只有我们暴露出的方法才能修改内部结构。对于 Stack 类来说，要确保元素只会被添加到栈顶，而不是栈底或其他任意位置（比如栈的中间）。不幸的是，我们在 Stack 类中声明的 items 和 count 属性并没有得到保护，因为 JavaScript 的类就是这样工作的。

试着执行下面的代码。

const stack = new Stack();
console.log(Object.getOwnPropertyNames(stack)); // {1}
console.log(Object.keys(stack)); // {2}
console.log(stack.items); // {3}

行{1}和行{2}的输出结果是["count", "items"]。这表示 count 和 items 属性是公开的，我们可以像行{3}那样直接访问它们。根据这种行为，我们可以对这两个属性赋新的值。

本章使用 ES2015（ES6）语法创建了 Stack 类。ES2015 类是基于原型的。尽管基于原型的类能节省内存空间并在扩展方面优于基于函数的类，但这种方式不能声明私有属性（变量）或方法。另外，在本例中，我们希望 Stack 类的用户只能访问我们在类中暴露的方法。下面来看看其他使用 JavaScript 来实现私有属性的方法。

下划线命名约定​

一部分开发者喜欢在 JavaScript 中使用下划线命名约定来标记一个属性为私有属性。

class Stack {
  constructor() {
    this._count = 0;
    this._items = {};
  }
}

下划线命名约定就是在属性名称之前加上一个下划线（_）。不过这种方式只是一种约定，并不能保护数据，而且只能依赖于使用我们代码的开发者所具备的常识。

用 ES2015 的限定作用域 Symbol 实现类​

ES2015 新增了一种叫作 Symbol 的基本类型，它是不可变的，可以用作对象的属性。看看怎么用它在 Stack 类中声明 items 属性（我们将使用数组来存储元素以简化代码）。

const _items = Symbol("stackItems"); // {1}
class Stack {
  constructor() {
    this[_items] = []; // {2}
  }
  // 栈的方法
}

在上面的代码中，我们声明了 Symbol 类型的变量_items（行{1}），在类的 constructor 函数中初始化它的值（行{2}）。要访问_items，只需要把所有的 this.items 都换成 this[_items]。

这种方法创建了一个假的私有属性，因为 ES2015 新增的 Object.getOwnProperty-Symbols 方法能够取到类里面声明的所有 Symbols 属性。下面是一个破坏 Stack 类的例子。

const stack = new Stack();
stack.push(5);
stack.push(8);
let objectSymbols = Object.getOwnPropertySymbols(stack);
console.log(objectSymbols.length); // 输出1
console.log(objectSymbols); // [Symbol()]
console.log(objectSymbols[0]); // Symbol()
stack[objectSymbols[0]].push(1);
stack.print(); // 输出5, 8, 1

从以上代码可以看到，访问 stack[objectSymbols[0]]是可以得到_items 的。并且，_items 属性是一个数组，可以进行任意的数组操作，比如从中间删除或添加元素（使用对象进行存储也是一样的）。但我们操作的是栈，不应该出现这种行为。还有第三个方案。

用 ES2015 的 WeakMap 实现类​

有一种数据类型可以确保属性是私有的，这就是 WeakMap。我们会在第 8 章深入探讨 Map 这种数据结构，现在只需要知道 WeakMap 可以存储键值对，其中键是对象，值可以是任意数据类型。

如果用 WeakMap 来存储 items 属性（数组版本）, Stack 类就是这样的：

const items = new WeakMap(); // {1}
class Stack {
  constructor() {
    items.set(this, []); // {2}
  }
  push(element) {
    const s = items.get(this); // {3}
    s.push(element);
  }
  pop() {
    const s = items.get(this);
    const r = s.pop();
    return r;
  }
  // 其他方法
}

上面的代码片段解释如下。

  • 行{1}，声明一个 WeakMap 类型的变量 items。
  • 行{2}，在 constructor 中，以 this（Stack 类自己的引用）为键，把代表栈的数组存入 items。
  • 行{3}，从 WeakMap 中取出值，即以 this 为键（行{2}设置的）从 items 中取值。

现在我们知道了，items 在 Stack 类里是真正的私有属性。采用这种方法，代码的可读性不强，而且在扩展该类时无法继承私有属性。鱼和熊掌不可兼得！

用栈解决问题​

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

既然我们已经了解了 Stack 类的用法，不妨用它来解决一些计算机科学问题。本节，我们将介绍如何解决十进制转二进制问题，以及任意进制转换的算法。

从十进制到二进制​

现实生活中，我们主要使用十进制。但在计算科学中，二进制非常重要，因为计算机里的所有内容都是用二进制数字表示的（0 和 1）。没有十进制和二进制相互转化的能力，与计算机交流就很困难。

要把十进制转化成二进制，我们可以将该十进制数除以 2（二进制是满二进一）并对商取整，直到结果是 0 为止。举个例子，把十进制的数 10 转化成二进制的数字，过程大概是如下这样。 image

下面是对应的算法描述。

function decimalToBinary(decNumber) {
  const remStack = new Stack();
  let number = decNumber;
  let rem;
  let binaryString = "";

  while (number > 0) {
    // {1}
    rem = Math.floor(number % 2); // {2}
    remStack.push(rem); // {3}
    number = Math.floor(number / 2); // {4}
  }

  while (!remStack.isEmpty()) {
    // {5}
    binaryString += remStack.pop().toString();
  }
  return binaryString;
}

在这段代码里，当除法的结果不为 0 时（行{1}），我们会获得一个余数，并放到栈里（行{2}、行{3}）。然后让结果继续除以 2（行{4}）。另外请注意：JavaScript 有数值类型，但是它不会区分整数和浮点数。因此，要使用 Math.floor 函数仅返回除法运算结果的整数部分。最后，用 pop 方法把栈中的元素都移除，把出栈的元素连接成字符串（行{5}）。

进制转换算法​

我们可以修改之前的算法，使之能把十进制转换成基数为 2 ～ 36 的任意进制。除了把十进制数除以 2 转成二进制数，还可以传入其他任意进制的基数为参数，就像下面的算法这样。

function baseConverter(decNumber, base) {
  const remStack = new Stack();
  const digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"; // {6}
  let number = decNumber;
  let rem;
  let baseString = "";

  if (!(base >= 2 && base <= 36)) {
    return "";
  }

  while (number > 0) {
    rem = Math.floor(number % base);
    remStack.push(rem);
    number = Math.floor(number / base);
  }
  while (!remStack.isEmpty()) {
    baseString += digits[remStack.pop()]; // {7}
  }

  return baseString;
}

我们只需要改变一个地方。在将十进制转成二进制时，余数是 0 或 1；在将十进制转成八进制时，余数是 0 ～ 7；但是将十进制转成十六进制时，余数是 0 ～ 9 加上 A、B、C、D、E 和 F（对应 10、11、12、13、14 和 15）。因此，我们需要对栈中的数字做个转化才可以（行{6}和行{7}）。因此，从十一进制开始，字母表中的每个字母将表示相应的基数。字母 A 代表基数 11, B 代表基数 12，以此类推。