javascript

手写栈与队列：从基础结构到实战应用

By AI-Writer 18 min read

手写栈与队列：从基础结构到实战应用

**栈（Stack）和队列（Queue）**是计算机科学中最基础、最常用的两种线性数据结构。它们规则简单，却在函数调用、异步任务调度、浏览器历史回退、表达式求值等场景中无处不在。理解它们的底层实现，是掌握更复杂数据结构（如树、图）的必经之路。

本文将带你从零手写这四种结构：普通栈、普通队列、双端队列（Deque）以及优先级队列（Priority Queue），并配合两个经典实战案例加深理解。

栈（Stack）：后进先出

核心概念

栈遵循 **LIFO（Last In, First Out）**原则，即最后进入的元素最先被取出。你可以把它想象成一摞盘子：只能从最上面放盘子，也只能从最上面取盘子。

栈的三个核心操作：

操作作用时间复杂度
push向栈顶添加元素O(1)
pop移除并返回栈顶元素O(1)
peek查看栈顶元素（不移除）O(1)

手写 Stack 类

使用 JavaScript 数组作为底层存储，利用 Array.prototype.push 和 pop 天然契合栈的语义。

js
class Stack {
  constructor() {
    this.items = [];
  }

  // 入栈：向栈顶添加元素
  push(element) {
    this.items.push(element);
  }

  // 出栈：移除并返回栈顶元素；栈空时返回 undefined
  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 = [];
  }
}

实战：括号匹配

编译器在解析代码时，需要检查各类括号是否成对出现且正确嵌套。栈是解决这一问题的经典数据结构。

js
function isValidParentheses(str) {
  const stack = new Stack();
  const pairs = {
    ')': '(',
    ']': '[',
    '}': '{',
  };

  for (const char of str) {
    // 遇到左括号，入栈
    if (['(', '[', '{'].includes(char)) {
      stack.push(char);
    }
    // 遇到右括号，检查栈顶是否匹配
    else if ([')', ']', '}'].includes(char)) {
      if (stack.isEmpty() || stack.pop() !== pairs[char]) {
        return false; // 不匹配或栈已空
      }
    }
  }

  // 栈空说明全部匹配
  return stack.isEmpty();
}

// 测试
console.log(isValidParentheses('({[]})')); // true
console.log(isValidParentheses('({[})'));  // false
console.log(isValidParentheses('((()))')); // true

算法逻辑很简单：左括号入栈，右括号与栈顶比较。如果最终栈为空，说明所有括号都完美匹配。

队列（Queue）：先进先出

核心概念

队列遵循 **FIFO（First In, First Out）**原则，即最先进入的元素最先被取出。生活中的排队买票就是典型的队列场景。

队列的三个核心操作：

操作作用时间复杂度
enqueue向队尾添加元素O(1)
dequeue移除并返回队首元素O(1)
front查看队首元素（不移除）O(1)

手写 Queue 类

js
class Queue {
  constructor() {
    this.items = [];
  }

  // 入队：向队尾添加元素
  enqueue(element) {
    this.items.push(element);
  }

  // 出队：移除并返回队首元素
  dequeue() {
    return this.items.shift();
  }

  // 查看队首元素
  front() {
    return this.items[0];
  }

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

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

  // 清空队列
  clear() {
    this.items = [];
  }
}

需要注意的是，shift() 操作在数组头部移除元素时，其余元素都需要向前移动一位。对于大数据量场景，这会导致 O(n) 的时间复杂度。生产环境中可使用对象+指针的方式实现均摊 O(1) 的队列。

高性能队列实现（对象+指针）

js
class FastQueue {
  constructor() {
    this.items = {};
    this.head = 0; // 队首指针
    this.tail = 0; // 队尾指针
  }

  enqueue(element) {
    this.items[this.tail] = element;
    this.tail++;
  }

  dequeue() {
    if (this.isEmpty()) return undefined;
    const element = this.items[this.head];
    delete this.items[this.head];
    this.head++;
    return element;
  }

  front() {
    return this.items[this.head];
  }

  isEmpty() {
    return this.tail - this.head === 0;
  }

  size() {
    return this.tail - this.head;
  }

  clear() {
    this.items = {};
    this.head = 0;
    this.tail = 0;
  }
}

这种实现方式中，enqueue 和 dequeue 都是纯粹的 O(1) 操作，无需移动任何元素。

实战：任务调度器

在 JavaScript 的异步编程中，事件循环的回调队列本质上就是一个队列。下面模拟一个简易的任务调度器：

js
class TaskScheduler {
  constructor() {
    this.queue = new FastQueue();
    this.running = false;
  }

  // 添加任务到队列
  addTask(taskFn, delay = 0) {
    this.queue.enqueue({ taskFn, delay });
    if (!this.running) {
      this.run();
    }
  }

  // 按顺序执行任务
  async run() {
    this.running = true;

    while (!this.queue.isEmpty()) {
      const { taskFn, delay } = this.queue.dequeue();
      await new Promise((resolve) => setTimeout(resolve, delay));
      await taskFn();
    }

    this.running = false;
  }
}

// 使用示例
const scheduler = new TaskScheduler();

scheduler.addTask(() => console.log('任务 1：发送请求'), 100);
scheduler.addTask(() => console.log('任务 2：处理响应'), 200);
scheduler.addTask(() => console.log('任务 3：更新 UI'), 50);

