🤺
Never Too Late/
🧩
链表和数组实现队列哪个更快
Search
链表和数组实现队列哪个更快
🧩

链表和数组实现队列哪个更快

Property
FrontEnd
Year
2022
Author
Tweet
队列(queue)，一种数据结构，是一个先进先出的线性表。在队尾入队，在队头出队。
由于 JavaScript 中没有队列，所以需要使用链表和数组来模拟。虽然这两个都可以实现队列，但是性能是不一样的。下面用代码来实现比较一下。

使用链表实现队列

interface IListNode {
  value: number;
  next: IListNode | null;
}
export class MyQueue {
  private head: IListNode | null = null;

  private tail: IListNode | null = null;

  private len: number = 0;

  // 入队
  add(n: number) {
    const newNode: IListNode = {
      value: n,
      next: null,
    };
    // 处理 head
    if (this.head === null) {
      this.head = newNode;
    }
    // 处理 tail
    const tailNode = this.tail;
    if (tailNode) {
      tailNode.next = newNode;
    }

    // 记录长度
    this.len++;
  }

  // 出队
  delete(): number | null {
    const headNode = this.head;
    if (headNode === null) return null;
    if (this.len === 0) return null;

    const value = headNode.value;

    this.head = headNode.next;
    // 记录长度
    this.len--;

    return value;
  }

  // 获取长度
  get length(): number {
    return this.len;
  }
}
在实现队列时，需要注意的是，不可遍历获取链表长度，否则时间复杂度就是。
✍️
使用数组实现队列的时候，有两种方式，1. 使用数组的API直进行入队和出队的操作；2. 使用两个栈实现一个队列

使用数组的API

  • 入队使用 push 方法
  • 出队使用 shift 方法
由于数组是连续内存，shift，unshift，splice这些API都会导致数组的所有元素都被处理一遍，时间复杂度都是。比较耗性能，不推荐使用这些API

使用两个栈实现一个队列

export class ArrayQueue {
  private stackIn: number[] = [];

  private stackOut: number[] = [];

  appendTail(value: number): void {
    this.stackIn.push(value);
  }

  deleteHead(): number {
    let res: number = -1;
    if (!this.stackOut.length) {
      if (!this.stackIn.length) {
        res = -1;
      }
    }
    while (this.stackIn.length) {
      const n = this.stackIn.pop();
      if (n !== undefined) this.stackOut.push(n);
    }
    const outNumber = this.stackOut.pop();
    if (outNumber !== undefined) {
      res = outNumber;
    }

		// 将 stackOut 再赋给 stackIn
    while (this.stackOut.length) {
      const n = this.stackOut.pop();
      if (n !== undefined) {
        this.stackIn.push(n);
      }
    }
    return res;
  }

  get length(): number {
    return this.stackIn.length;
  }
}

性能测试

可以使用 console.time和console.timeEnd来获取中间代码的运行时间
// 链表实现队列
const newArrayQueue = new MyQueue();
console.time('queueWithList');
for (let i = 0; i < 10 * 1000; i++) {
  newArrayQueue.add(i);
}
for (let i = 0; i < 10 * 1000; i++) {
  newArrayQueue.delete();
}
console.timeEnd('queueWithList');

// 两个栈实现队列
const newArrayQueue = new ArrayQueue();
console.time('queueWithDoubleArray');
for (let i = 0; i < 10 * 1000; i++) {
  newArrayQueue.appendTail(i);
}
for (let i = 0; i < 10 * 1000; i++) {
  newArrayQueue.deleteHead();
}
console.timeEnd('queueWithDoubleArray');

// 数组API实现队列
console.time('queueWithArray');
let arr = [];
for (let i = 0; i < 10 * 10000; i++) {
  arr.push(i);
}
for (let i = 0; i < 10 * 10000; i++) {
  arr.shift();
}
console.timeEnd('queueWithArray');
notion image
可以从打印的结果上看到，
  • 使用链表实现的队列速度最快
  • 使用API实现的队列速度最慢
Copyright 2022 YoungLe