爱囡囡，爱前端

0%

TypeScript数据结构与算法：队列

发表于 分类于 ， ，

上一篇《TypeScript 数据结构与算法：栈》实现了 Typescript 中栈的数据结构与算法，本篇继续实现队列。

队列 （Queue）是遵循 先进先出（First In First Out，FIFO）原则的一组有序集合。队列在底部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾。就前端来说，当我们在浏览器中打开新标签时，其实就创建了一个任务队列。

数据结构

队列

普通队列实现时的几个必需方法如下：

  • enqueue(element)：队尾入队。
  • dequeue()：队首出队并返回被移除的元素。
  • peek()：查看队首元素。
  • isEmpty()：返回队列是否为空。
  • size()：返回队列包含的元素个数。

与栈类似，队列实现时用Map来存储数据，用lowestCount 来指示队首的键，用 count 来指示队尾的键；出队时则 lowestCount++，入队时则 count++。

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
export default class Queue<T> {
  private count: number;
  private lowestCount: number;
  private items: Map<number, T>;

  constructor() {
    this.count = 0;
    this.lowestCount = 0;
    this.items = new Map();
  }

  /**
   * @description: 在count方向（队列底部）入队
   * @param {T} element
   */
  enqueue(element: T): void {
    this.items.set(this.count, element);
    this.count++;
  }

  /**
   * @description: 在lowestCount方向（队列顶部）出队
   * @return {T} element
   */
  dequeue(): T {
    if (this.isEmpty()) {
      return undefined;
    }
    const result: T = this.items.get(this.lowestCount);
    this.items.delete(this.lowestCount);
    this.lowestCount++;
    return result;
  }

  /**
   * @description: 返回队列顶部的元素
   * @return {T} element
   */
  peek(): T {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items.get(this.lowestCount);
  }

  /**
   * @description: 返回队列是否为空
   * @return {Boolean}
   */
  isEmpty(): boolean {
    return this.items.size === 0;
  }

  /**
   * @description: 清空队列
   */
  clear(): void {
    this.items = new Map();
    this.count = 0;
    this.lowestCount = 0;
  }

  /**
   * @description: 返回队列元素的数目
   * @return {Number}
   */
  size(): number {
    return this.items.size;
  }

  /**
   * @description: 覆盖Object默认的toString
   * @return {String}
   */
  toString(): string {
    if (this.isEmpty()) {
      return '';
    }
    let objString: string = `${this.items.get(this.lowestCount)}`;
    for (let i = this.lowestCount + 1; i < this.count; i++) {
      objString = `${objString},${this.items.get(i)}`;
    }
    return objString;
  }
}

双端队列

双端队列（deque，Double-Ended Queue）是一种允许同时从队首和队尾添加和移除元素的特殊队列。

双端队列的一个常见应用是存储一系列的可撤销操作：

  1. 每当用户在软件中进行了一个操作，该操作会在一个双端队列的队尾入队。
  2. 当用户点击撤销按钮时，该操作会被从双端队列的队尾出队。
  3. 当操作次数过多后，最先进行的操作会被从双端队列的队首出队。

由于双端队列同时遵守了先进先出和后进先出原则，可以说是把队列和栈相结合的一种数据结构，必需的方法如下：

  • addBack(element)：队尾入队。
  • removeFront()：队首出队。
  • peekFront()：查看队首元素。
  • addFront(element)：队首入队（双端队列特有）。
  • removeBack()：队尾出队（双端队列特有）。
  • peekBack()：查看队尾元素（双端队列特有）。

在实现时，其实与队列的实现方式类似，只不过在队首入队时需要 lowestCount--，队尾出队时需要 count--。

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
export default class Deque<T> {
  private count: number;
  private lowestCount: number;
  private items: Map<number, T>;

  constructor() {
    this.count = 0;
    this.lowestCount = 0;
    this.items = new Map();
  }

  /**
   * @description: 在lowestCount方向（队列顶部）入队
   * @param {T} element
   */
  addFront(element: T): void {
    this.lowestCount--;
    this.items.set(this.lowestCount, element);
  }

  /**
   * @description: 在count方向（队列底部）入队
   * @param {T} element
   */
  addBack(element: T): void {
    this.items.set(this.count, element);
    this.count++;
  }

  /**
   * @description: 在lowestCount方向（队列顶部）出队
   * @return {T} element
   */
  removeFront(): T {
    if (this.isEmpty()) {
      return undefined;
    }
    const result = this.items.get(this.lowestCount);
    this.items.delete(this.lowestCount);
    this.lowestCount++;
    return result;
  }

