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

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

数据结构与算法 · 用链表实现队列

一、思路

记录链表的 head 、 tail
入队，在 tail 位置入队
出队，在 head 位置出队
队列的 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')

<div> <button style='padding: 10px 20px; color: #00b1fb;' class='rotate-btn' onclick='run()'>运行</button> <br> <b>queue with list run time：</b> <span style='color: red;' class='box1-ms'>0</span> <hr> <b>queue with array run time：</b> <span style='color: red;' class='box2-ms'>0</span> <hr> </div> <script> class MyQueue { head = null tail = null

len = 0

// 入队，在 tail 位置入队
add(n) {
  const newNode = {
    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() {
  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() {
  // length 需要单独记录存储，不能遍历链表获取，否则时间复杂度太高 O(n)
  return this.len
}

}

// 性能测试 function run() { const q1 = new MyQueue() console.time('queue with list') let s1 = performance.now() for (let i = 0; i < 10 * 10000; i++) { q1.add(i) } for (let i = 0; i < 10 * 10000; i++) { q1.delete() } document.querySelector('.box1-ms').innerText = performance.now() - s1 + ' ms'

const q2 = []
let s2 = performance.now()
for (let i = 0; i < 10 * 10000; i++) {
  q2.push(i)
}
for (let i = 0; i < 10 * 10000; i++) {
  q2.shift()
}
document.querySelector('.box2-ms').innerText = performance.now() - s2 + ' ms'

} </script>

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

四、算法复杂度

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

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

《数据结构与算法》系列

欢迎访问：天问博客