TypeScript数据结构之队列结构Queue教程示例

1. 认识队列结构

队列是一个 先进先出（FIFO） 的数据结构

js 中没有队列，但我们可以用 数组或链表 实现队列的所有功能

队列的常用操作:

enqueue(element)：向队列尾部添加一个（多个）新的项

dequeue()：移除队列的第一项，并返回被移除的元素

front/peek()：返回队列中的第一个元素

isEmpty()：判断队列是否为空

size()：返回队列的元素个数

队列的结构示意图：

2. 实现队列结构封装

队列的实现和栈一样也有两种实现方式：

• 基于 数组 实现
• 基于 链表 实现

链表也是一种数据结构，js 中没有自带链表结构，后续会写关于链表的文章，本章先使用数组来实现。

实现：

// 封装一个队列
export default class ArrayQueue<T = any> {
  private data: T[] = [];
  constructor(data: T[]) {
    this.data = data || [];
  }
  enqueue(element: T): void {
    this.data.push(element);
  }
  dequeue(): T | undefined {
    return this.data.shift();
  }
  peek(): T | undefined {
    return this.data[0];
  }
  isEmpty(): boolean {
    return this.data.length === 0;
  }
  size(): number {
    return this.data.length;
  }
}

测试：

const queue = new ArrayQueue<number>();
queue.push(1);
queue.push(2);
queue.pop();
queue.push(3);
console.log(queue); // ArrayQueue { data: [ 2, 3 ] }

3. 实战一：最近的请求次数

这是 Leetcode 上的第 933 道题，难度为 简单

3.1 题目描述

写一个 RecentCounter 类来计算特定时间范围内最近的请求。

请你实现 RecentCounter 类：

• RecentCounter() 初始化计数器，请求数为 0 。
• int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数。

保证 每次对 ping 的调用都使用比之前更大的 t 值。

示例 1：

输入：
["RecentCounter", "ping", "ping", "ping", "ping"]
[[], [1], [100], [3001], [3002]]
输出：
[null, 1, 2, 3, 3]
解释：
RecentCounter recentCounter = new RecentCounter();
recentCounter.ping(1);     // requests = [1]，范围是 [-2999,1]，返回 1
recentCounter.ping(100);   // requests = [1, 100]，范围是 [-2900,100]，返回 2
recentCounter.ping(3001);  // requests = [1, 100, 3001]，范围是 [1,3001]，返回 3
recentCounter.ping(3002);  // requests = [1, 100, 3001, 3002]，范围是 [2,3002]，返回 3

提示：

• 1 <= t <= 109
• 保证每次对 ping 调用所使用的 t 值都 严格递增
• 至多调用 ping 方法 104 次

3.2 解一：队列

思路：

我们可以用一个队列维护发生请求的时间，当在时间 t 收到请求时，将时间 t 入队。 保证队列的 尾部值 减去队列的 首部值 小于等于 3000，队列中的元素数量即为 最近的请求次数

代码：

class RecentCounter {
  queue: ArrayQueue<number>;
  constructor() {
    this.queue = new ArrayQueue<number>();
  }
  ping(t: number): number {
    this.queue.enqueue(t);
    while (this.queue.peek() < t - 3000) {
      this.queue.dequeue();
    }
    return this.queue.size();
  }
}
/**
 * Your RecentCounter object will be instantiated and called as such:
 * var obj = new RecentCounter()
 * var param_1 = obj.ping(t)
 */

复杂度分析：

时间复杂度：均摊 O(1)，每个元素至多入队出队各一次。

空间复杂度：O(L)，其中 L 为队列的最大元素个数。

4. 实战二：无法吃午餐的学生数量

这是 Leetcode 上的第 1700 道题，难度为 简单

4.1 题目描述

学校的自助午餐提供圆形和方形的三明治，分别用数字 0 和 1 表示。所有学生站在一个队列里，每个学生要么喜欢圆形的要么喜欢方形的。
餐厅里三明治的数量与学生的数量相同。所有三明治都放在一个 栈 里，每一轮：

• 如果队列最前面的学生 喜欢 栈顶的三明治，那么会 拿走它 并离开队列。
• 否则，这名学生会 放弃这个三明治 并回到队列的尾部。

这个过程会一直持续到队列里所有学生都不喜欢栈顶的三明治为止。

给你两个整数数组 students 和 sandwiches ，其中 sandwiches[i] 是栈里面第 i​​​​​​ 个三明治的类型（i = 0 是栈的顶部）， students[j] 是初始队列里第 j​​​​​​ 名学生对三明治的喜好（j = 0 是队列的最开始位置）。请你返回无法吃午餐的学生数量。

示例 1：

