【数据结构与算法】(8)：用链表实现队列

前边有一章介绍了 用两个栈实现一个队列，本文就介绍一下怎么 用链表实现队列 ？

一、思路

1. 记录链表的 head 、 tail
2. 入队，在 tail 位置入队
3. 出队，在 head 位置出队
4. 队列的 length 单独记录存储

二、链表实现队列

• TS 代码演示

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

class MyQueue {
  private head: IListNode | null = null
  private tail: IListNode | null = null

  private len = 0

  // 入队，在 tail 位置入队
  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.log(q.length)
console.log(q.delete())
console.log(q.length)
console.log(q.delete())
console.log(q.length)
console.log(q.delete())
console.log(q.length)
console.log(q.delete())
console.log(q.length)
console.log(q.delete())
console.log(q.length)

三、性能测试

使用数组的 push 、shift 操作模拟队列，来对比用链表实现的队列，进行 10万次 入队、出队模拟测试。

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')

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')

运行


queue with list run time： 0

---

queue with array run time： 0

---

通过运行得知 用数组模拟队列 的方法远不如 用链表实现队列 的方法的执行效率。

四、算法复杂度

• 空间复杂度都是 O(n)
• add 时间复杂度：链表 O(1); 数组 O(1)
• delete 时间复杂度：链表 O(1); 数组 O(n)

总结：数据量越大越能突显算法的重要性。

---

《数据结构与算法》系列

1. 什么是算法复杂度
2. 堆(heap)、栈(stack)、队列(queue)
3. 把一个数组旋转k步
4. 判断字符串是否括号匹配
5. 数组、栈、链表、队列结构与对比
6. 用两个栈实现一个队列
7. 反转单向链表
8. 用链表实现队列
9. 二分查找
10. 查找两数之和

---

欢迎访问：天问博客

本文作者： Tiven
发布时间： 2023-07-16
最后更新： 2023-07-20
本文标题： 【数据结构与算法】(8)：用链表实现队列
本文链接： https://www.tiven.cn/p/a0867d06/
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明出处！