背景

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

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

思路

注意：

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

代码

interface IListNode {
    value: number
    next: IListNode | null
}

export class MyQueue {
    private head: IListNode | null = null
    private tail: IListNode | null = null
    private len = 0

    /**
     * 入队，在 tail 位置
     * @param n number
     */
    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.tail = newNode

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

    /**
     * 出队，在 head 位置
     */
    delete(): number | null {
        const headNode = this.head
        if (headNode == null) return null
        if (this.len <= 0) return null

        // 取值
        const value = headNode.value

        // 处理 head
        this.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()
    })
})

复杂度对比：
add 函数时间复杂度：
链表：O(1)，数组：O(1)

delete 函数时间复杂度：
链表：O(1)，数组：O(n)

栈、队列和数组、链表的区别

栈、队列是一种逻辑结构，是比较抽象的概念。

数组、链表是物理结构。任何的编程语言都有自己的数组（有的没有），可以说数组来实现栈的结构。

同样，任何编程语言都可以实现链表，只不过一般不会有具体的链表API，不像数组，但是也是用编程语言来实现的，和数组的本质是一样的。

数组和链表都可以实现队列，但是链表实现起来性能更好。

一句话总结：数组实现栈，链表实现队列。