输入： students = [1,1,0,0], sandwiches = [0,1,0,1]
输出： 0 解释：
- 最前面的学生放弃最顶上的三明治，并回到队列的末尾，学生队列变为 students = [1,0,0,1]。
- 最前面的学生放弃最顶上的三明治，并回到队列的末尾，学生队列变为 students = [0,0,1,1]。
- 最前面的学生拿走最顶上的三明治，剩余学生队列为 students = [0,1,1]，三明治栈为 sandwiches = [1,0,1]。
- 最前面的学生放弃最顶上的三明治，并回到队列的末尾，学生队列变为 students = [1,1,0]。
- 最前面的学生拿走最顶上的三明治，剩余学生队列为 students = [1,0]，三明治栈为 sandwiches = [0,1]。
- 最前面的学生放弃最顶上的三明治，并回到队列的末尾，学生队列变为 students = [0,1]。
- 最前面的学生拿走最顶上的三明治，剩余学生队列为 students = [1]，三明治栈为 sandwiches = [1]。
- 最前面的学生拿走最顶上的三明治，剩余学生队列为 students = []，三明治栈为 sandwiches = []。
所以所有学生都有三明治吃。

示例 2：

输入： students = [1,1,1,0,0,1], sandwiches = [1,0,0,0,1,1]
输出： 3

提示：

• 1 <= students.length, sandwiches.length <= 100
• students.length == sandwiches.length
• sandwiches[i] 要么是 0 ，要么是 1 。
• students[i] 要么是 0 ，要么是 1 。

4.2 解一：队列

思路： 我们可以维护两个队列，一个是学生队列，一个是三明治队列。

循环比较 学生队列 和 三明治队列 的 头部第一个元素，如果相同则都 移除 它们，如果不相同则将学生队列的头部元素移到尾部，直到碰到下一组相同的两个头部元素 或者 学生队列所有学生都不喜欢三明治队列的第一个三明治。

代码：

function countStudents(students: number[], sandwiches: number[]): number {
  const studentsQueue = new ArrayQueue<number>(students);
  const sandwichesQueue = new ArrayQueue<number>(sandwiches);
  let count = 0;
  while (studentsQueue.size()) {
    if (studentsQueue.peek() === sandwichesQueue.peek()) {
      studentsQueue.dequeue();
      sandwichesQueue.dequeue();
      count = 0;
    } else {
      studentsQueue.enqueue(studentsQueue.dequeue()!);
      count++;
    }
    if (count === studentsQueue.size()) return sandwichesQueue.size();
  }
  return 0;
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是学生的数量。
• 空间复杂度：O(1)。

5. 实战三：字符串中的第一个唯一字符

这是 Leetcode 上的第 387 道题，难度为 简单

5.1 题目描述

给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。

示例 1：

输入: s = "leetcode"
输出: 0

示例 2:

输入: s = "loveleetcode"
输出: 2

示例 3:

输入: s = "aabb"
输出: -1

提示:

• 1 <= s.length <= 105
• s 只包含小写字母

5.2 解一：哈希表

思路：

维护一个 map，分两次遍历字符串

• 第一次遍历存储每个字符对应的出现次数
• 第二次遍历取出第一个只出现第一次的字符

代码：

function firstUniqChar(s: string): number {
  const map = new Map<string, number>();
  for (let i = 0; i < s.length; i++) {
    let n = map.get(s[i]);
    n ? map.set(s[i], n + 1) : map.set(s[i], 1);
  }
  for (let i = 0; i < s.length; i++) {
    if (map.get(s[i]) === 1) return i;
  }
  return -1;
}

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(∣Σ∣)，其中 Σ 是字符集，在本题中 s 只包含小写字母，因此 ∣Σ∣≤26 。我们需要 O(∣Σ∣) 的空间存储哈希映射。

5.3 解二：队列

思路：

维护一个队列，按照顺序存储每一个字符以及它们第一次出现的位置。当我们对字符串进行遍历时，设当前遍历到的字符为 c，如果 c 不在哈希映射中，我们就将 c 与它的索引作为一个二元组放入队尾，否则我们就需要检查队列中的元素是否都满足「只出现一次 的要求，即我们不断地根据哈希映射中存储的值（是否为 −1）选择弹出队首的元素，直到队首元素 「真的」 只出现了一次或者队列为空。

在遍历完成后，如果队列为空，说明没有不重复的字符，返回 −1，否则队首的元素即为第一个不重复的字符以及其索引的二元组

代码：

function firstUniqChar(s: string): number {
  const map = new Map<string, number>();
  const queue = new ArrayQueue<[string, number]>();
  for (let i = 0; i < s.length; i++) {
    if(!map.has(s[i])) {
      map.set(s[i], i)
      queue.enqueue([s[i], i]);
    } else {
      map.set(s[i], -1)
      while(queue.size() && map.get((queue.peek() as [string,number])[0]) === -1) {
        queue.dequeue()
      }
    }
  }
  return queue.size() ? (queue.peek() as [string, number])[1] : -1;
}

复杂度分析:

• 时间复杂度：O(n)
• 空间复杂度：O(∣Σ∣)