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

news/2024/5/8 3:24:00/文章来源:https://blog.csdn.net/weixin_43972437/article/details/130106320

背景

对于这个问题，我们先来思考一下数组和链表各有什么特点。
数组：连续存储，push 很快，shift 很慢。
链表：非连续存储，add、delete 都很快，但是查找很慢。

所以，我们可以得出结论，链表实现队列更快一点。

思路

在这里插入图片描述
注意：

length 不能遍历，在add和delete的时候对应的增减length
注意处理头部和尾部
队尾部入队，队头部出队。入队的时候把tail指向当前节点，出队的时候把 head 指向当前 head 的next

代码

interface IListNode {value: numbernext: IListNode | null
}export class MyQueue {private head: IListNode | null = nullprivate tail: IListNode | null = nullprivate len = 0/*** 入队，在 tail 位置* @param n number*/add(n: number) {const newNode: IListNode = {value: n,next: null,}// 处理 headif (this.head == null) {this.head = newNode}// 处理 tailconst tailNode = this.tailif (tailNode) {tailNode.next = newNode}this.tail = newNode// 记录长度this.len++}/*** 出队，在 head 位置*/delete(): number | null {const headNode = this.headif (headNode == null) return nullif (this.len <= 0) return null// 取值const value = headNode.value// 处理 headthis.head = headNode.next// 记录长度this.len--return value}get length(): number {// length 要单独存储，不能遍历链表来获取（否则时间复杂度太高 O(n)）return this.len}
}

// 功能测试
const q = new MyQueue()
q.add(100)
q.add(200)
q.add(300)
console.info('length1', q.length)
console.log(q.delete())
console.info('length2', q.length)
console.log(q.delete())
console.info('length3', q.length)
console.log(q.delete())
console.info('length4', q.length)
console.log(q.delete())
console.info('length5', q.length)

在这里插入图片描述
接下来对比一下数组实现队列和链表实现队列的速度：

// 性能测试
// 链表实现的队列
const q1 = new MyQueue()
console.time('queue with list')
for (let i = 0; i < 10 * 10000; i++) {q1.add(i)
}
for (let i = 0; i < 10 * 10000; i++) {q1.delete()
}
console.timeEnd('queue with list') // 17ms// 数组实现队列
const q2 = []
console.time('queue with array')
for (let i = 0; i < 10 * 10000; i++) {q2.push(i) // 入队
}
for (let i = 0; i < 10 * 10000; i++) {q2.shift() // 出队
}
console.timeEnd('queue with array') // 431ms

在这里插入图片描述
测试用例

import { MyQueue } from './queue-with-list'describe('链表实现队列', () => {it('add and length', () => {const q = new MyQueue()expect(q.length).toBe(0)q.add(100)q.add(200)q.add(300)expect(q.length).toBe(3)})it('delete', () => {const q = new MyQueue()expect(q.delete()).toBeNull()q.add(100)q.add(200)q.add(300)expect(q.delete()).toBe(100)expect(q.delete()).toBe(200)expect(q.delete()).toBe(300)expect(q.delete()).toBeNull()})
})