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 队列结构的资料请关注我们其它相关文章!