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

目录
  • 1. 认识队列结构
  • 2. 实现队列结构封装
  • 3. 实战一:最近的请求次数
    • 3.1 题目描述
    • 3.2 解一:队列
  • 4. 实战二:无法吃午餐的学生数量
    • 4.1 题目描述
    • 4.2 解一:队列
  • 5. 实战三:字符串中的第一个唯一字符
    • 5.1 题目描述
    • 5.2 解一:哈希表
    • 5.3 解二:队列

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(∣Σ∣)

以上就是TypeScript数据结构之队列结构Queue教程示例的详细内容,更多关于TypeScript 队列结构的资料请关注我们其它相关文章!

(0)

相关推荐

  • TypeScript数据结构栈结构Stack教程示例

    目录 1. 认识栈结构 2. 实现栈结构的封装 2.1 基于数组 v1 版 2.2 使用泛型重构 v2 版 3. 实战一:有效的括号 3.1 题目描述 3.2 题目分析 3.3 解一:栈 4. 实战二:下一个更大元素 I 4.1 题目描述 4.2 解一:暴力 4.3 解二:单调栈 1. 认识栈结构 栈是一种 后进先出(LIFO) 的数据结构 在 js 中没有栈,但我们可以用 数组或链表 实现栈的所有功能 栈的常用操作: push(入栈) pop(出栈) peek(返回栈顶元素) isEmpty(

  • 前端算法之TypeScript包含min函数的栈实例详解

    目录 前言 思路梳理 实现代码 示例代码 前言 基于数据结构: “栈”,实现一个min函数,调用此函数即可获取栈中的最小元素.在该栈中,调用min.push.pop的时间复杂度都是O(1). 本文就跟大家分享下这个算法,欢迎各位感兴趣的开发者阅读本文. 思路梳理 相信大多数开发者看到这个问题,第一反应可能是每次往栈中压入一个新元素时,将栈里的所有元素排序,让最小的元素位于栈顶,这样就能在O(1)的时间内得到最小元素了.但这种思路不能保证最后入栈的元素能够最先出栈,因此这个思路行不通. 紧接着,我

  • TypeScript手写一个简单的eslint插件实例

    目录 引言 前置知识 第一个eslint规则:no-console 本地测试 本地查看效果 no-console规则添加功能:排除用户指定的文件 发布npm包 引言 看到参考链接1以后,觉得用TS写一个eslint插件应该很简单⌨️,尝试下来确实如此. 前置知识 本文假设 你对AST遍历有所了解. 你写过单测用例. 第一个eslint规则:no-console 为了简单,我们只使用tsc进行构建.首先package.json需要设置入口"main": "dist/index.

  • TypeScript合并两个排序链表的方法详解

    目录 前言 思路分析 实现代码 测试用例 示例代码 前言 给定两个递增排序的链表,如何将这两个链表合并?合并后的链表依然按照递增排序.本文就跟大家分享一种解决方案,欢迎各位感兴趣的开发者阅读本文. 思路分析 经过前面的学习,我们知道了有关链表的操作可以用指针来完成.同样的,这个问题也可以用双指针的思路来实现: p1指针指向链表1的头节点 p2指针指向链表2的头节点 声明一个变量存储合并后的链表,比对两个指针指向的节点值大小: 如果p1指针指向的节点值比p2指向的值小,合并后的链表节点就取p1节点

  • TypeScript调整数组元素顺序算法

    目录 前言 实现思路 实现代码 代码的可扩展性 测试用例 示例代码 总结 前言 有一个整数数组,我们想按照特定规则对数组中的元素进行排序,比如:数组中的所有奇数位于数组的前半部分. 本文将带大家实现这个算法,欢迎各位感兴趣的开发者阅读本文. 实现思路 我们通过一个实例来分析下:假设有这样一个数组:[2, 4, 5, 6, 7, 8, 9, 11],将奇数移动到最前面后,就是:[11, 9, 5, 7, 6, 8, 4, 2]. 通过观察后,我们发现在扫描这个数组的时候,如果发现有偶数出现在奇数的

  • Typescript tsconfig.json的配置详情

    目录 背景 配置详情 include/exclude/files 三者的关系 typeRoots & types 背景 当我们在做 typescript 相关的项目时,总是不可避免的要配置 ts,但是每个配置项到底代表什么意思,以及我们可能需要哪些配置项呢?每次去查官网.查相关资料,感觉都比较费时费力.所以直接就把所有配置都整理出来,当作一个“字典”来用,这样就轻松了许多,不知道对大家有帮助吗? 配置详情 { "compilerOptions": { /* Basic Opti

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

    目录 1. 认识队列结构 2. 实现队列结构封装 3. 实战一:最近的请求次数 3.1 题目描述 3.2 解一:队列 4. 实战二:无法吃午餐的学生数量 4.1 题目描述 4.2 解一:队列 5. 实战三:字符串中的第一个唯一字符 5.1 题目描述 5.2 解一:哈希表 5.3 解二:队列 1. 认识队列结构 队列是一个 先进先出(FIFO) 的数据结构 js 中没有队列,但我们可以用 数组或链表 实现队列的所有功能 队列的常用操作: enqueue(element):向队列尾部添加一个(多个)

  • JavaScript队列结构Queue实现过程解析

    一.队列简介 队列是是一种受限的线性表,特点为先进先出(FIFO:first in first out). 受限之处在于它只允许在表的前端(front)进行删除操作:在表的后端(rear)进行插入操作: 相当于排队买票,先来的先买票,后来的后买票. 队列的应用: 打印队列:计算机打印多个文件的时候,需要排队打印:线程队列:当开启多线程时,当新开启的线程所需的资源不足时就先放入线程队列,等待CPU处理: 队列类的实现: 队列的实现和栈一样,有两种方案: 基于数组实现:基于链表实现: 队列的常见操作

  • TypeScript数据结构链表结构 LinkedList教程及面试

    目录 1. 认识链表 2. 实现链表结构的封装 2.1 基础框架 v1 版 2.2 添加 append 方法 v2 版 2.3 添加 traverse 方法 v3 版 2.4 添加 insert 方法 v4 版 2.5 添加 removeAt 方法 v5 版 2.6 添加 get 方法 v6 版 2.7 添加 getNode 方法 v7 版 2.8 添加 update 方法 v8 版 2.9 添加 indexOf 方法 v9 版 2.10 添加 remove 方法 v10 版 2.11 添加方法

  • PHP实现的链式队列结构示例

    本文实例讲述了PHP实现的链式队列结构.分享给大家供大家参考,具体如下: <?php header("Content-Type:text/html;charset=utf-8"); /** * 链式队列 */ class node{ public $nickname; public $next; } class queue { public $front;//头部 public $tail;//尾部 public $maxSize;//容量 public $next;//指针 p

  • Java定义队列结构,并实现入队、出队操作完整示例

    本文实例讲述了Java定义队列结构,并实现入队.出队操作.分享给大家供大家参考,具体如下: package com.example.demo; import java.util.ArrayList; public class Queue { ArrayList<Object> list = new ArrayList<>(); //入队 public void in(Object o) { list.add(o); } //出队 public Object out() { Obje

  • Go语言学习教程之结构体的示例详解

    目录 前言 可导出的标识符 嵌入字段 提升 标签 结构体与JSON相互转换 结构体转JSON JSON转结构体 练习代码步骤 前言 结构体是一个序列,包含一些被命名的元素,这些被命名的元素称为字段(field),每个字段有一个名字和一个类型. 结构体用得比较多的地方是声明与数据库交互时需要用到的Model类型,以及与JSON数据进行相互转换.(当然,项目中任何需要多种数据结构组合在一起使用的地方,都可以选择用结构体) 代码段1:声明一个待办事项的Model类型: type Todo struct

  • TypeScript类型系统自定义数据类型教程示例

    目录 TypeScript 类型系统和自定义数据类型 什么是类型系统 函数类型 类型别名 可选参数 默认参数 函数重载 接口类型 可选属性 只读属性 接口扩展 多重接口声明 接口的索引签名 用接口描述函数 类类型 implements关键字 类的静态端类型和实例端类型 将 this 作为类型 将 this 作为参数 枚举 枚举类型 枚举的成员类型 枚举的成员 字面量类型 联合类型 交叉类型 泛型 泛型函数 泛型接口 泛型类 在工厂函数中使用泛型 泛型约束 在泛型约束中使用类型参数 在泛型中使用条

  • TypeScript 基础数据结构哈希表 HashTable教程

    目录 前言 1. 哈希表介绍和特性 2. 哈希表的一些概念 3. 地址冲突解决方案 3.1 方案一:链地址法 3.2 方案二:开放地址法 4. 哈希函数代码实现 5. 哈希表封装 5.1 整体框架 v1 版 5.2 添加 put 方法 v2 版 5.3 添加 get 方法 v3 版 5.4 添加 delete 方法 v4 版 6. 哈希表的自动扩容 前言 哈希表是一种 非常重要的数据结构,几乎所有的编程语言都有 直接或者间接 的应用这种数据结构. 很多学习编程的人一直搞不懂哈希表到底是如何实现的

  • JS中的算法与数据结构之队列(Queue)实例详解

    本文实例讲述了JS中的算法与数据结构之队列(Queue).分享给大家供大家参考,具体如下: 队列(Queue) 我们之前说到了栈,它是一种比较高效的数据结构,遵循 先入后出(LIFO,last-in-first-out) 的原则.而今天我们要讨论的队列,它也是一种特殊的列表,它与栈不同的是, 队列只能在队尾插入元素,在队首删除元素,就像我们平时排队买票一样~ 队列用于存储按顺序排列的数据,遵循 先进先出(FIFO,First-In-First-Out) 的原则,也是计算机常用的一种数据结构,别用

随机推荐