链表在队列实现中的应用：队列的链表实现与数组实现的场景选择与性能对比

一、队列的本质与两种实现的核心差异

队列这个东西，说穿了就是“先到先服务”的排队队伍。比如你去餐厅取号，先来的先叫号，这就是队列的核心逻辑——只允许从队尾加人，从队头走人，中间不能插也不能插队。现在要把这个逻辑用代码写出来，有两种最常用的办法：用数组存、用链表存。这俩的核心差异，本质上是“存数据的容器结构”不一样，导致后续的操作逻辑、性能表现天差地别。

先给大家补个最基础的前置知识：数组和链表的区别，用生活化的话讲，数组就是“连在一起的一排座位”，每个座位的位置是固定的，比如第一个座位在1号，第二个就在2号，能直接通过编号找位置；链表就是“一串连起来的人”，第一个人手里拿着第二个人的位置，第二个人拿着第三个人的，想找某个人，得从第一个人开始一个一个问。

1.1 两种实现的基础逻辑

我们先统一用JavaScript这个技术栈来写示例，所有示例都用这个语言，大家不用换脑子。

数组实现队列的基础逻辑

数组实现队列，就是把排队的人按顺序存在这个“连在一起的座位”里。比如队头是第一个座位，队尾是最后一个有人的座位。要加人就往队尾的下一个座位塞，要走人就把队头的座位清空。但这里有个问题：如果队头的人走了，空出来的座位就浪费了，后面的人都得往前挪，不然下一个来的人不知道往哪放。

举个完整的JavaScript示例：

// 技术栈：JavaScript
// 数组实现队列的基础版本（未优化的朴素版本）
class ArrayQueue {
  constructor() {
    // 用数组存队列元素，初始为空
    this.items = [];
  }

  // 入队：往队尾加元素
  enqueue(element) {
    // 数组的push方法就是往最后加元素，对应队尾加人
    this.items.push(element);
  }

  // 出队：从队头拿元素
  dequeue() {
    // 数组的shift方法就是拿第一个元素，同时把后面所有元素往前挪一位
    if (this.isEmpty()) {
      return null; // 空队列不能出队
    }
    return this.items.shift();
  }

