cover

数据结构与算法之队列

最后更新:  阅读时间: 2 min 知识共享许可协议

前言

队列是一种列表，只能在队尾插入元素，在队首删除元素。队列用于存储按顺序排列的的数据，先进先出，可以将队列想象成在饭店排队取餐的人群，在队伍前面的先取餐，后来的人后取餐。

实现

用 TypeScript 实现队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Queue {
  data: Array<any> = []

  // 入队
  enqueue(element: any) {
    this.data.push(element)
  }

  // 出队
  dequeue() {
    return this.data.shift()
  }

  // 返回第一个元素
  front() {
    return this.data[0]
  }

  // 返回最后一个元素
  back() {
    return this.data[this.data.length - 1]
  }

  // 显示队列中所有元素
  toString() {
    return this.data.map(ele => `${ele}`).toString()
  }

  // 判断队列是否为空
  empty() {
    if (this.data.length) {
      return false
    }
    return true
  }
}

测试一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const queue = new Queue()

queue.enqueue('a')
queue.enqueue('b')
queue.enqueue('c')
queue.enqueue('d')
queue.enqueue('e')

console.log('queue: ', queue)
console.log('front: ', queue.front())
console.log('back: ', queue.back())

queue.dequeue()
queue.dequeue()
queue.dequeue()
queue.dequeue()

console.log('queue: ', queue)

console.log('queue: ', queue.empty())

输出

1
2
3
4
5
6
7
8
9
queue:  Queue { data: [ 'a', 'b', 'c', 'd', 'e' ] }

front: a

back:  e

queue:  Queue { data: [ 'e' ] }

queue:  false

优先队列

优先队列指的是在删除队列中元素的时候需要考虑元素的优先级，优先级高的元素先出队，优先级低的后出队，同等优先级的元素按原本的顺序出队。

首先需要一个具有优先级的元素

1
2
3
4
interface Element {
  data: any
  code: number // code 表示优先级，数值越小优先级越高，0 为最高
}

然后需要修改下队列的出队方法，找到队列中优先级最高的元素，然后将其移除队列

1
2
3
4
5
6
7
dequeue() {
  const codes = this.data.map(ele => ele.code)
  const minCode = Math.min.apply(null, codes)
  const index = this.data.findIndex(ele => ele.code === minCode)

  return this.data.splice(index, 1)
}

测试一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const queue = new Queue()

queue.enqueue({ data: 'a', code: 5 })
queue.enqueue({ data: 'b', code: 4 })
queue.enqueue({ data: 'c', code: 3 })
queue.enqueue({ data: 'd', code: 2 })
queue.enqueue({ data: 'e', code: 1 })

console.log('queue: ', queue)

queue.dequeue()
queue.dequeue()
queue.dequeue()
queue.dequeue()

console.log('queue: ', queue)

输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
queue:  Queue {
  data:
   [
     { data: 'a', code: 5 },
     { data: 'b', code: 4 },
     { data: 'c', code: 3 },
     { data: 'd', code: 2 },
     { data: 'e', code: 1 }
  ]
}

queue:  Queue {
  data:
    [
      { data: 'a', code: 5 },
      { data: 'b', code: 4 }
    ]
}

可以看到队列中剩下了优先级较低的元素

Buy Me A Coffee
← 如何在 Egg.js 中使用 Sequelize 的事务 Transaction 关于 Flutter 的安卓打包 →