JavaScript 数据结构与算法（三）栈结构

1. 栈结构概述

数组是一个线性结构，能够在任意位置插入和删除元素。然而，栈是一种受限制的线性结构，具有特殊的操作规则——后进先出(LIFO)，即新添加的元素总是在栈顶，移除时则是从栈顶开始。（LIFO - Last In, First Out）

栈的主要特点是先进后出，后进先出。其核心操作包括进栈和出栈，分别对应于arr.push()和arr.pop()。栈的特性使其在处理函数调用、递归以及数据优先级等场景中非常有用。下面将详细探讨栈的实现和应用。

2. 栈常见操作

栈的基本操作包括:

- push(): 将新元素压入栈顶。 - pop(): 移除栈顶元素并返回该元素。 - peek(): 读取栈顶元素而不修改栈结构。 - isEmpty(): 检查栈是否为空。 - size(): 返回栈中元素的个数。 - toString(): 将栈内容转换为字符串表示。

这些操作对应于数组的push、pop、peek等方法，但栈的操作有限制，仅允许在栈顶进行。

3. 栈在程序中的应用

栈的应用领域包括:

- **函数调用栈**: 函数在调用时将自身压入栈底，每次调用子函数时将父函数的上下文压入栈。例如，函数调用顺序A→B→C（深度优先）会按照C→B→A弹出处理。 - **递归**: 递归函数通过不断压入自身引用至栈顶实现调用，直到满足终止条件，避免深度过度导致栈溢出。 - **后缀表达式计算**: 栈常用于处理后缀表达式，通过一次性压入数据并按需弹出结果。

4. 栈操作合法性判断

题目：6,5,4,3,2,1按顺序进入栈，哪个出栈序列是非法的？

选项包括A、B、C、D四个选项。 分析结果显示选项C的出栈顺序3,4,6,5,2,1是非法的，因为按照原有入栈顺序6→5→4→3→2→1，只有选项C的部分出栈步骤高于入栈元素的实际深度。具体来说，3的出栈需先有4和5在栈内，而这些元素在选项C中未被正确保留。因此，选项C的出栈顺序不符合栈操作规则。

5. 基于数组实现栈结构

在JavaScript中，使用数组实现栈非常简单。以下是一个实现栈的类：

class StackArray {
  constructor() {
    this.items = [];
  }
  push(element) {
    this.items.push(element);
  }
  pop() {
    return this.items.pop();
  }
  peek() {
    return this.items[this.items.length - 1];
  }
  isEmpty() {
    return this.items.length === 0;
  }
  size() {
    return this.items.length;
  }
  clear() {
    this.items = [];
  }
  toString() {
    return this.items.toString();
  }
}

该实现通过数组的基本操作实现栈功能，操作简单且性能较好。栈的主操作包括push、pop、peek等，用户可以根据需要扩展其他功能。

6. 栈的应用-十进制转二进制

利用栈实现十进制转二进制的算法：依次除以2，将余数存储在栈中。最后从栈底读取并倒序排列即可得到二进制表示。但需注意算法细节和优化。以下是一个实现示例：

function dec2bin(dec) {
  const stack = new StackArray();
  while (dec > 0) {
    stack.push(dec % 2);
    dec = Math.floor(dec / 2);
  }
  let binaryString = '';
  while (!stack.isEmpty()) {
    binaryString += stack.pop().toString();
  }
  return binaryString;
}

该实现首先推导余数到栈中，最后反转栈中的元素顺序组合成二进制字符串。该算法的时间复杂度为O(log N)，其中N为输入数值，适用于较大数值的转换。算法的几何效率因栈操作而有所优势。

7. 栈结构的实现与保护

7.1 使用ES2015的Symbol实现类

Symbol在ES2015中引入后，为栈实现提供了更高的安全性。通过Symbol作为栈元素存储键，可以确保属性是私有化的。以下是一个实现示例：

const _items = Symbol('items');
class Stack {
  constructor() {
    this[_items] = [];
  }
  push(element) {
    this[_items].push(element);
  }
  pop() {
    return this[_items].pop();
  }
  peek() {
    return this[_items][this[_items].length - 1];
  }
  isEmpty() {
    return this[_items].length === 0;
  }
  size() {
    return this[_items].length;
  }
  clear() {
    this[_items] = [];
  }
  toString() {
    return this[_items].toString();
  }
}

此实现通过隐藏的Symbol键存储栈元素，保护了内部数据结构，防止外部干扰。这样的实现方式比传统对象实现更具安全性，适用于需要高安全性的场景。

7.2 使用WeakMap实现栈结构

WeakMap结合了对象引用和弱键的特性，适用于需要高效垃圾回收的场景。以下是一个基于WeakMap实现栈的示例：

class Stack {
  constructor() {
    this.map = new WeakMap();
  }
  push(element) {
    this.map.set(element, element);
  }
  pop() {
    return this.map.getAndRemove(true)?.value;
  }
  peek() {
    return this.map.get(this.map.size - 1)?.value;
  }
  isEmpty() {
    return this.map.size === 0;
  }
  size() {
    return this.map.size;
  }
  clear() {
    this.map.clear();
  }
}

此实现通过WeakMap的键值对存储栈元素，键为对象或数组，值可为任意类型。由于WeakKey仅存储弱引用，无需额外释放内存，简化了管理流程。此外，当引用释放时，WeakMap会自动移除对应的记录，保持内存健康。

8. 栈结构的核心优势

栈作为一种基础数据结构，具有以下核心优势：

- LIFO特性: 异或程序流程控制问题。 - 轻松管理上下文: 函数调用栈确保每个函数调用都有独特的上下文环境。 - 高效内存管理: 先进后出的特性确保内存利用 compact。

了解这些特性有助于在实际开发中更好地选择和使用栈结构，提升应用程序的效率和性能。