  // 查看队头元素
  front() {
    if (this.isEmpty()) {
      return null;
    }
    return this.items[0];
  }

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

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

// 测试用例
const aq = new ArrayQueue();
aq.enqueue('张三');
aq.enqueue('李四');
console.log(aq.dequeue()); // 输出'张三'，此时数组变成['李四']，后面的元素往前挪了一位
console.log(aq.front()); // 输出'李四'

链表实现队列的基础逻辑

链表实现队列，就是把排队的人按“前一个指向后一个”的方式连起来，不用管位置是不是连在一起。队头是第一个人，队尾是最后一个人，想加人就把最后一个人的“下一个”指向新的人，想走人就把队头换成原来队头的“下一个”，中间不用动其他元素。

同样是JavaScript的示例：

// 技术栈：JavaScript
// 链表实现队列的基础版本
class Node {
  // 链表的每个节点，存两个东西：自己的值、下一个节点的指针
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkedQueue {
  constructor() {
    // 队头节点，初始为空
    this.head = null;
    // 队尾节点，初始为空
    this.tail = null;
    // 队列长度，方便快速获取
    this.length = 0;
  }

  // 入队：往队尾加元素
  enqueue(element) {
    const newNode = new Node(element);
    if (this.isEmpty()) {
      // 空队列时，新节点既是队头也是队尾
      this.head = newNode;
      this.tail = newNode;
    } else {
      // 非空队列，把原队尾的next指向新节点，更新队尾为新节点
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
  }

  // 出队：从队头拿元素
  dequeue() {
    if (this.isEmpty()) {
      return null;
    }
    // 拿到原队头的值
    const value = this.head.value;
    // 更新队头为原队头的下一个节点
    this.head = this.head.next;
    this.length--;
    // 如果出队后队列空了，把队尾也设为空，避免内存泄漏
    if (this.isEmpty()) {
      this.tail = null;
    }
    return value;
  }

  // 查看队头元素
  front() {
    if (this.isEmpty()) {
      return null;
    }
    return this.head.value;
  }

  // 判断队列是否为空
  isEmpty() {
    return this.length === 0;
  }

  // 查看队列长度
  size() {
    return this.length;
  }
}

// 测试用例
const lq = new LinkedQueue();
lq.enqueue('张三');
lq.enqueue('李四');
console.log(lq.dequeue()); // 输出'张三'，此时队头变成'李四'的节点，其他节点不用动
console.log(lq.front()); // 输出'李四'

二、两种实现的性能对比

性能对比说白了就是“加人、走人、看队头”这三个核心操作的速度，还有会不会浪费空间。我们还是用生活化的例子来解释，不用讲大O符号的专业术语，大家都能懂。

2.1 核心操作的速度对比

加人（入队）的速度

数组实现的入队：如果是朴素版本（就是我们上面写的那个），加人是很快的，因为直接往数组最后塞就行。但如果是优化过的数组队列（比如循环队列，后面会讲），也一样快。 链表实现的入队：也很快，因为只要把队尾的下一个指向新节点就行，不用动其他元素。

走人（出队）的速度

数组实现的出队：朴素版本的出队特别慢！比如队列里有1000个人，队头的张三走了，后面的999个人都得往前挪一个位置，相当于所有人都要动一遍。人数越多，挪的时间越长。 链表实现的出队：特别快！不管队列里有多少人，只要把队头换成原来队头的下一个就行，其他所有人都不用动。比如1000个人的队列，张三走了，只有队头的指针变了，其他999个人都不用挪。

看队头的速度

两种实现都一样快，数组直接拿第一个元素，链表直接拿队头节点的值，都是一步到位。

2.2 空间利用的对比

数组实现的队列：有两种情况，一种是朴素版本，出队后前面的空位置不会浪费，因为出队的时候会把后面的元素往前挪；另一种是优化过的循环队列，会重复利用空位置，但如果队列的最大长度是固定的，当队列满了之后就不能再加人了，必须扩容（扩容的时候要把所有元素复制到新的更大的数组里，也会花时间）。 链表实现的队列：没有最大长度的限制，只要内存够就能一直加人，而且不会有空间浪费，每个节点只存自己的值和下一个节点的指针，没有空位置。

2.3 实际测试的性能差异

我们可以写个简单的测试代码，对比两种实现出队100万次的时间：

// 技术栈：JavaScript
// 性能测试：两种队列出队100万次的时间对比
const testSize = 1000000; // 测试次数：100万次

// 测试数组队列
const aq = new ArrayQueue();
for (let i = 0; i < testSize; i++) {
  aq.enqueue(i);
}
console.time('数组队列出队时间');
for (let i = 0; i < testSize; i++) {
  aq.dequeue();
}
console.timeEnd('数组队列出队时间');

// 测试链表队列
const lq = new LinkedQueue();
for (let i = 0; i < testSize; i++) {
  lq.enqueue(i);
}
console.time('链表队列出队时间');
for (let i = 0; i < testSize; i++) {
  lq.dequeue();
}
console.timeEnd('链表队列出队时间');

大家自己跑这个代码的话，会发现数组队列的出队时间特别长，可能要几秒甚至十几秒，而链表队列的出队时间几乎可以忽略，只要几毫秒。这就是两种实现的性能差异，在数据量小的时候可能不明显，数据量大了之后差距会特别大。

三、两种实现的场景选择

知道了性能差异，接下来就是什么时候用数组队列，什么时候用链表队列。我们还是用生活化的场景来举例子。

3.1 适合用数组实现队列的场景

数组实现的队列适合“队列长度固定、出队次数少”的场景。比如你去银行办业务，窗口有3个，排队的人最多也就10个，而且出队的次数很少（大部分人都是按顺序办业务）。这时候用数组队列就很合适，因为数组的内存是连续的，访问速度快，而且队列长度固定，不会有扩容的问题。

再比如操作系统里的进程调度队列，每个CPU核的调度队列长度是固定的，出队次数也不多，这时候用数组队列就很合适。

还有一个优化过的数组队列——循环队列，适合“队列长度固定、需要重复利用空间”的场景。比如你家里的鞋柜，最多放10双鞋，满了之后要把旧的鞋拿出来，再放新的鞋。这时候用循环队列就很合适，因为可以重复利用空位置，不用每次都挪元素。

循环队列的JavaScript示例：

// 技术栈：JavaScript
// 优化后的数组队列：循环队列（适合固定长度的场景）
class CircularQueue {
  constructor(maxSize) {
    this.maxSize = maxSize; // 队列的最大长度
    this.items = new Array(maxSize); // 用数组存元素，长度固定
    this.frontIndex = 0; // 队头的索引
    this.tailIndex = 0; // 队尾的索引
    this.count = 0; // 队列里的元素个数
  }

  // 入队
  enqueue(element) {
    if (this.isFull()) {
      return false; // 队列满了不能入队
    }
    this.items[this.tailIndex] = element;
    // 队尾索引加1，如果到了最大长度就回到0（循环）
    this.tailIndex = (this.tailIndex + 1) % this.maxSize;
    this.count++;
    return true;
  }

  // 出队
  dequeue() {
    if (this.isEmpty()) {
      return null;
    }
    const value = this.items[this.frontIndex];
    // 队头索引加1，如果到了最大长度就回到0（循环）
    this.frontIndex = (this.frontIndex + 1) % this.maxSize;
    this.count--;
    return value;
  }

  // 判断队列是否为空
  isEmpty() {
    return this.count === 0;
  }

  // 判断队列是否满了
  isFull() {
    return this.count === this.maxSize;
  }

  // 查看队头元素
  front() {
    if (this.isEmpty()) {
      return null;
    }
    return this.items[this.frontIndex];
  }

  // 查看队列长度
  size() {
    return this.count;
  }
}

// 测试用例
const cq = new CircularQueue(3); // 最大长度3
cq.enqueue('张三');
cq.enqueue('李四');
cq.enqueue('王五');
console.log(cq.isFull()); // 输出true
console.log(cq.dequeue()); // 输出'张三'
console.log(cq.enqueue('赵六')); // 输出true（空出的位置被利用）
console.log(cq.items); // 输出['张三', '李四', '赵六']，队头索引现在是1，队尾索引是0

3.2 适合用链表实现队列的场景

链表实现的队列适合“队列长度不固定、出队次数多”的场景。比如你在微信群里抢红包，发红包的人先抢，抢完的人再让下一个人抢，这时候队列的长度是不固定的（可能有10个人抢，也可能有100个人抢），而且出队次数很多（每个人抢完就出队）。这时候用链表队列就很合适，因为出队快，而且没有最大长度的限制。

再比如消息队列（比如Kafka、RabbitMQ），生产者往队列里发消息，消费者从队列里拿消息，队列的长度是不固定的（可能有1000条消息，也可能有100万条消息），而且出队次数很多（消费者拿消息的速度很快）。这时候用链表队列就很合适，因为出队快，而且不会有扩容的问题。

还有一个场景是“队列需要动态扩容”，比如你做一个在线聊天系统，用户发的消息存在队列里，队列的长度是不固定的（可能有10条消息，也可能有1000条消息），这时候用链表队列就很合适，因为不用扩容，只要内存够就能一直加人。

四、两种实现的优缺点与注意事项

4.1 数组实现队列的优缺点

优点：

1. 内存连续，访问速度快：数组的元素是连续存的，访问的时候直接通过索引就能找到，速度比链表快。
2. 节省内存：数组的每个元素只存自己的值，没有额外的指针，所以比链表节省内存。
3. 适合固定长度的场景：循环队列可以重复利用空间，不会有空间浪费。

缺点：

1. 朴素版本出队慢：出队的时候要把后面的元素往前挪，数据量越大，速度越慢。
2. 动态扩容麻烦：如果队列的长度超过了数组的最大长度，就要扩容，扩容的时候要把所有元素复制到新的数组里，会花时间。
3. 容易出现内存泄漏：如果队列的长度固定，满了之后就不能再加人了，容易导致新的元素丢失。

注意事项：

1. 尽量用循环队列代替朴素版本的数组队列：循环队列的出队速度比朴素版本快很多，而且可以重复利用空间。
2. 合理设置数组的最大长度：如果数组的最大长度设置得太小，容易导致队列满；如果设置得太大，会浪费内存。
3. 注意扩容的时机：如果需要动态扩容，尽量在队列的长度达到数组最大长度的80%的时候扩容，避免频繁扩容。

4.2 链表实现队列的优缺点

优点：

1. 出队速度快：出队的时候只要把队头的指针换成下一个节点的指针就行，不用动其他元素，数据量越大，速度越快。
2. 没有最大长度的限制：只要内存够就能一直加人，不会有队列满的问题。
3. 不需要扩容：链表的节点是动态分配的，不用提前分配内存，也不用扩容。

缺点：

1. 内存不连续，访问速度慢：链表的元素是分散存的，访问的时候要从队头开始一个一个找，速度比数组慢。
2. 占用内存多：链表的每个节点除了存自己的值，还要存下一个节点的指针，所以比数组占用的内存多。
3. 容易出现内存泄漏：如果节点没有被正确释放，会导致内存泄漏。

注意事项：

1. 注意节点的内存管理：如果是在垃圾回收机制不自动管理的语言（比如C++），要手动释放不用的节点，避免内存泄漏。
2. 合理设置链表的最大长度：如果链表的长度太长，会占用太多内存，影响系统的性能。
3. 尽量用尾指针优化入队速度：如果没有尾指针，入队的时候要从队头开始找队尾，速度会很慢，所以一定要有尾指针。

五、文章总结

队列的链表实现和数组实现，本质上是两种不同的容器结构的选择，各有优缺点，没有绝对的好坏，只有适合不适合的场景。

总结一下：

• 如果队列的长度固定、出队次数少，适合用数组实现的队列（尤其是循环队列），速度快、省内存。
• 如果队列的长度不固定、出队次数多，适合用链表实现的队列，出队快、没有扩容问题。

大家在实际开发的时候，要根据自己的场景选择合适的实现方式，不要盲目追求性能，也不要盲目追求省内存。比如你做一个简单的排队系统，队列长度最多10个，出队次数也不多，用数组队列就很合适；如果你做一个消息队列，队列长度不固定，出队次数很多，用链表队列就很合适。

最后再提醒大家一句，性能优化不是万能的，要先保证代码的正确性和可读性，再去考虑性能优化。如果你的代码逻辑都错了，性能再好也没用。