  /**
   * @description: 在count方向（队列底部）出队
   * @return {T} element
   */
  removeBack(): T {
    if (this.isEmpty()) {
      return undefined;
    }
    this.count--;
    const result = this.items.get(this.count);
    this.items.delete(this.count);
    return result;
  }

  /**
   * @description: 返回队列顶部的元素
   * @return {T} element
   */
  peekFront(): T {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items.get(this.lowestCount);
  }

  /**
   * @description: 返回队列底部的元素
   * @return {T} element
   */
  peekBack(): T {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items.get(this.count - 1);
  }

  /**
   * @description: 返回队列是否为空
   * @return {Boolean}
   */
  isEmpty(): boolean {
    return this.items.size === 0;
  }

  /**
   * @description: 清空队列
   */
  clear(): void {
    this.items = new Map();
    this.count = 0;
    this.lowestCount = 0;
  }

  /**
   * @description: 返回队列元素的数目
   * @return {Number}
   */
  size(): number {
    return this.items.size;
  }

  /**
   * @description: 覆盖Object默认的toString
   * @return {String}
   */
  toString(): string {
    if (this.isEmpty()) {
      return '';
    }
    let objString: string = `${this.items.get(this.lowestCount)}`;
    for (let i = this.lowestCount + 1; i < this.count; i++) {
      objString = `${objString},${this.items.get(i)}`;
    }
    return objString;
  }
}

算法

击鼓传花

书中用队列实现了一个奇怪版本的击鼓传花游戏（hot potato）。在这个游戏中，孩子们围成一个圆圈，按同一方向把花尽快地传递给下一个人。固定次数后传花停止，这个时候花在谁手里，谁就退出圆圈、结束游戏。重复这个过程，直到只剩一个孩子（胜者）。

击鼓传花算法的关键在于需要在元素出队的同时入队，实现循环队列：

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
import Queue from '../data-structures/queue';

/**
 * @param {Array<T>} elimitated 失败者数组
 * @param {T} winner 胜利者
 */
interface HotPotatoResult<T> {
  elimitated: Array<T>;
  winner: T;
}

/**
 * @description: 击鼓传花算法
 * @param {Array<T>} 传花的元素数组
 * @param {number} 每次传花的次数
 * @return {HotPotatoResult<T>} 返回算法结果
 */
export function hotPotato<T>(
  elementsList: Array<T>,
  num: number
): HotPotatoResult<T> {
  const queue: Queue<T> = new Queue();
  const elimitatedList: Array<T> = [];

  // 初始化队列
  for (let i = 0; i < elementsList.length; i++) {
    queue.enqueue(elementsList[i]);
  }

  while (queue.size() > 1) {
    // 循环队列旋转固定num次数
    for (let i = 0; i < num; i++) {
      // 元素出队的同时又入队，形成循环队列
      queue.enqueue(queue.dequeue());
    }
    // 被抽中的元素则被出队淘汰
    elimitatedList.push(queue.dequeue());
  }

  return {
    elimitated: elimitatedList,
    winner: queue.dequeue(),
  };
}

测试下击鼓传花游戏的结果：

1
2
3
const names = ['白胡子', '红发', '凯多', '大妈', '黑胡子'];

hotPotato(names, 6); // { elimitated: [ '红发', '黑胡子', '白胡子', '凯多' ], winner: '大妈' }

大妈拿下一城。

回文检查器

回文是正反都能读通的单词、词组、数或一系列字符的序列，例如 madam 或 racecar。

回文检查可以用很多算法实现，双端队列是实现该算法最简单的数据结构。实现的关键就是同时在队首和队尾出队，判断字符是否相同：

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
import Deque from '../data-structures/deque';

/**
 * @description: 回文检查器
 * @param {string} aString 待检查的字符串
 * @return {boolean} 返回是否回文
 */
export function palindromeChecker(aString: string): boolean {
  // 检查字符串的合法性
  if (
    aString === undefined ||
    aString === null ||
    (aString !== null && aString.length === 0)
  ) {
    return false;
  }

  // 将字符串小写并剔除空格
  const lowerString: string = aString.toLocaleLowerCase().split(' ').join('');

  // 初始化双端队列
  const deque: Deque<string> = new Deque();
  for (let i = 0; i < lowerString.length; i++) {
    deque.addBack(lowerString.charAt(i));
  }

  // 分别从顶部和底部出队一个元素进行对比
  while (deque.size() > 1) {
    if (deque.removeFront() !== deque.removeBack()) {
      return false;
    }
  }

  return true;
}

下一篇来分析链表。

前端记事本，不定期更新，欢迎关注！

👆 全文结束，棒槌时间到 👇