队列的概念

​ 队列是遵循FIFO（First In First Out，先进先出，也称为先来先服务）原则的一组有序的项。意如其名，就像排队一样，从尾部添加，从顶部移除，新添的元素必须排在队列的末尾。

1
2
3
4
5
6
7
8
9
flowchart LR
	subgraph a[队列]
		q[...]-->3-->2
	end
	
	subgraph b[执行]
		q1[1]
	end
	2-->q1

创建队列

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Queue {
  items: Array<any>
  constructor() {
    this.items = []
  }

  /**
   * 入队
   * 向队列尾部添加一个（或多个）新的项
   * @param el
   */
  enqueue(el): void {
    if (el instanceof Array) {
      this.items.push(...el)
    } else {
      this.items.push(el)
    }
  }

  /**
   * 出队
   * 移除队列的第一（即排在队列最前面的）项，并返回被移除的元素
   */
  dequeue(): any {
    return this.items.shift()
  }

  /**
   * 返回队列中第一个元素——最先被添加，也将是最先被移除的元素。
   * 队列不做任何变动（不移除元素，只返回元素信息——与Stack类的peek方法非常类似）
   */
  front(): any {
    return this.items[0]
  }

  /**
   * 判断队列是否为空
   * 如果队列中不包含任何元素，返回true，否则返回false
   */
  isEmpty(): boolean {
    return this.items.length === 0
  }

  /**
   * 返回队列包含的元素个数
   */
  size(): number {
    return this.items.length
  }
}

优先队列

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
class QueueElement<T, K> {
  element: T
  priority: K
  constructor(el, priority) {
    this.element = el
    this.priority = priority
  }
}

class PriorityQueue {
  items: Array<any>
  constructor() {
    this.items = []
  }

  /**
   * @desc 入队
   * @param el {T} 需要入队的元素
   * @param priority {number} 优先级
   */
  enqueue<T> (el: T, priority: number): void {
    // 创建一个带优先级的对象
    const queueElement = new QueueElement<T, number>(el, priority)
    // 判断队列是否为空，空就直接加进去
    if (this.isEmpty()) {
      this.items.push(queueElement)
    } else {
      //不为空判断该插在那个优先级前面
      const length = this.items.length
      let added = false
      for (let i = 0; i < length; i++) {
        if (this.items[i].priority > queueElement.priority) {
          this.items.splice(i, 0, queueElement)
          added = true
          break
        }
      }
      // 都不符合就放最后
      if (!added) {
        this.items.push(queueElement)
      }
    }
  }

  /**
   * @desc 出队
   * @return QueueElement {el, priority} 返回一个带优先级的对象
   */
  dequeue (): QueueElement<any, number> {
    return this.items.shift()
  }

  /**
   * @desc 返回队列第一名但不改变队列
   * @return QueueElement {el, priority} 返回一个带优先级的对象
   */
  front (): QueueElement<any, number> {
    const {el, priority} = this.items[0]
    return new QueueElement<any, number>(el, priority)
  }

  /**
   * @desc 返回队列长度
   * @return {number}
   */
  size (): number {
    return this.items.length
  }

  /**
   * @desc 判断队列是否为空
   * @return {boolean}
   */
  isEmpty (): boolean {
    return !this.items.length
  }
}

const priorityQueue = new PriorityQueue()
priorityQueue.enqueue('b', 2)
priorityQueue.enqueue('b', 2)
priorityQueue.enqueue('a', 1)
priorityQueue.enqueue('c', 3)
priorityQueue.enqueue('a', 1)
priorityQueue.enqueue('a', 1)
// QueueElement { element: 'a', priority: 1 }
console.log(priorityQueue.dequeue())
// [
//  	QueueElement { element: 'a', priority: 1 },
//  	QueueElement { element: 'a', priority: 1 },
//  	QueueElement { element: 'b', priority: 2 },
//  	QueueElement { element: 'b', priority: 2 },
//  	QueueElement { element: 'c', priority: 3 }
// ]
console.log(priorityQueue.items)

1
2
graph LR

本文参考自<学习JavaScript数据结构与算法>。