在 JavaScript 中如何拦截对象的读取、修改、删除操作？Vue3的响应式系统如何实现？本文将深入讲解 JavaScript 的元编程世界，探索 Proxy 和 Reflect 的奥秘。

前言：从Vue3的响应式说起

// Vue3的响应式数据实现原理
const reactive = (target) => {
    return new Proxy(target, {
        get(target, key, receiver) {
            track(target, key); // 依赖收集
            return Reflect.get(target, key, receiver);
        },
        set(target, key, value, receiver) {
            const result = Reflect.set(target, key, value, receiver);
            trigger(target, key); // 触发更新
            return result;
        }
    });
};

Vue3的响应式数据实现原理的背后，就是 Proxy 和 Reflect 。理解它们，我们就能真正掌握 JavaScript 元编程的能力。

理解Proxy与Reflect

什么是Proxy（代理）？

Proxy 对象用于创建一个对象的代理，从而实现对基本操作的拦截和自定义（如属性查找、赋值、枚举、函数调用等）。

Proxy工作流程示意图

┌─────────┐   操作请求   ┌─────────┐   转发操作    ┌─────────┐
│ 客户端   │───────────→ │  Proxy  │───────────→ │ 目标对象 │
│         │             │  代理    │             │         │
│         │←─────────── │         │←─────────── │         │
└─────────┘   响应结果   └─────────┘   实际结果    └─────────┘
                ↓                           ↓
         ┌─────────────┐            ┌─────────────┐
         │ 拦截和自定义  │            │ 原始行为     │
         │   （陷阱）   │            │             │
         └─────────────┘            └─────────────┘

什么是Reflect（反射）？

Reflect 是一个内置的对象，它提供拦截 JavaScript 操作的方法。这些方法与 Proxy 的陷阱方法一一对应。

为什么需要Reflect？

1. 统一的操作API
2. 更好的错误处理（返回布尔值而非抛出异常）
3. 与Proxy陷阱方法一一对应

代理基础：创建第一个代理

// 目标对象
const target = {
  name: '张三',
  age: 30
};

// 处理器对象（包含陷阱方法）
const handler = {
  // 拦截属性读取
  get(target, property, receiver) {

    // 添加自定义逻辑
    if (property === 'age') {
      return `${target[property]}岁`;
    }

    // 默认行为：使用Reflect
    return Reflect.get(target, property, receiver);
  },

  // 拦截属性设置
  set(target, property, value, receiver) {
    // 添加验证逻辑
    if (property === 'age' && (value < 0 || value > 150)) {
      console.warn('年龄必须在0-150之间');
      return false; // 返回false表示设置失败
    }

    // 默认行为：使用Reflect
    return Reflect.set(target, property, value, receiver);
  }
};

// 创建代理
const proxy = new Proxy(target, handler);

console.log(proxy.name);  // 张三
console.log(proxy.age);   // 30岁
console.log(target.age); // 30

13种可拦截的陷阱方法

完整陷阱方法概览

const completeHandler = {
  // 1. 属性访问拦截
  get(target, prop, receiver) {
    console.log(`get: ${prop}`);
    return Reflect.get(target, prop, receiver);
  },

  // 2. 属性赋值拦截
  set(target, prop, value, receiver) {
    console.log(`set: ${prop} = ${value}`);
    return Reflect.set(target, prop, value, receiver);
  },

  // 3. in操作符拦截
  has(target, prop) {
    console.log(`has: ${prop}`);
    return Reflect.has(target, prop);
  },

  // 4. delete操作符拦截
  deleteProperty(target, prop) {
    console.log(`delete: ${prop}`);
    return Reflect.deleteProperty(target, prop);
  },

  // 5. 构造函数调用拦截
  construct(target, args, newTarget) {
    console.log(`construct with args:`, args);
    return Reflect.construct(target, args, newTarget);
  },

  // 6. 函数调用拦截
  apply(target, thisArg, args) {
    console.log(`apply: thisArg=`, thisArg, 'args=', args);
    return Reflect.apply(target, thisArg, args);
  },

  // 7. Object.getOwnPropertyDescriptor拦截
  getOwnPropertyDescriptor(target, prop) {
    console.log(`getOwnPropertyDescriptor: ${prop}`);
    return Reflect.getOwnPropertyDescriptor(target, prop);
  },

  // 8. Object.defineProperty拦截
  defineProperty(target, prop, descriptor) {
    console.log(`defineProperty: ${prop}`, descriptor);
    return Reflect.defineProperty(target, prop, descriptor);
  },

  // 9. 原型访问拦截
  getPrototypeOf(target) {
    console.log('getPrototypeOf');
    return Reflect.getPrototypeOf(target);
  },

  // 10. 原型设置拦截
  setPrototypeOf(target, prototype) {
    console.log(`setPrototypeOf:`, prototype);
    return Reflect.setPrototypeOf(target, prototype);
  },

  // 11. 可扩展性判断拦截
  isExtensible(target) {
    console.log('isExtensible');
    return Reflect.isExtensible(target);
  },

  // 12. 防止扩展拦截
  preventExtensions(target) {
    console.log('preventExtensions');
    return Reflect.preventExtensions(target);
  },

  // 13. 自身属性枚举拦截
  ownKeys(target) {
    console.log('ownKeys');
    return Reflect.ownKeys(target);
  }
};

陷阱方法详细解析

1. get陷阱：属性访问拦截

get() 会在获取属性值的操作中被调用：

const getHandler = {
  get(target, property, receiver) {
    // 处理不存在的属性
    if (!(property in target)) {
      throw new Error(`属性不存在: ${property}`);
    }

    // 处理私有属性（约定以_开头的属性为私有）
    if (property.startsWith('_')) {
      throw new Error(`不能访问私有属性: ${property}`);
    }
    return Reflect.get(target, property, receiver);
  }
};

• 参数说明：
  1. target：目标对象
  2. property：引用的目标对象上的属性
  3. receiver：代理对象
• 返回值说明：返回值无限制

2. set陷阱：属性赋值拦截

set() 会在设置属性值的操作中被调用：

const setHandler = {
  set(target, property, value, receiver) {
    // 只读属性检查（约定以$开头的属性为只读）
    if (property.startsWith('$')) {
      throw new Error(`属性不可修改: ${property}`);
    }
    // 执行设置
    return Reflect.set(target, property, value, receiver);
  }
};

