链表和数组，哪个实现队列更快？
- 数组是连续存储，push很快，shift很慢
- 链表是非连续存储，add和delete都很快（但查找很慢）
- 结论：链表实现队列更快
链表实现队列
- 单向链表，但要同时记录head和tail
- 要从tail入队，从head出队，否则出队时tail不好单位
- length要实时记录，不可遍历链表获取
代码实现
interface ILinkNode {
value: number
next: ILinkNode | null
}
class Myqueue {
private len:number = 0
private head:ILinkNode | null = null
private tail:ILinkNode | null = null
/**
* 入队，在tail位置
*/
add(n:number) {
const linkNode: ILinkNode = {
value: n,
next: null
}
// 处理head，如果head是null，说明当前队列是个空的
if (this.head == null) {
this.head = linkNode
}
// 处理tail
const tailNode:ILinkNode | null = this.tail
if (tailNode) {
tailNode.next = linkNode
}
// 将新的节点，作为队尾部
this.tail = linkNode
// 记录长度+1
this.len++;
}
/**
* 出队，在head位置
*/
delete(): number | null {
// 获取当前head，如果是null，说明是个空队列，返回null
const headNode: ILinkNode | null= this.head
if (headNode == null) return null;
if (this.len <= 0) return null;
// 当不是空队列时，取值
const value:number = headNode.value
// 处理head,让head指针指向下一个元素, 当前被删除的节点由js的gc处理
this.head = headNode.next
// 记录长度-1
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.log(q.length) // 3
console.log(q.delete()) // 100
console.log(q.length) // 2
console.log(q.delete()) // 200
console.log(q.length) // 1
console.log(q.delete()) // 300
console.log(q.length) // 0单元测试
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)
wxpect(q.delete()).toBe(200)
wxpect(q.delete()).toBe(300)
wxpect(q.delete()).toBeNull()
})
})性能测试
// 这是链表实现的队列
const q = new Myqueue();
console.time('link with queue');
for (let i = 0; i < 10 * 10000; i++) {
q.add(i);
}
for (let i = 0; i < 10 * 10000; i++) {
q.delete();
}
console.timeEnd('link with queue');
// 这个是由之前2个栈实现的队列
const q1 = new MyQueue1();
console.time('stack with queue');
for (let i = 0; i < 10 * 10000; i++) {
q1.add(i);
}
for (let i = 0; i < 10 * 10000; i++) {
q1.delete();
}
console.timeEnd('stack with queue');
// 这个是纯数组操作
const arr = [];
console.time('link with array');
for (let i = 0; i < 10 * 10000; i++) {
arr.push(i);
}
for (let i = 0; i < 10 * 10000; i++) {
arr.shift();
}
console.timeEnd('link with array');打印结果：
link with queue: 14.319ms
stack with queue: 35.966s
link with array: 9.087s由此可见在20万数据循环操作下，链表实现的队列最快，是栈队列的2572倍，是数组的643倍。这个数值具体看设备算力，这里只做参考。
性能分析
- 空间复杂度都是O(n)
- add时间复杂度：链表O(1), 数组O(1)
- delete时间复杂度：链表O(1),数组O(n)
总结：
- 数据结构的选择，要比算法优化更重要
- 要有时间复杂度的敏感性，如length不能遍历查找