这个调度器保证了任务按照添加顺序依次执行，且可以设置每个任务之间的延迟间隔。

双端队列（Deque）：两端都能操作

**双端队列（Double-Ended Queue）**是一种允许在队列两端同时进行插入和删除操作的数据结构。它融合了栈和队列的特性，既可以当作栈使用（只操作一端），也可以当作队列使用。

js
class Deque {
  constructor() {
    this.items = {};
    this.head = 0;
    this.tail = 0;
  }

  // 从前端入队
  addFront(element) {
    this.head--;
    this.items[this.head] = element;
  }

  // 从后端入队
  addBack(element) {
    this.items[this.tail] = element;
    this.tail++;
  }

  // 从前端出队
  removeFront() {
    if (this.isEmpty()) return undefined;
    const element = this.items[this.head];
    delete this.items[this.head];
    this.head++;
    return element;
  }

  // 从后端出队
  removeBack() {
    if (this.isEmpty()) return undefined;
    this.tail--;
    const element = this.items[this.tail];
    delete this.items[this.tail];
    return element;
  }

  peekFront() {
    return this.items[this.head];
  }

  peekBack() {
    return this.items[this.tail - 1];
  }

  isEmpty() {
    return this.tail - this.head === 0;
  }

  size() {
    return this.tail - this.head;
  }

  clear() {
    this.items = {};
    this.head = 0;
    this.tail = 0;
  }
}

应用：回文检查

回文是指正读反读都相同的字符串。利用双端队列可以优雅地解决这个问题：

js
function isPalindrome(str) {
  const deque = new Deque();
  const cleaned = str.toLowerCase().replace(/[^a-z0-9]/g, '');

  // 将所有字符从后端入队
  for (const char of cleaned) {
    deque.addBack(char);
  }

  // 两端同时出队比较
  while (deque.size() > 1) {
    if (deque.removeFront() !== deque.removeBack()) {
      return false;
    }
  }

  return true;
}

console.log(isPalindrome('A man, a plan, a canal: Panama')); // true
console.log(isPalindrome('race a car'));                      // false
console.log(isPalindrome('level'));                           // true

优先级队列（Priority Queue）：带权重的队列

普通队列遵循严格的 FIFO 原则，但现实中很多场景需要考虑优先级。例如：医院急诊分诊、操作系统进程调度、网络请求优先级控制。

优先级队列的核心特点是：出队时总是返回优先级最高（或最低）的元素，而不是最早入队的元素。

js
class PriorityQueue {
  constructor(comparator = (a, b) => a.priority - b.priority) {
    this.items = [];
    this.comparator = comparator; // 默认最小堆：priority 越小越优先
  }

  // 入队：保持数组按优先级有序
  enqueue(element, priority) {
    const item = { element, priority };

    // 找到插入位置，保持升序
    let inserted = false;
    for (let i = 0; i < this.items.length; i++) {
      if (this.comparator(item, this.items[i]) < 0) {
        this.items.splice(i, 0, item);
        inserted = true;
        break;
      }
    }

    // 优先级最低，放到末尾
    if (!inserted) {
      this.items.push(item);
    }
  }

  // 出队：返回优先级最高的元素
  dequeue() {
    if (this.isEmpty()) return undefined;
    return this.items.shift().element;
  }

  // 查看优先级最高的元素
  front() {
    return this.items[0]?.element;
  }

  isEmpty() {
    return this.items.length === 0;
  }

  size() {
    return this.items.length;
  }
}

上述实现基于有序数组，入队最坏时间复杂度为 O(n)。如果数据量很大，应该使用**二叉堆（Binary Heap）**实现，将入队和出队都优化到 O(log n)。

实战：医院急诊分诊

js
const emergencyQueue = new PriorityQueue();

// 数字越小优先级越高（1 = 危重，5 = 轻微）
emergencyQueue.enqueue('心脏病发作患者', 1);
emergencyQueue.enqueue('骨折患者', 3);
emergencyQueue.enqueue('感冒发烧患者', 5);
emergencyQueue.enqueue('大出血患者', 1);
emergencyQueue.enqueue('轻微擦伤患者', 4);

// 按优先级依次处理
while (!emergencyQueue.isEmpty()) {
  console.log(`正在处理：${emergencyQueue.dequeue()}`);
}
// 输出顺序：心脏病发作患者 → 大出血患者 → 骨折患者 → 轻微擦伤患者 → 感冒发烧患者

总结

数据结构核心规则典型操作应用场景
栈（Stack）LIFOpush / pop / peek函数调用栈、括号匹配、撤销操作、DFS
队列（Queue）FIFOenqueue / dequeue / front任务调度、BFS、消息队列、事件循环
双端队列（Deque）两端均可操作add/remove Front/Back滑动窗口、回文检查、单调队列
优先级队列按权重出队enqueue / dequeue进程调度、Dijkstra 算法、哈夫曼编码

栈和队列的实现虽然简单，但它们是构建更复杂算法的基础。理解这些结构的手写实现，能帮助你在面试和实际开发中灵活运用，而不是仅仅停留在”知道 API”的层面。

#javascript #data-structure #algorithm #stack #queue

评论

A

Written by

AI-Writer

Related Articles

javascript
#6

类与继承机制

全面解析 ES6 class 语法糖、构造函数、静态方法、私有字段与继承机制，理解 class 背后的原型链本质。

Read More
Back to All Articles