• 参数说明：
  1. target：目标对象
  2. property：引用的目标对象上的属性
  3. value：要给属性设置的值
  4. receiver：代理对象
• 返回值说明：返回 true 表示成功；返回false表示失败。

3. has陷阱：in操作符拦截

has() 会在 in 操作符中被调用：

const hasHandler = {
  has(target, property) {
    // 隐藏某些属性（不在in操作中暴露）
    const hiddenProperties = ['password', 'token', '_internal'];
    if (hiddenProperties.includes(property)) {
      console.log(`隐藏属性: ${property}`);
      return false;
    }

    // 虚拟属性（不存在但返回true）
    const virtualProperties = ['isAdmin', 'hasAccess'];
    if (virtualProperties.includes(property)) {
      console.log(`虚拟属性: ${property}`);
      return true;
    }

    return Reflect.has(target, property);
  }
};

• 参数说明：
  1. target：目标对象
  2. value：要给属性设置的值
• 返回值说明：返回布尔值表示属性是否存在，返回非布尔型会被转成布尔型。

注：Object.keys() 不受 has() 影响，仍会返回所有属性。

4. apply陷阱：函数调用拦截

apply() 会在调用函数时被调用：

const applyHandler = {
  apply(target, thisArg, argumentsList) {
    // 参数验证
    if (target.name === 'calculate') {
      if (argumentsList.length < 2) {
        throw new Error('calculate函数需要至少2个参数');
      }
      if (!argumentsList.every(arg => typeof arg === 'number')) {
        throw new Error('calculate函数的所有参数必须是数字');
      }
    }
    return Reflect.apply(target, thisArg, argumentsList);
  }
};

• 参数说明：
  1. target：目标对象
  2. thisArg：调用函数时的this参数
  3. argumentsList：调用函数时的参数列表
• 返回值说明：返回值无限制

5. construct陷阱：构造函数拦截

construct() 会在调用函数时被调用：

const constructHandler = {
  construct(target, argumentsList, newTarget) {
    // 单例模式：确保只有一个实例
    if (target._instance) {
      console.log('返回现有实例');
      return target._instance;
    }

    // 创建实例
    const instance = Reflect.construct(target, argumentsList, newTarget);

    // 为单例保存实例
    if (target.name === 'Singleton') {
      target._instance = instance;
    }

    // 为实例添加额外属性
    instance.createdAt = new Date();
    instance._id = Math.random().toString(36).substr(2, 9);

    console.log('创建新实例，ID:', instance._id);
    return instance;
  }
};

• 参数说明：
  1. target：目标构造函数
  2. argumentsList：传给目标构造函数的参数列表
  3. newTarget：最初被调用的构造函数
• 返回值说明：必须返回一个对象

6. ownKeys陷阱：影响Object.keys()等遍历

ownKeys() 会在Object.keys()及类似方法中被调用：

const ownKeysHandler = {
  ownKeys(target) {
    // 过滤掉以_开头的私有属性
    const keys = Reflect.ownKeys(target);
    return keys.filter(key => {
      if (typeof key === 'string') {
        return !key.startsWith('_');
      }
      return true;
    });
  }
};

• 参数说明：
  1. target：目标构造函数
• 返回值说明：必须返回一个包含字符串或符号的可枚举对象

7. getOwnPropertyDescriptor陷阱：影响Object.getOwnPropertyDescriptor()

getOwnPropertyDescriptor() 会在Object.getOwnPropertyDescriptor()方法中被调用：

const getOwnPropertyDescriptorHandler = {
  getOwnPropertyDescriptor(target, prop) {
    // 隐藏私有属性的描述符
    if (prop.startsWith('_')) {
      return undefined;
    }
    return Reflect.getOwnPropertyDescriptor(target, prop);
  }
};

• 参数说明：
  1. target：目标构造函数
  2. prop：引用的目标对象上的字符串属性
• 返回值说明：必须返回对象，或在属性不存在时返回 undefined

8. defineProperty陷阱：拦截Object.defineProperty()

defineProperty() 会在Object.defineProperty()方法中被调用：

const definePropertyHandler = {
  defineProperty(target, prop, descriptor) {
    // 防止修改只读属性
    if (prop === 'id' && target.id) {
      console.warn('id属性是只读的');
      return false;
    }
    return Reflect.defineProperty(target, prop, descriptor);
  }
};

• 参数说明：
  1. target：目标构造函数
  2. prop：引用的目标对象上的字符串属性
  3. descriptor：包含可选的enumrable、configurable、value、get 和 set 等定义的对象
• 返回值说明：必须返回布尔值，表示属性是否成功定义

9. deleteProperty陷阱：拦截delete操作

deleteProperty() 会在 delete 操作中被调用：

const deletePropertyHandler = {
  deleteProperty(target, prop) {
    // 防止删除重要属性
    const protectedProps = ['id', 'createdAt'];
    if (protectedProps.includes(prop)) {
      console.warn(`不能删除受保护的属性: ${prop}`);
      return false;
    }
    return Reflect.deleteProperty(target, prop);
  }
};

• 参数说明：
  1. target：目标构造函数
  2. property：引用的目标对象上的属性
• 返回值说明：必须返回布尔值，表示属性是否被成功删除

10. preventExtensions陷阱：拦截Object.preventExtensions()

preventExtensions() 会在 Object.preventExtensions() 方法中被调用：

const preventExtensionsHandler = {
  preventExtensions(target) {
    // 在阻止扩展前添加标记
    target._frozenAt = new Date();
    return Reflect.preventExtensions(target);
  }
};

• 参数说明：
  1. target：目标构造函数
• 返回值说明：必须返回布尔值，表示 target 是否已经不可扩展

11. getPrototypeOf陷阱：拦截Object.getPrototypeOf()

getPrototypeOf() 会在 Object.getPrototypeOf() 方法中被调用：

const getPrototypeOfHandler = {
  getPrototypeOf(target) {
    return Reflect.getPrototypeOf(target);
  }
};

• 参数说明：
  1. target：目标构造函数
• 返回值说明：必须返回对象或null

12. setPrototypeOf陷阱：拦截Object.setPrototypeOf()

