实现一个队列

问题

队列（Queue）是一种先进先出（FIFO, First In First Out）的数据结构。需要实现一个队列类，支持以下操作：

• enqueue(element): 向队列尾部添加元素
• dequeue(): 移除并返回队列头部元素
• front(): 查看队列头部元素但不移除
• isEmpty(): 判断队列是否为空
• size(): 返回队列中元素的个数
• clear(): 清空队列

解答

class Queue {
  constructor() {
    this.items = []; // 使用数组存储队列元素
  }

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

  // 移除并返回队列头部元素
  dequeue() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items.shift();
  }

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

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

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

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

  // 打印队列（用于调试）
  toString() {
    return this.items.toString();
  }
}

优化版本（使用对象实现，性能更好）

class Queue {
  constructor() {
    this.items = {}; // 使用对象存储
    this.headIndex = 0; // 队首指针
    this.tailIndex = 0; // 队尾指针
  }

  // 向队列尾部添加元素
  enqueue(element) {
    this.items[this.tailIndex] = element;
    this.tailIndex++;
  }

  // 移除并返回队列头部元素
  dequeue() {
    if (this.isEmpty()) {
      return undefined;
    }
    const element = this.items[this.headIndex];
    delete this.items[this.headIndex];
    this.headIndex++;
    return element;
  }

  // 查看队列头部元素
  front() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.headIndex];
  }

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

  // 返回队列大小
  size() {
    return this.tailIndex - this.headIndex;
  }

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

  // 打印队列
  toString() {
    if (this.isEmpty()) {
      return '';
    }
    let str = `${this.items[this.headIndex]}`;
    for (let i = this.headIndex + 1; i < this.tailIndex; i++) {
      str += `,${this.items[i]}`;
    }
    return str;
  }
}

使用示例

// 创建队列实例
const queue = new Queue();

// 入队操作
queue.enqueue('张三');
queue.enqueue('李四');
queue.enqueue('王五');

console.log(queue.toString()); // 输出: 张三,李四,王五
console.log(queue.size()); // 输出: 3

// 查看队首元素
console.log(queue.front()); // 输出: 张三

// 出队操作
console.log(queue.dequeue()); // 输出: 张三
console.log(queue.dequeue()); // 输出: 李四

console.log(queue.size()); // 输出: 1
console.log(queue.isEmpty()); // 输出: false

// 继续操作
queue.enqueue('赵六');
console.log(queue.toString()); // 输出: 王五,赵六

// 清空队列
queue.clear();
console.log(queue.isEmpty()); // 输出: true

关键点

• 数据结构选择：可以使用数组或对象实现。数组实现简单直观，但 shift() 操作的时间复杂度为 O(n)；对象实现使用双指针，所有操作时间复杂度均为 O(1)，性能更优

• 双指针技巧：在对象实现中，使用 headIndex 和 tailIndex 两个指针分别指向队首和队尾，避免了数组的元素移动开销

• 边界处理：在 dequeue() 和 front() 方法中需要判断队列是否为空，避免访问不存在的元素

• 空间管理：对象实现中使用 delete 删除已出队的元素，防止内存泄漏

• FIFO 原则：严格遵循先进先出原则，入队在尾部，出队在头部

• 封装性：将内部数据结构和指针封装在类内部，对外只暴露必要的操作接口