栈与队列数据结构实现详解

今天golang学习网给大家带来了《JavaScript数据结构：栈与队列实现详解》，其中涉及到的知识点包括等等，无论你是小白还是老手，都适合看一看哦~有好的建议也欢迎大家在评论留言，若是看完有所收获，也希望大家能多多点赞支持呀！一起加油学习~

JavaScript中栈和队列是基于数组等原生语法实现的LIFO和FIFO线性结构；栈用push/pop实现O(1)操作，队列优选索引偏移法避免shift的O(n)开销，二者广泛应用于DFS/BFS、事件循环等场景。

JavaScript 数据结构是指用 JavaScript 语言组织、存储和操作数据的方式，它不是语言内置的“类库”，而是基于原生语法（如数组、对象、函数）构建的逻辑模型。栈和队列是两种基础的线性数据结构，它们的核心区别在于数据进出的规则：栈是后进先出（LIFO），队列是先进先出（FIFO）。

用数组实现栈（Stack）

栈常用 push() 和 pop() 操作模拟入栈和出栈，时间复杂度均为 O(1)。为保证封装性和语义清晰，建议封装成类或构造函数。

• 定义一个 Stack 类，内部用数组存储元素
• 提供 push(item)：向数组末尾添加元素
• 提供 pop()：移除并返回数组末尾元素；若为空，可返回 undefined 或抛错
• 补充辅助方法：peek()（查看栈顶）、isEmpty()（判断是否为空）、size()（返回长度）

示例：

class Stack {
  constructor() {
    this.items = [];
  }
  push(item) {
    this.items.push(item);
  }
  pop() {
    return this.items.pop();
  }
  peek() {
    return this.items[this.items.length - 1];
  }
  isEmpty() {
    return this.items.length === 0;
  }
  size() {
    return this.items.length;
  }
}

用数组实现队列（Queue）

队列需支持从一端入、另一端出。若只用 push() 和 shift()，shift() 在数组头部删除会导致 O(n) 时间复杂度。更优做法是用双指针模拟（类似循环队列思想），或直接使用数组 + 索引管理避免频繁移动元素。

• 基础实现可用 push() 入队、shift() 出队，适合小规模或教学场景
• 高性能实现：维护 head 和 tail 索引，用数组存储，不实际删除元素，仅移动索引；当空间不足时可扩容或清理已出队部分
• 必须提供 enqueue(item)（入队）、dequeue()（出队）、front()（看队首）、isEmpty()、size()

简易版示例：

class Queue {
  constructor() {
    this.items = [];
  }
  enqueue(item) {
    this.items.push(item);
  }
  dequeue() {
    return this.items.shift();
  }
  front() {
    return this.items[0];
  }
  isEmpty() {
    return this.items.length === 0;
  }
  size() {
    return this.items.length;
  }
}

用对象+指针实现更高效的队列（无数组移动）

避免 shift() 的性能损耗，可改用对象键值对 + 计数器，或用链表结构。但最简洁实用的方式是“索引偏移法”——用数组配合起始索引管理逻辑队首位置。

• 初始化时设 head = 0，items = []
• enqueue 仍用 push；dequeue 不删元素，只返回 items[head] 并递增 head
• 当 head 超过一定比例（如一半），可截取剩余部分重置 items 和 head，保持内存合理
• 此时 size() 应为 items.length - head

栈和队列的实际用途提示

理解它们不只是为了手写代码，更是为了识别问题模式：

• 函数调用堆栈、浏览器历史记录、括号匹配、深度优先搜索（DFS）天然契合栈
• 任务调度、广度优先搜索（BFS）、打印任务排队、消息中间件消费顺序依赖队列
• 现代 JS 中，Promise.then() 链、事件循环中的 microtask 队列，底层都体现队列思想
• 不必强求“完全手写”，关键是在需要控制存取顺序时，能想到该用哪种结构，并知道如何用 JS 表达

以上就是《栈与队列数据结构实现详解》的详细内容，更多关于的资料请关注golang学习网公众号！