Xiaoming.wiki 小明维基
数据结构队列算法

【数据结构入门】队列：公平的排队专家

队列是最重要的数据结构之一，遵循"先来先服务"原则。本文教你理解队列的原理和应用场景。

9 分钟阅读
小明

从排队买奶茶说起

周末，你去买奶茶。店里生意很好，已经排了 10 个人。

你是第 11 个。

然后你发现，店员总是先做排在前面的人的奶茶，做完一杯，前面的人拿走，后面的人往前移。

没有人插队，先来的先走。

这就是**队列（Queue）**的精髓：先进先出（FIFO，First In First Out）。

队列的基本概念

核心特性

队列只有两个主要操作：

  1. 入队（Enqueue）：从队尾加入元素
  2. 出队（Dequeue）：从队首移除元素
入队 →  [A] [B] [C] [D]  → 出队
        队尾        队首

就像排队一样：

  • 新来的人排在队尾
  • 办完事的人从队首离开

与栈的对比

特性栈队列
原则后进先出 (LIFO)先进先出 (FIFO)
比喻叠盘子排队
添加在顶部 (push)在尾部 (enqueue)
移除从顶部 (pop)从头部 (dequeue)

JavaScript 实现队列

方法一：数组实现（简单但有问题）

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

  // 入队：加到数组末尾
  enqueue(element) {
    this.items.push(element);
  }

  // 出队：从数组开头移除
  dequeue() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items.shift();
  }

  // 查看队首元素
  peek() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[0];
  }

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

  // 队列大小
  size() {
    return this.items.length;
  }

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

测试一下：

const queue = new SimpleQueue();

queue.enqueue('小明');
queue.enqueue('小红');
queue.enqueue('小刚');

console.log(queue.peek());    // 小明
console.log(queue.dequeue()); // 小明
console.log(queue.dequeue()); // 小红
console.log(queue.size());    // 1

问题在哪？

shift() 的时间复杂度是 O(n)！因为移除第一个元素后，后面所有元素都要往前移动一位。

如果队列很大，这会很慢。

方法二：对象实现（高效版）

class Queue {
  constructor() {
    this.items = {};
    this.headIndex = 0;  // 队首索引
    this.tailIndex = 0;  // 队尾索引
  }

  // 入队：O(1)
  enqueue(element) {
    this.items[this.tailIndex] = element;
    this.tailIndex++;
  }

  // 出队：O(1)
  dequeue() {
    if (this.isEmpty()) {
      return undefined;
    }
    const item = this.items[this.headIndex];
    delete this.items[this.headIndex];
    this.headIndex++;
    return item;
  }

  // 查看队首：O(1)
  peek() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.headIndex];
  }

  // 检查是否为空：O(1)
  isEmpty() {
    return this.tailIndex === this.headIndex;
  }

  // 队列大小：O(1)
  size() {
    return this.tailIndex - this.headIndex;
  }

  // 清空队列
  clear() {
    this.items = {};
    this.headIndex = 0;
    this.tailIndex = 0;
  }

  // 转换为字符串（调试用）
  toString() {
    if (this.isEmpty()) {
      return '';
    }
    const result = [];
    for (let i = this.headIndex; i < this.tailIndex; i++) {
      result.push(this.items[i]);
    }
    return result.join(', ');
  }
}

为什么这个更高效？

用对象存储，通过索引直接访问，入队和出队都是 O(1)。

虽然索引会不断增加，但在实际应用中，这通常不是问题（可以在适当时候重置索引）。

队列的变种

双端队列（Deque）

普通队列只能从一端进、另一端出。双端队列允许从两端进出。

class Deque {
  constructor() {
    this.items = {};
    this.headIndex = 0;
    this.tailIndex = 0;
  }

  // 从前端添加
  addFront(element) {
    this.headIndex--;
    this.items[this.headIndex] = element;
  }

  // 从后端添加
  addBack(element) {
    this.items[this.tailIndex] = element;
    this.tailIndex++;
  }

  // 从前端移除
  removeFront() {
    if (this.isEmpty()) return undefined;
    const item = this.items[this.headIndex];
    delete this.items[this.headIndex];
    this.headIndex++;
    return item;
  }