setPrototypeOf() 会在 Object.setPrototypeOf() 方法中被调用：

const setPrototypeOfHandler = {
  setPrototypeOf(target, prototype) {
    return Reflect.setPrototypeOf(target, prototype);
  }
};

• 参数说明：
  1. target：目标构造函数
  2. property：引用的目标对象上的属性
• 返回值说明：必须返回布尔值，表示原型赋值是否成功

13. isExtensible陷阱：拦截Object.isExtensible()

isExtensible() 会在 Object.isExtensible() 方法中被调用：

const isExtensibleHandler = {
  isExtensible(targete) {
    return Reflect.isExtensible(targete);
  }
};

• 参数说明：
  1. target：目标构造函数
• 返回值说明：必须返回布尔值，表示 target 是否可扩展

可撤销代理

什么是可撤销代理？

可撤销代理（Revocable Proxy）是一种特殊的代理，它提供了一个 revoke() 方法，调用该方法后，代理将不再可用，所有对代理的操作都会抛出 TypeError，即：会中断代理对象和目标对象之间的联系。

const target = { name: 'zhangsan' };
const handler = {
  get() {
    return 'foo';
  }
}
// 创建可撤销代理
const { proxy, revoke } = Proxy.revocable(target, handler);

console.log(proxy.name); // 'zhangsan'

// 撤销代理
revoke();

// 代理已失效
try {
  console.log(proxy.name); // TypeError: Cannot perform 'get' on a proxy that has been revoked
} catch (error) {
  console.log('错误:', error.message);
}

实现响应式数据（Vue3原理）

// 简易版Vue3响应式系统
class ReactiveSystem {
  constructor() {
    this.targetMap = new WeakMap(); // 存储依赖关系
    this.effectStack = [];          // 当前正在执行的effect
    this.batchQueue = new Set();    // 批量更新队列
    this.isBatching = false;        // 是否处于批量更新模式
  }

  // 核心：创建响应式对象
  reactive(target) {
    return new Proxy(target, {
      get(target, key, receiver) {
        // 获取原始值
        const result = Reflect.get(target, key, receiver);

        // 依赖收集
        track(target, key);

        // 深度响应式（如果值是对象，继续代理）
        if (result && typeof result === 'object') {
          return reactive(result);
        }

        return result;
      },

      set(target, key, value, receiver) {
        // 获取旧值
        const oldValue = target[key];

        // 设置新值
        const result = Reflect.set(target, key, value, receiver);

        // 触发更新（值确实改变时才触发）
        if (oldValue !== value) {
          trigger(target, key);
        }

        return result;
      },

      // 处理删除操作
      deleteProperty(target, key) {
        const hasKey = key in target;
        const result = Reflect.deleteProperty(target, key);

        if (hasKey && result) {
          trigger(target, key);
        }

        return result;
      }
    });
  }

  // 依赖收集
  track(target, key) {
    if (this.effectStack.length === 0) return;

    let depsMap = this.targetMap.get(target);
    if (!depsMap) {
      depsMap = new Map();
      this.targetMap.set(target, depsMap);
    }

    let dep = depsMap.get(key);
    if (!dep) {
      dep = new Set();
      depsMap.set(key, dep);
    }

    // 收集当前正在执行的effect
    const activeEffect = this.effectStack[this.effectStack.length - 1];
    if (activeEffect) {
      dep.add(activeEffect);
      // effect也需要知道哪些依赖收集了它
      activeEffect.deps.push(dep);
    }
  }

  // 触发更新
  trigger(target, key) {
    const depsMap = this.targetMap.get(target);
    if (!depsMap) return;

    const dep = depsMap.get(key);
    if (dep) {
      // 如果是批量更新模式，加入队列
      if (this.isBatching) {
        dep.forEach(effect => this.batchQueue.add(effect));
      } else {
        // 立即执行所有依赖的effect
        dep.forEach(effect => {
          if (effect !== this.effectStack[this.effectStack.length - 1]) {
            effect.run();
          }
        });
      }
    }
  }

  // 创建effect（副作用）
  effect(fn) {
    const effect = new ReactiveEffect(fn, this);
    effect.run();

    // 返回停止函数
    const runner = effect.run.bind(effect);
    runner.effect = effect;
    runner.stop = () => effect.stop();

    return runner;
  }

  // 开始批量更新
  batchStart() {
    this.isBatching = true;
  }

  // 结束批量更新
  batchEnd() {
    this.isBatching = false;

    // 执行队列中的所有effect
    this.batchQueue.forEach(effect => {
      if (effect !== this.effectStack[this.effectStack.length - 1]) {
        effect.run();
      }
    });

    this.batchQueue.clear();
  }

  // computed计算属性
  computed(getter) {
    let value;
    let dirty = true;

    const runner = this.effect(() => {
      value = getter();
      dirty = false;
    });

    return {
      get value() {
        if (dirty) {
          runner();
        }
        return value;
      }
    };
  }

  // watch侦听器
  watch(source, callback, options = {}) {
    let getter;

    if (typeof source === 'function') {
      getter = source;
    } else {
      getter = () => this.traverse(source);
    }

    let oldValue;
    const job = () => {
      const newValue = runner();
      callback(newValue, oldValue);
      oldValue = newValue;
    };

    const runner = this.effect(getter, {
      lazy: true,
      scheduler: job
    });

    oldValue = runner();

    if (options.immediate) {
      job();
    }
  }

  // 深度遍历对象（用于watch）
  traverse(value, seen = new Set()) {
    if (typeof value !== 'object' || value === null || seen.has(value)) {
      return value;
    }

    seen.add(value);

    for (const key in value) {
      this.traverse(value[key], seen);
    }

    return value;
  }
}

// 响应式effect类
class ReactiveEffect {
  constructor(fn, scheduler) {
    this.fn = fn;
    this.scheduler = scheduler;
    this.deps = [];
    this.active = true;
  }

  run() {
    if (!this.active) return;

    try {
      this.scheduler.effectStack.push(this);
      return this.fn();
    } finally {
      this.scheduler.effectStack.pop();
    }
  }

  stop() {
    if (this.active) {
      // 从所有依赖中移除自己
      this.deps.forEach(dep => dep.delete(this));
      this.deps.length = 0;
      this.active = false;
    }
  }
}

