数组和链表都可以实现队列，但数组是连续存储，push 很快， shift 很慢。链表是非连续存储，
add 和 delete 都很快（但查找很慢，需要遍历整个链表）。但综合考虑链表实现队列会更高效
链表实现队列需要注意：
- 使用单向链表，需要同时记录 head 和 tail
- 要从 tail 入队，head 出队。否则tail出队不方便定位上一个元素
- 队列长度需要单独记录，不可实时遍历获取
功能实现
添加文件： queue-with-link-list.ts
定义节点类型
export interface LinkListNode {
value: number;
next: LinkListNode | null;
}
实现 MyLinkListQueue
/**
* 单向链表实现队列
*/
export class MyLinkListQueue {
private head: LinkListNode | null = null;
private tail: LinkListNode | null = null;
private len: number = 0;
/**
* 添加元素 入队列 尾部操作
*/
add(n: number) {
const newNode: LinkListNode = {
value: n,
next: null,
};
// 添加新节点
if (!this.head) {
this.head = newNode;
} else if (this.tail) {
this.tail.next = newNode;
}
// 更新 tail
this.tail = newNode;
// 更新队列长度
this.len += 1;
}
/**
* 移除元素 出队列 头部操作
*/
delete(): number | undefined {
if (!this.head) {
return undefined;
}
// 取值
const value = this.head.value;
// 更新 head
this.head = this.head.next;
// 更新长度
this.len -= 1;
return value;
}
get length() {
// length 需要单独存储不可实时遍历链表（否则时间复杂度是 O(n)）
return this.len;
}
}
添加功能测试
// 功能测试
export const link_list_queue_test = () => {
const q = new MyLinkListQueue();
console.info(q.length); // 0
q.add(100);
console.info(q.length); // 1
q.add(200);
console.info(q.length); // 2
q.add(300);
console.info(q.length); // 3
console.log(q.delete()); // 100
console.info(q.length); // 2
console.log(q.delete()); // 200
console.info(q.length); // 1
console.log(q.delete()); // 300
console.info(q.length); // 0
};
单元测试
添加文件： tests/queue-with-link-list.test.ts
import { MyLinkListQueue, LinkListNode } from '../src/utils';
describe('单向链表实现队列单元测试', () => {
test('空链表长度为0', () => {
const q = new MyLinkListQueue();
expect(q.length).toBe(0);
});
test('向队列添加3个值', () => {
const q = new MyLinkListQueue();
q.add(100);
expect(q.length).toBe(1);
q.add(200);
expect(q.length).toBe(2);
q.add(300);
expect(q.length).toBe(3);
});
test('移除队列元素', () => {
const q = new MyLinkListQueue();
q.add(100);
q.add(200);
q.add(300);
expect(q.length).toBe(3);
expect(q.delete()).toBe(100);
expect(q.length).toBe(2);
expect(q.delete()).toBe(200);
expect(q.length).toBe(1);
expect(q.delete()).toBe(300);
expect(q.length).toBe(0);
expect(q.delete()).toBe(undefined);
});
});
运行单元测试输出如下：
测试通过
PASS tests/queue-with-link-list.test.ts (9.272 s)
单向链表实现队列单元测试
✓ 空链表长度为0 (2 ms)
✓ 向队列添加3个值 (20 ms)
✓ 移除队列元素 (1 ms)
数组和链表队列性能测试
// 性能测试 链表和数组分别操作 100000 次 入队出队操作
export const link_list_quey_performance_test = () => {
// 链表队列
const q1 = new MyLinkListQueue();
console.time('q1-test');
for (let i = 0; i < 10 * 10000; i ++) {
q1.add(i);
}
for (let i = 0; i < 10 * 10000; i ++) {
q1.delete();
}
console.timeEnd('q1-test');
// 数组队列
const q2 = [];
console.time('q2-test');
for (let i = 0; i < 10 * 10000; i ++) {
q2.push(i);
}
for (let i = 0; i < 10 * 10000; i ++) {
q2.shift();
}
console.timeEnd('q2-test');
};
输出结果如下：
- q1-test: 19 ms
- q2-test: 811 ms
性能分析
数组和链表实现队列，空间复杂度都是 O(n), add的时间复杂度： 链表O(1)，数组O(1)，
delete的时间复杂度 链表O(1)，数组O(n)。数据结构的选择要比算法优化更重要，
要有时间复杂度的敏感性，如length需要单独存储。