  // 从后端移除
  removeBack() {
    if (this.isEmpty()) return undefined;
    this.tailIndex--;
    const item = this.items[this.tailIndex];
    delete this.items[this.tailIndex];
    return item;
  }

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

  // 查看后端
  peekBack() {
    if (this.isEmpty()) return undefined;
    return this.items[this.tailIndex - 1];
  }

  isEmpty() {
    return this.tailIndex === this.headIndex;
  }

  size() {
    return this.tailIndex - this.headIndex;
  }
}

应用场景：需要从两端操作的场景，比如实现"撤销/重做"功能。

优先队列（Priority Queue）

普通队列"先来先服务"，优先队列是"重要的先服务"。

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

  // 入队（按优先级插入）
  // priority 越小，优先级越高
  enqueue(element, priority) {
    const queueElement = { element, priority };
    
    if (this.isEmpty()) {
      this.items.push(queueElement);
    } else {
      let added = false;
      for (let i = 0; i < this.items.length; i++) {
        if (queueElement.priority < this.items[i].priority) {
          this.items.splice(i, 0, queueElement);
          added = true;
          break;
        }
      }
      if (!added) {
        this.items.push(queueElement);
      }
    }
  }

  // 出队
  dequeue() {
    if (this.isEmpty()) return undefined;
    return this.items.shift().element;
  }

  peek() {
    if (this.isEmpty()) return undefined;
    return this.items[0].element;
  }

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

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

使用示例：

const pq = new PriorityQueue();

// 医院急诊排队
pq.enqueue('感冒发烧', 3);
pq.enqueue('心脏病发作', 1);  // 优先级最高
pq.enqueue('骨折', 2);

console.log(pq.dequeue()); // 心脏病发作（先处理）
console.log(pq.dequeue()); // 骨折
console.log(pq.dequeue()); // 感冒发烧

注意：这个实现的时间复杂度是 O(n)，更高效的实现需要用堆。

循环队列（Circular Queue）

普通队列的索引会不断增加，循环队列让索引"循环"使用，适合固定大小的场景。

class CircularQueue {
  constructor(capacity) {
    this.items = new Array(capacity);
    this.capacity = capacity;
    this.head = 0;
    this.tail = 0;
    this.count = 0;
  }

  enqueue(element) {
    if (this.isFull()) {
      return false;
    }
    this.items[this.tail] = element;
    this.tail = (this.tail + 1) % this.capacity;  // 循环
    this.count++;
    return true;
  }

  dequeue() {
    if (this.isEmpty()) {
      return undefined;
    }
    const item = this.items[this.head];
    this.head = (this.head + 1) % this.capacity;  // 循环
    this.count--;
    return item;
  }

  peek() {
    if (this.isEmpty()) return undefined;
    return this.items[this.head];
  }

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

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

  size() {
    return this.count;
  }
}

应用场景：缓冲区、滑动窗口等固定大小的场景。

队列的应用场景

1. 任务调度

操作系统用队列管理进程：

class TaskScheduler {
  constructor() {
    this.taskQueue = new Queue();
  }

  addTask(task) {
    console.log(`任务 "${task.name}" 加入队列`);
    this.taskQueue.enqueue(task);
  }

  run() {
    console.log('开始执行任务...');
    while (!this.taskQueue.isEmpty()) {
      const task = this.taskQueue.dequeue();
      console.log(`执行: ${task.name}`);
      task.execute();
    }
    console.log('所有任务完成');
  }
}

// 使用
const scheduler = new TaskScheduler();
scheduler.addTask({ name: '编译代码', execute: () => console.log('编译中...') });
scheduler.addTask({ name: '运行测试', execute: () => console.log('测试中...') });
scheduler.addTask({ name: '部署上线', execute: () => console.log('部署中...') });
scheduler.run();

2. 广度优先搜索（BFS）

队列是 BFS 的核心：

function bfs(graph, start) {
  const visited = new Set();
  const queue = new Queue();
  
  queue.enqueue(start);
  visited.add(start);
  
  while (!queue.isEmpty()) {
    const vertex = queue.dequeue();
    console.log('访问节点:', vertex);
    
    // 将未访问的邻居加入队列
    for (const neighbor of graph[vertex]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.enqueue(neighbor);
      }
    }
  }
}

// 图的邻接表表示
const graph = {
  'A': ['B', 'C'],
  'B': ['A', 'D', 'E'],
  'C': ['A', 'F'],
  'D': ['B'],
  'E': ['B', 'F'],
  'F': ['C', 'E']
};

bfs(graph, 'A');  // A → B → C → D → E → F

3. 消息队列

异步处理消息：

class MessageQueue {
  constructor() {
    this.queue = new Queue();
    this.processing = false;
  }

  // 发送消息
  send(message) {
    this.queue.enqueue({
      id: Date.now(),
      content: message,
      timestamp: new Date()
    });
    this.process();
  }

  // 处理消息
  async process() {
    if (this.processing) return;
    this.processing = true;
    
    while (!this.queue.isEmpty()) {
      const message = this.queue.dequeue();
      console.log(`处理消息: ${message.content}`);
      await this.handleMessage(message);
    }
    
    this.processing = false;
  }

  async handleMessage(message) {
    // 模拟异步处理
    return new Promise(resolve => setTimeout(resolve, 100));
  }
}

4. 请求限流

控制并发请求数量：

class RequestQueue {
  constructor(maxConcurrent = 3) {
    this.queue = [];
    this.running = 0;
    this.maxConcurrent = maxConcurrent;
  }

  async add(requestFn) {
    return new Promise((resolve, reject) => {
      this.queue.push({ requestFn, resolve, reject });
      this.run();
    });
  }

  async run() {
    while (this.running < this.maxConcurrent && this.queue.length > 0) {
      const { requestFn, resolve, reject } = this.queue.shift();
      this.running++;
      
      try {
        const result = await requestFn();
        resolve(result);
      } catch (error) {
        reject(error);
      } finally {
        this.running--;
        this.run();  // 继续处理队列
      }
    }
  }
}

// 使用
const limiter = new RequestQueue(3);

for (let i = 1; i <= 10; i++) {
  limiter.add(() => fetch(`/api/data/${i}`))
    .then(res => console.log(`请求 ${i} 完成`));
}
// 同时最多只有 3 个请求在进行

经典问题：击鼓传花

用队列模拟击鼓传花游戏：

function hotPotato(players, num) {
  const queue = new Queue();
  
  // 所有玩家入队
  for (const player of players) {
    queue.enqueue(player);
  }
  
  // 游戏开始
  while (queue.size() > 1) {
    // 传递 num 次
    for (let i = 0; i < num; i++) {
      // 队首的人传给队尾
      queue.enqueue(queue.dequeue());
    }
    // 淘汰当前拿到花的人
    const eliminated = queue.dequeue();
    console.log(`${eliminated} 被淘汰`);
  }
  
  return queue.dequeue();  // 返回获胜者
}

const players = ['小明', '小红', '小刚', '小芳', '小李'];
const winner = hotPotato(players, 7);
console.log(`获胜者: ${winner}`);

经典问题：判断回文

用双端队列判断字符串是否是回文：

function isPalindrome(str) {
  const deque = new Deque();
  
  // 预处理：去除空格，转小写
  const cleanStr = str.toLowerCase().replace(/\s/g, '');
  
  // 所有字符入队
  for (const char of cleanStr) {
    deque.addBack(char);
  }
  
  // 从两端比较
  while (deque.size() > 1) {
    const front = deque.removeFront();
    const back = deque.removeBack();
    if (front !== back) {
      return false;
    }
  }
  
  return true;
}

console.log(isPalindrome('level'));         // true
console.log(isPalindrome('hello'));         // false
console.log(isPalindrome('A man a plan a canal Panama')); // true

总结

队列的核心特点：

特性说明
原则先进先出 (FIFO)
入队O(1)
出队O(1)（使用对象实现）
查看队首O(1)

记住这句话：需要"公平排队"的场景，就用队列。

  • 任务调度 → 队列
  • BFS 遍历 → 队列
  • 消息队列 → 队列
  • 打印任务 → 队列

下一篇，我们来聊 JavaScript 中最神奇的概念——闭包。

相关标签

# 数据结构 # 队列 # 算法
返回专题列表