实现不可变数据（immer.js原理）

// 简易版immer实现
class Immer {
  constructor(baseState) {
    this.baseState = baseState;
    this.draft = this.createDraft(baseState);
    this.isModified = false;
  }

  // 创建草稿（代理）
  createDraft(base) {
    // 如果不是对象，直接返回
    if (typeof base !== 'object' || base === null) {
      return base;
    }

    // 处理数组
    if (Array.isArray(base)) {
      return this.createArrayDraft(base);
    }

    // 处理对象
    return this.createObjectDraft(base);
  }

  // 创建对象草稿
  createObjectDraft(base) {
    const draft = Array.isArray(base) ? [] : {};

    // 复制所有属性
    for (const key in base) {
      if (base.hasOwnProperty(key)) {
        draft[key] = this.createDraft(base[key]);
      }
    }

    // 创建代理
    return new Proxy(draft, {
      get: (target, prop, receiver) => {
        // 特殊属性处理
        if (prop === '__immer_draft__') return true;
        if (prop === '__immer_original__') return base;

        return Reflect.get(target, prop, receiver);
      },

      set: (target, prop, value, receiver) => {
        this.isModified = true;

        // 如果新值是普通值，直接设置
        if (typeof value !== 'object' || value === null) {
          return Reflect.set(target, prop, value, receiver);
        }

        // 如果新值是草稿，获取其最终状态
        if (value.__immer_draft__) {
          value = this.finalize(value);
        }

        // 如果新值是对象，创建新的草稿
        const newDraft = this.createDraft(value);
        return Reflect.set(target, prop, newDraft, receiver);
      },

      deleteProperty: (target, prop) => {
        this.isModified = true;
        return Reflect.deleteProperty(target, prop);
      }
    });
  }

  // 创建数组草稿（需要特殊处理）
  createArrayDraft(base) {
    const draft = this.createObjectDraft(base);

    // 代理数组方法
    const arrayMethods = ['push', 'pop', 'shift', 'unshift', 'splice', 'sort', 'reverse'];

    arrayMethods.forEach(method => {
      const originalMethod = Array.prototype[method];

      draft[method] = function (...args) {
        this.isModified = true;
        return originalMethod.apply(this, args);
      }.bind({ isModified: false }); // 这里简化处理
    });

    return draft;
  }

  // 获取草稿
  getDraft() {
    return this.draft;
  }

  // 完成修改，生成新状态
  produce(producer) {
    // 执行生产者函数
    producer(this.draft);

    // 如果没有修改，返回原状态
    if (!this.isModified) {
      return this.baseState;
    }

    // 最终化草稿，生成新状态
    return this.finalize(this.draft);
  }

  // 最终化草稿（将草稿转换为普通对象）
  finalize(draft) {
    // 如果不是草稿，直接返回
    if (!draft || !draft.__immer_draft__) {
      return draft;
    }

    const original = draft.__immer_original__;
    const result = Array.isArray(original) ? [] : {};
    let hasChanges = false;

    // 收集所有键（包括原对象和新对象）
    const allKeys = new Set([
      ...Object.keys(original || {}),
      ...Object.keys(draft)
    ]);

    for (const key of allKeys) {
      const originalValue = original ? original[key] : undefined;
      const draftValue = draft[key];

      // 如果属性被删除
      if (!(key in draft)) {
        hasChanges = true;
        continue;
      }

      // 如果值是草稿，递归最终化
      if (draftValue && draftValue.__immer_draft__) {
        const finalized = this.finalize(draftValue);
        if (finalized !== originalValue) {
          hasChanges = true;
          result[key] = finalized;
        } else {
          result[key] = originalValue;
        }
      }
      // 如果值被修改
      else if (draftValue !== originalValue) {
        hasChanges = true;
        result[key] = draftValue;
      }
      // 值未修改
      else {
        result[key] = originalValue;
      }
    }

    return hasChanges ? result : original;
  }
}

// 简化API
function produce(baseState, producer) {
  const immer = new Immer(baseState);
  return immer.produce(producer);
}

结语

Proxy和Reflect开启了JavaScript元编程的新篇章，它们不仅是框架开发的利器，也是理解现代JavaScript运行时特性的关键。对于文章中错误的地方或者有任何问题，欢迎在评论区留言讨论！

当函数调用层层嵌套，JavaScript 引擎如何管理这些调用？当事件循环处理异步任务时，背后的数据结构是什么？本文将深入探讨栈、队列和树在前端开发中的核心应用。

前言：从函数调用说起

// 一个简单的函数调用栈示例
function funcA() {
    console.log('进入函数A');
    funcB();
    console.log('离开函数A');
}

function funcB() {
    console.log('进入函数B');
    funcC();
    console.log('离开函数B');
}

function funcC() {
    console.log('进入函数C');
    console.log('离开函数C');
}

funcA();

这段代码的输出顺序是什么？进入函数A 进入函数B 进入函数C 离开函数C 离开函数B 离开函数A 。

这种"先进后出"的执行顺序，正是栈的典型特征。

栈（Stack）的实现与应用

栈的基本概念

栈 是一种后进先出（LIFO）的数据结构，就像一摞盘子，我们只能从最上面取放盘子。

栈的操作示意图

      push(3)      push(5)      pop() → 5
┌───┐    →    ┌───┐    →    ┌───┐    →    ┌───┐
│   │         │ 3 │         │ 5 │         │ 3 │
├───┤         ├───┤         ├───┤         ├───┤
│   │         │   │         │ 3 │         │   │
└───┘         └───┘         └───┘         └───┘
 空栈          栈底:3        栈顶:5        栈底:3

用数组实现栈

class ArrayStack {
  constructor(capacity = 10) {
    this.items = new Array(capacity);  // 底层数组
    this.top = -1;                     // 栈顶指针
    this.capacity = capacity;          // 栈容量
  }

  // 入栈操作
  push(element) {
    if (this.isFull()) {
      throw new Error('栈已满');
    }
    this.top++;
    this.items[this.top] = element;
    return this;
  }

  // 出栈操作
  pop() {
    if (this.isEmpty()) {
      throw new Error('栈为空');
    }
    const element = this.items[this.top];
    this.items[this.top] = undefined;  // 清理引用
    this.top--;
    return element;
  }

