会飞的菜虫

优先队列

在计算机科学中, 优先级队列(priority queue) 是一种抽象数据类型, 它类似于常规的队列或栈, 但每个元素都有与之关联的“优先级”。

在优先队列中, 低优先级的元素之前前面应该是高优先级的元素。 如果两个元素具有相同的优先级, 则根据它们在队列中的顺序是它们的出现顺序即可。

优先队列虽通常用堆来实现,但它在概念上与堆不同。优先队列是一个抽象概念，就像“列表”或“图”这样的抽象概念一样;

正如列表可以用链表或数组实现一样，优先队列可以用堆或各种其他方法实现,例如无序数组。

堆 (数据结构)

在计算机科学中, 一个 堆(heap) 是一种特殊的基于树的数据结构，它满足下面描述的堆属性。

在一个 最小堆(min heap) 中, 如果 P 是 C 的一个父级节点, 那么 P 的 key(或 value)应小于或等于 C 的对应值.

哈希表

在计算中, 一个 哈希表(hash table 或 hash map) 是一种实现 关联数组(associative array)
的抽象数据类型, 该结构可以将 _键映射到值_。

哈希表使用 哈希函数/散列函数 来计算一个值在数组或桶(buckets)中或槽(slots)中对应的索引,可使用该索引找到所需的值。

理想情况下,散列函数将为每个键分配给一个唯一的桶(bucket),但是大多数哈希表设计采用不完美的散列函数,这可能会导致”哈希冲突(hash collisions)”,也就是散列函数为多个键(key)生成了相同的索引,这种碰撞必须
以某种方式进行处理。

栈

在计算机科学中, 一个 栈(stack) 是一种抽象数据类型,用作表示元素的集合,具有两种主要操作:

• push, 添加元素到栈的顶端(末尾);
• pop, 移除栈最顶端(末尾)的元素.

以上两种操作可以简单概括为“后进先出(LIFO = last in, first out)”。

此外,应有一个 peek 操作用于访问栈当前顶端(末尾)的元素。

“栈”这个名称,可类比于一组物体的堆叠(一摞书,一摞盘子之类的)。

队列

在计算机科学中, 一个 队列(queue) 是一种特殊类型的抽象数据类型或集合。集合中的实体按顺序保存。

队列基本操作有两种：入队和出队。从队列的后端位置添加实体，称为入队；从队列的前端位置移除实体，称为出队。

队列中元素先进先出 FIFO (first in, first out)的示意

双向链表

在计算机科学中, 一个 双向链表(doubly linked list) 是由一组称为节点的顺序链接记录组成的链接数据结构。每个节点包含两个字段，称为链接，它们是对节点序列中上一个节点和下一个节点的引用。开始节点和结束节点的上一个链接和下一个链接分别指向某种终止节点，通常是前哨节点或 null，以方便遍历列表。如果只有一个前哨节点，则列表通过前哨节点循环链接。它可以被概念化为两个由相同数据项组成的单链表，但顺序相反。

两个节点链接允许在任一方向上遍历列表。

在双向链表中进行添加或者删除节点时,需做的链接更改要比单向链表复杂得多。这种操作在单向链表中更简单高效,因为不需要关注一个节点（除第一个和最后一个节点以外的节点）的两个链接,而只需要关注一个链接即可。

链表

在计算机科学中, 一个 链表 是数据元素的线性集合, 元素的线性顺序不是由它们在内存中的物理位置给出的。 相反, 每个元素指向下一个元素。它是由一组节点组成的数据结构,这些节点一起,表示序列。

在最简单的形式下，每个节点由数据和到序列中下一个节点的引用(换句话说，链接)组成。这种结构允许在迭代期间有效地从序列中的任何位置插入或删除元素。

更复杂的变体添加额外的链接，允许有效地插入或删除任意元素引用。链表的一个缺点是访问时间是线性的(而且难以管道化)。

更快的访问，如随机访问，是不可行的。与链表相比，数组具有更好的缓存位置。

Comparator 类是一个用于比较两个值的工具类.

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

export default class Comparator {
  /**
   * 类的构造函数, 接受一个可选的compareFunction参数, 用于自定义比较函数.
   * 如果没有传入compareFunction, 则会使用默认的比较函数.
   */
  constructor(compareFunction) {
    this.compare = compareFunction || Comparator.defaultCompareFunction;
  }

  /**
   * 默认的比较函数, 假设a和b是字符串或数字.
   * 如果a 等于 b, 则返回0
   * 如果a 小于 b, 则返回-1
   * 如果a 大于 b, 则返回1
   */
  static defaultCompareFunction(a, b) {
    if (a === b) {
      return 0;
    }

    return a < b ? -1 : 1;
  }

  /**
   * 检查两个变量是否相等.
   * 内部调用this.compare(a, b), 如果返回值为0, 表示相等, 返回true; 否则返回false.
   */
  equal(a, b) {
    return this.compare(a, b) === 0;
  }

  /**
   * 检查变量a是否小于b.
   * 内部调用this.compare(a, b), 如果返回值是-1, 表示a小于b, 返回true; 否则返回false
   */
  lessThan(a, b) {
    return this.compare(a, b) < 0;
  }

  /**
   * 检查变量a是否大于b
   * 内部调用this.compare(a, b), 如果返回值为1, 表示a大于b, 返回true; 否则返回false
   */
  greaterThan(a, b) {
    return this.compare(a, b) > 0;
  }

  /**
   * 检查变量a是否小于等于b.
   */
  lessThanOrEqual(a, b) {
    return this.lessThan(a, b) || this.equal(a, b);
  }

  /**
   * 检查变量a是否大于等于b
   */
  greaterThanOrEqual(a, b) {
    return this.greaterThan(a, b) || this.equal(a, b);
  }

  /**
   * 反转比较顺序. 将当前的比较函数this.compare替换为compareOriginal(b, a), 实现反转比较的效果.
   */
  reverse() {
    const compareOriginal = this.compare;
    this.compare = (a, b) => compareOriginal(b, a);
  }
}

在Comparator类种, compareFunction是一个可选参数, 可以传入自定义的比较函数. 如果没有传入比较函数, 则会使用默认的比较函数. compareFunction应该是一个函数, 接受两个参数a和b, 返回一个数字, 表示它们的比较结果.

这个类的目的是为了提供一种方便的方式来进行比较操作, 以及在需要时动态地改变比较顺序.

• 源码地址: JavaScript Algorithms and Data Structures

使用 CSS 实现翻牌效果, 结果图:

创建 Dockerfile 文件

在 express 项目的目录下, 新建 dockerfile 文件, 命名为 Dockerfile

1

touch Dockerfile

编辑Dockerfile文件: