队列是一种列表，只能在队尾插入元素，在队首删除元素。队列用于存储按顺序排列的的数据，先进先出，可以将队列想象成在饭店排队取餐的人群，在队伍前面的先取餐，后来的人后取餐
前言
队列是一种列表，只能在队尾插入元素，在队首删除元素。队列用于存储按顺序排列的的数据，先进先出，可以将队列想象成在饭店排队取餐的人群，在队伍前面的先取餐，后来的人后取餐。
实现
用 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
}
|
然后需要修改下队列的出队方法，找到队列中优先级最高的元素，然后将其移除队列
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 }
]
}
|
可以看到队列中剩下了优先级较低的元素