  // 查看栈顶元素（不弹出）
  peek() {
    if (this.isEmpty()) {
      return null;
    }
    return this.items[this.top];
  }

  // 判断栈是否为空
  isEmpty() {
    return this.top === -1;
  }

  // 判断栈是否已满
  isFull() {
    return this.top === this.capacity - 1;
  }

  // 获取栈大小
  get size() {
    return this.top + 1;
  }

  // 清空栈
  clear() {
    this.items = new Array(this.capacity);
    this.top = -1;
  }
}

用链表实现栈

class ListNode {
  constructor(value, next = null) {
    this.value = value;
    this.next = next;
  }
}

class LinkedListStack {
  constructor() {
    this.top = null;    // 栈顶节点
    this.length = 0;    // 栈长度
  }

  // 入栈操作
  push(element) {
    // 创建新节点，指向原来的栈顶
    const newNode = new ListNode(element, this.top);
    this.top = newNode;
    this.length++;
    return this;
  }

  // 出栈操作
  pop() {
    if (this.isEmpty()) {
      throw new Error('栈为空');
    }
    const value = this.top.value;
    this.top = this.top.next;  // 移动栈顶指针
    this.length--;
    return value;
  }

  peek() {
    if (this.isEmpty()) {
      return null;
    }
    return this.top.value;
  }

  isEmpty() {
    return this.top === null;
  }

  get size() {
    return this.length;
  }

  clear() {
    this.top = null;
    this.length = 0;
  }
}

数组栈 vs 链表栈

• 数组栈：内存连续，CPU缓存友好，访问速度快
• 链表栈：动态扩容，无容量限制，但内存不连续
• 实际选择：JavaScript 数组经过V8引擎优化，通常数组栈性能更好

栈的实际应用

应用1：函数调用栈模拟

class CallStackSimulator {
  constructor() {
    this.callStack = new ArrayStack(50);
    this.currentDepth = 0;
    this.maxDepth = 0;
  }

  // 函数调用
  callFunction(funcName) {
    const frame = {
      funcName,
      timestamp: Date.now(),
      localVars: {}
    };

    this.callStack.push(frame);
    this.currentDepth++;
    this.maxDepth = Math.max(this.maxDepth, this.currentDepth);

    console.log(`调用: ${funcName} (深度: ${this.currentDepth})`);
    this.printStack();

    return frame;
  }

  // 函数返回
  returnFromFunction() {
    if (this.callStack.isEmpty()) {
      console.log('调用栈已空');
      return null;
    }

    const frame = this.callStack.pop();
    const duration = Date.now() - frame.timestamp;
    this.currentDepth--;

    console.log(`返回: ${frame.funcName} (耗时: ${duration}ms)`);
    console.log(`剩余深度: ${this.currentDepth}`);

    return frame;
  }
}

队列（Queue）与双端队列（Deque）

队列（Queue）的基本概念

队列 是一种先进先出（FIFO）的数据结构，就像排队买票，先来的人先服务。

队列的操作示意图

      enqueue(3)    enqueue(5)    dequeue() → 3
┌───┬───┐  →  ┌───┬───┐  →  ┌───┬───┐  →  ┌───┬───┐
│   │   │     │ 3 │   │     │ 3 │ 5 │     │   │ 5 │
└───┴───┘     └───┴───┘     └───┴───┘     └───┴───┘
front rear   front↑rear    front rear↑     ↑front rear

双端队列（Deque）的基本概念

双端队列 允许在两端进行插入和删除操作，结合了栈和队列的特性。

双端队列的实现

class Deque {
  constructor(capacity = 10) {
    this.items = new Array(capacity);
    this.capacity = capacity;
    this.front = 0;
    this.rear = 0;
    this.count = 0;
  }

  // 前端添加
  addFront(element) {
    if (this.isFull()) {
      this._resize();
    }

    this.front = (this.front - 1 + this.capacity) % this.capacity;
    this.items[this.front] = element;
    this.count++;

    console.log(`前端添加: ${element}, front: ${this.front}`);
    return this;
  }

  // 后端添加
  addRear(element) {
    if (this.isFull()) {
      this._resize();
    }

    this.items[this.rear] = element;
    this.rear = (this.rear + 1) % this.capacity;
    this.count++;

    console.log(`后端添加: ${element}, rear: ${this.rear}`);
    return this;
  }

  // 前端删除
  removeFront() {
    if (this.isEmpty()) {
      throw new Error('队列为空');
    }

    const element = this.items[this.front];
    this.items[this.front] = undefined;
    this.front = (this.front + 1) % this.capacity;
    this.count--;

    console.log(`前端删除: ${element}, front: ${this.front}`);
    return element;
  }

  // 后端删除
  removeRear() {
    if (this.isEmpty()) {
      throw new Error('队列为空');
    }

    this.rear = (this.rear - 1 + this.capacity) % this.capacity;
    const element = this.items[this.rear];
    this.items[this.rear] = undefined;
    this.count--;

    console.log(`后端删除: ${element}, rear: ${this.rear}`);
    return element;
  }

  // 查看前端
  peekFront() {
    if (this.isEmpty()) {
      return null;
    }
    return this.items[this.front];
  }

  // 查看后端
  peekRear() {
    if (this.isEmpty()) {
      return null;
    }
    const index = (this.rear - 1 + this.capacity) % this.capacity;
    return this.items[index];
  }

  // 扩容
  _resize() {
    const newCapacity = this.capacity * 2;
    const newItems = new Array(newCapacity);

    // 复制元素到新数组
    for (let i = 0; i < this.count; i++) {
      const index = (this.front + i) % this.capacity;
      newItems[i] = this.items[index];
    }

    this.items = newItems;
    this.front = 0;
    this.rear = this.count;
    this.capacity = newCapacity;

    console.log(`队列扩容: ${this.capacity / 2} → ${newCapacity}`);
  }

  isEmpty() {
    return this.count === 0;
  }

  isFull() {
    return this.count === this.capacity;
  }

  get size() {
    return this.count;
  }
}

队列的实际应用

应用1：任务调度器

class TaskScheduler {
  constructor() {
    this.taskQueue = new CircularQueue(100);  // 任务队列
    this.currentTask = null;
    this.taskId = 0;
    this.isProcessing = false;
  }

  // 创建任务
  createTask(name, duration, priority = 0) {
    return {
      id: ++this.taskId,
      name,
      duration,      // 任务执行时间（毫秒）
      priority,      // 优先级（数值越小优先级越高）
      status: 'pending',
      createdAt: Date.now(),
      startedAt: null,
      completedAt: null
    };
  }

  // 添加任务到队列
  addTask(task) {
    this.taskQueue.enqueue(task);
    console.log(`任务添加: ${task.name} (ID: ${task.id})`);
    this.printQueueStatus();

    // 如果没有正在处理的任务，开始处理
    if (!this.isProcessing) {
      this.processNextTask();
    }
  }

  // 处理下一个任务
  async processNextTask() {
    if (this.taskQueue.isEmpty()) {
      this.isProcessing = false;
      console.log('所有任务处理完成！');
      return;
    }

    this.isProcessing = true;
    this.currentTask = this.taskQueue.dequeue();
    this.currentTask.status = 'processing';
    this.currentTask.startedAt = Date.now();

    console.log(`\n开始处理任务: ${this.currentTask.name}`);
    console.log(`任务ID: ${this.currentTask.id}, 预计耗时: ${this.currentTask.duration}ms`);
    this.printQueueStatus();

    // 模拟任务执行
    await this.executeTask(this.currentTask);

    // 任务完成
    this.currentTask.completedAt = Date.now();
    this.currentTask.status = 'completed';
    const totalTime = this.currentTask.completedAt - this.currentTask.startedAt;

    console.log(`任务完成: ${this.currentTask.name}`);
    console.log(`实际耗时: ${totalTime}ms`);

    // 处理下一个任务
    setTimeout(() => {
      this.processNextTask();
    }, 0);
  }

  // 模拟任务执行
  executeTask(task) {
    return new Promise(resolve => {
      setTimeout(() => {
        resolve();
      }, task.duration);
    });
  }
}

树（Tree）的实现与应用

树的基本概念

树是一种分层的数据结构，由节点和边组成。每个节点有零个或多个子节点，没有父节点的节点称为根节点；没有子节点的节点称为叶子节点。

二叉树结构示意图

        A (根节点)
       / \
      B   C
     / \   \
    D   E   F
   /
  G

术语解释：

• 根节点: A
• 叶子节点: E, F, G
• 深度: 节点G的深度是3
• 高度: 树的高度是3
• 子树: B、D、E、G构成一个子树

二叉树的实现

class TreeNode {
  constructor(value) {
    this.value = value;    // 节点值
    this.left = null;      // 左子节点
    this.right = null;     // 右子节点
    this.parent = null;    // 父节点（可选）
  }

  // 判断是否为叶子节点
  isLeaf() {
    return this.left === null && this.right === null;
  }

  // 判断是否有左子节点
  hasLeft() {
    return this.left !== null;
  }

  // 判断是否有右子节点
  hasRight() {
    return this.right !== null;
  }

  // 获取高度
  getHeight() {
    const leftHeight = this.left ? this.left.getHeight() : 0;
    const rightHeight = this.right ? this.right.getHeight() : 0;
    return Math.max(leftHeight, rightHeight) + 1;
  }
}

二叉树遍历算法

class BinaryTree {
  constructor() {
    this.root = null;  // 根节点
  }

  // 前序遍历：根 → 左 → 右
  preorderTraversal(callback) {
    const result = [];
    this._preorder(this.root, callback, result);
    return result;
  }

  _preorder(node, callback, result) {
    if (node === null) return;

    // 访问当前节点
    if (callback) callback(node);
    result.push(node.value);

    // 遍历左子树
    this._preorder(node.left, callback, result);

    // 遍历右子树
    this._preorder(node.right, callback, result);
  }

  // 中序遍历：左 → 根 → 右（对二叉搜索树会得到有序序列）
  inorderTraversal(callback) {
    const result = [];
    this._inorder(this.root, callback, result);
    return result;
  }

  _inorder(node, callback, result) {
    if (node === null) return;

    // 遍历左子树
    this._inorder(node.left, callback, result);

    // 访问当前节点
    if (callback) callback(node);
    result.push(node.value);

    // 遍历右子树
    this._inorder(node.right, callback, result);
  }

  // 后序遍历：左 → 右 → 根
  postorderTraversal(callback) {
    const result = [];
    this._postorder(this.root, callback, result);
    return result;
  }

  _postorder(node, callback, result) {
    if (node === null) return;

    // 遍历左子树
    this._postorder(node.left, callback, result);

    // 遍历右子树
    this._postorder(node.right, callback, result);

    // 访问当前节点
    if (callback) callback(node);
    result.push(node.value);
  }

  // 层序遍历：按层级从上到下，从左到右
  levelOrderTraversal(callback) {
    if (this.root === null) return [];

    const result = [];
    const queue = new CircularQueue(100);
    queue.enqueue(this.root);

    while (!queue.isEmpty()) {
      const node = queue.dequeue();

      // 访问当前节点
      if (callback) callback(node);
      result.push(node.value);

      // 将子节点加入队列
      if (node.left) {
        queue.enqueue(node.left);
      }
      if (node.right) {
        queue.enqueue(node.right);
      }
    }

    return result;
  }

  // 深度优先搜索（DFS）
  dfs(targetValue) {
    return this._dfs(this.root, targetValue);
  }

  _dfs(node, targetValue) {
    if (node === null) return null;

    // 检查当前节点
    if (node.value === targetValue) {
      return node;
    }

    // 搜索左子树
    const leftResult = this._dfs(node.left, targetValue);
    if (leftResult !== null) {
      return leftResult;
    }

    // 搜索右子树
    return this._dfs(node.right, targetValue);
  }

  // 广度优先搜索（BFS）
  bfs(targetValue) {
    if (this.root === null) return null;

    const queue = new CircularQueue(100);
    queue.enqueue(this.root);

    while (!queue.isEmpty()) {
      const node = queue.dequeue();

      // 检查当前节点
      if (node.value === targetValue) {
        return node;
      }

      // 将子节点加入队列
      if (node.left) {
        queue.enqueue(node.left);
      }
      if (node.right) {
        queue.enqueue(node.right);
      }
    }
    return null;
  }
}

数据结构选择的关键因素

访问模式

• 随机访问：数组（O(1)）
• 顺序访问：链表、栈、队列
• 层级访问：树

操作频率

• 频繁插入/删除开头：链表
• 频繁插入/删除两端：双端队列
• 频繁随机访问：数组

内存考虑

• 内存连续：数组（缓存友好）
• 内存分散：链表（无扩容成本）
• 动态大小：链表、树

结语

本文讲解了栈、队列和树的实现与应用，理解这些数据结构，不仅能帮助我们在面试中表现出色，更能让我们在实际开发中写出更高效、更可靠的代码。对于文章中错误的地方或者有任何问题，欢迎在评论区留言讨论！

数组在 JavaScript 中如此方便，为什么我们还需要链表呢？当 V8 引擎处理数组时，链表又在哪些场景下更有优势？本篇文章将深入探讨数据结构的核心差异。

前言：从一道面试题说起

// 面试题：如何高效地从大型数据集合中频繁插入和删除元素？
const data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

// 场景1：在数组开头插入元素（性能如何？）
data.unshift(0); // 需要移动所有元素！

// 场景2：在数组中间删除元素（性能如何？）
data.splice(5, 1); // 需要移动一半的元素！

// 场景3：只需要顺序访问数据
for (let i = 0; i < data.length; i++) {
    console.log(data[i]); // 数组很快！
}

那么问题来了：有没有一种数据结构，插入和删除快，顺序访问也快？当然有，答案就是：链表！ 数组和链表是编程中最基础的两种数据结构，理解它们的差异能帮助我们在不同场景下做出最优选择。

理解数组与链表的本质差异

内存结构对比

我们先通过一个简图，观察一下数组和链表在内存中的存储方式：

数组的内存结构（连续存储）

┌─────┬─────┬─────┬─────┬─────┐
│  0  │  1  │  2  │  3  │  4  │ ← 索引
├─────┼─────┼─────┼─────┼─────┤
│  10 │  20 │  30 │  40 │  50 │ ← 值
└─────┴─────┴─────┴─────┴─────┘
地址: 1000 1004 1008 1012 1016 （假设每个元素占4字节）

数组的存储特点：

1. 连续的内存空间
2. 通过索引直接计算地址：地址 = 基地址 + 索引 × 元素大小
3. 随机访问时间复杂度：O(1)

链表的内存结构（非连续存储）

      ┌─────┐    ┌─────┐    ┌─────┐
头 →  │  10 │ →  │  20 │ →  │  30 │ → null
      └─────┘    └─────┘    └─────┘
地址:  2000       3040       4080  （地址不连续）

链表的特点

1. 非连续的内存空间
2. 每个节点包含数据和指向下一个节点的指针
3. 随机访问需要遍历：O(n)
4. 插入和删除只需要修改指针：O(1)

时间复杂度对比表

数据结构	访问	插入开头	插入结尾	插入中间	删除开头	删除结尾	删除中间	搜索
数组	O(1)	O(n)	O(1)	O(n)	O(n)	O(1)	O(n)	O(n)
单向链表	O(n)	O(1)	O(n)	O(n)	O(1)	O(n)	O(n)	O(n)
双向链表	O(n)	O(1)	O(1)	O(n)	O(1)	O(1)	O(n)	O(n)
带尾指针的单向链表	O(n)	O(1)	O(1)	O(n)	O(1)	O(n)	O(n)	O(n)

关键差异总结

1. 随机访问元素：数组完胜（O(1) vs O(n)）
2. 插入/删除开头：链表完胜（O(1) vs O(n)）
3. 插入/删除结尾：数组和双向链表都很快
4. 插入/删除中间：都不快，但链表稍好
5. 内存使用：数组更紧凑，链表有指针开销

实现单向链表

基础节点类

class ListNode {
  constructor(value, next = null) {
    this.value = value;  // 存储的数据
    this.next = next;    // 指向下一个节点的指针
  }
}

单向链表类

class LinkedList {
  constructor() {
    this.head = null;    // 链表头节点
    this.length = 0;     // 链表长度
  }

  // 获取链表长度
  get size() {
    return this.length;
  }

  // 在链表头部添加节点
  addFirst(value) {
    // 创建新节点，指向原来的头节点
    const newNode = new ListNode(value, this.head);
    // 更新头节点为新节点
    this.head = newNode;
    this.length++;
    return this;
  }

  // 在链表尾部添加节点
  addLast(value) {
    const newNode = new ListNode(value);
    // 如果链表为空，新节点就是头节点
    if (this.head == null) {
      this.head = newNode;
    } else {
      // 找到最后一个节点
      let current = this.head;
      while (current.next != null) {
        current = current.next;
      }
      // 将新节点添加到末尾
      current.next = newNode;
    }
    this.length++;
    return this;
  }

  // 删除头节点
  removeFirst() {
    if (this.head == null) {
      return null;
    }
    const removedValue = this.head.value;
    this.head = this.head.next;
    this.length--;

    return removedValue;
  }

  // 删除尾节点
  removeLast() {
    if (this.head == null) {
      return null;
    }
    // 如果只有一个节点
    if (this.head.next == null) {
      const removedValue = this.head.value;
      this.head = null;
      this.length--;
      return removedValue;
    }
    // 找到倒数第二个节点
    let current = this.head;
    while (current.next.next != null) {
      current = current.next;
    }
    const removedValue = current.next.value;
    current.next = null;
    this.length--;
    return removedValue;
  }
}

单向链表的实际应用

应用1：浏览器历史记录

class BrowserHistory {
  constructor() {
    this.history = new LinkedList();
    this.current = null;
  }

  // 访问新页面
  visit(url) {
    // 如果当前有页面，添加到历史记录
    if (this.current !== null) {
      this.history.addLast(this.current);
    }
    this.current = url;
    console.log(`访问: ${url}`);
  }

  // 后退
  back() {
    if (this.history.size === 0) {
      console.log('无法后退：已经是第一页');
      return null;
    }
    const previous = this.history.removeLast();
    const current = this.current;
    this.current = previous;
    console.log(`后退: ${current} → ${previous}`);
    return previous;
  }

  // 查看历史记录
  showHistory() {
    console.log('历史记录:');
    this.history.forEach((url, index) => {
      console.log(`  ${index + 1}. ${url}`);
    });
    console.log(`当前: ${this.current}`);
  }
}

应用2：任务队列

class TaskQueue {
  constructor() {
    this.queue = new LinkedList();
  }

  // 添加任务
  enqueue(task) {
    this.queue.addLast(task);
    console.log(`添加任务: ${task.name}`);
  }

  // 执行下一个任务
  dequeue() {
    if (this.queue.isEmpty()) {
      console.log('任务队列为空');
      return null;
    }

    const task = this.queue.removeFirst();
    console.log(`执行任务: ${task.name}`);

    // 模拟任务执行
    try {
      task.execute();
    } catch (error) {
      console.error(`任务执行失败: ${error.message}`);
    }

    return task;
  }

  // 查看下一个任务（不执行）
  peek() {
    if (this.queue.isEmpty()) {
      return null;
    }
    return this.queue.get(0);
  }

  // 清空任务队列
  clear() {
    this.queue = new LinkedList();
    console.log('任务队列已清空');
  }

  // 获取队列长度
  get size() {
    return this.queue.size;
  }

  // 打印队列状态
  printQueue() {
    console.log('当前任务队列:');
    this.queue.forEach((task, index) => {
      console.log(`  ${index + 1}. ${task.name}`);
    });
  }
}

实现双向链表

基础节点类

class ListNode {
  constructor(value, next = null) {
    this.value = value;  // 存储的数据
    this.next = next;    // 指向下一个节点的指针
    this.prev = prev;    // 指向前一个节点的指针
  }
}

双向链表类

class DoublyLinkedList {
  constructor() {
    this.head = null;    // 链表头节点
    this.tail = null;    // 链表尾节点
    this.length = 0;     // 链表长度
  }

  get size() {
    return this.length;
  }

  // 在头部添加节点
  addFirst(value) {
    const newNode = new DoubleListNode(value, null, this.head);

    if (this.head !== null) {
      this.head.prev = newNode;
    } else {
      // 如果链表为空，新节点也是尾节点
      this.tail = newNode;
    }

    this.head = newNode;
    this.length++;
    return this;
  }

  // 在尾部添加节点
  addLast(value) {
    const newNode = new DoubleListNode(value, this.tail, null);

    if (this.tail !== null) {
      this.tail.next = newNode;
    } else {
      // 如果链表为空，新节点也是头节点
      this.head = newNode;
    }

    this.tail = newNode;
    this.length++;
    return this;
  }

  // 删除头节点
  removeFirst() {
    if (this.head === null) {
      return null;
    }

    const removedValue = this.head.value;

    if (this.head === this.tail) {
      // 只有一个节点
      this.head = null;
      this.tail = null;
    } else {
      this.head = this.head.next;
      this.head.prev = null;
    }

    this.length--;
    return removedValue;
  }

  // 删除尾节点
  removeLast() {
    if (this.tail === null) {
      return null;
    }

    const removedValue = this.tail.value;

    if (this.head === this.tail) {
      // 只有一个节点
      this.head = null;
      this.tail = null;
    } else {
      this.tail = this.tail.prev;
      this.tail.next = null;
    }

    this.length--;
    return removedValue;
  }
}

双向链表的实际应用

应用1：浏览器历史记录（增强版）

class EnhancedBrowserHistory {
  constructor() {
    this.history = new DoublyLinkedList();
    this.current = null;
    this.currentIndex = -1;
  }

  // 访问新页面
  visit(url) {
    console.log(`访问: ${url}`);

    // 如果当前位置不在末尾，需要截断后面的历史
    if (this.currentIndex < this.history.size - 1) {
      // 移除当前位置之后的所有历史
      const removeCount = this.history.size - 1 - this.currentIndex;
      for (let i = 0; i < removeCount; i++) {
        this.history.removeLast();
      }
    }

    // 添加新页面到历史记录
    if (this.current !== null) {
      this.history.addLast(this.current);
    }

    this.current = url;
    this.currentIndex = this.history.size;

    this.printHistory();
  }

  // 后退
  back() {
    if (this.currentIndex <= 0) {
      console.log('无法后退：已经是第一页');
      return null;
    }

    this.currentIndex--;
    this.current = this.history.get(this.currentIndex);

    console.log(`后退到: ${this.current}`);
    this.printHistory();

    return this.current;
  }

  // 前进
  forward() {
    if (this.currentIndex >= this.history.size - 1) {
      console.log('无法前进：已经是最后一页');
      return null;
    }

    this.currentIndex++;
    this.current = this.currentIndex === this.history.size ?
      '当前页面' : this.history.get(this.currentIndex);

    console.log(`前进到: ${this.current}`);
    this.printHistory();

    return this.current;
  }

  // 查看历史记录
  printHistory() {
    console.log('历史记录:');
    this.history.forEach((url, index) => {
      const marker = index === this.currentIndex ? '← 当前' : '';
      console.log(`  ${index + 1}. ${url} ${marker}`);
    });

    if (this.currentIndex === this.history.size) {
      console.log(`  当前: ${this.current}`);
    }
  }

  // 跳转到指定历史
  go(index) {
    if (index < 0 || index > this.history.size) {
      console.log(`无效的历史位置: ${index}`);
      return null;
    }

    this.currentIndex = index;
    this.current = index === this.history.size ?
      '当前页面' : this.history.get(index);

    console.log(`跳转到: ${this.current}`);
    this.printHistory();

    return this.current;
  }
}

核心要点总结

数组 vs 链表的本质差异

• 数组：连续内存，随机访问快(O(1))，插入删除慢(O(n))
• 链表：非连续内存，随机访问慢(O(n))，插入删除快(O(1))
• JavaScript数组：是特殊对象，V8引擎会优化存储方式

单向链表 vs 双向链表

• 单向链表：每个节点只有一个指针(next)，内存开销小
• 双向链表：每个节点有两个指针(prev, next)，支持双向遍历
• 选择：需要反向操作时用双向链表，否则用单向链表

结语

数据结构的选择没有绝对的对错，只有适合与否。理解数组和链表的差异，能帮助我们在实际开发中做出更明智的选择，写出更高效的代码。对于文章中错误的地方或者有任何问题，欢迎在评论区留言讨论！