TypeScript_队列结构-链表

队列

队列（Queue），它是一种受限的线性表，先进先出（FIFO First In First Out）

• 受限之处在于它只允许在队列的前端（front）进行删除操作
• 而在队列的后端（rear）进行插入操作

队列

• 有五份文档需要打印，这些文档会按照次序放入到打印队列中
• 打印机会依次从队列中取出文档，优先放入的文档，优先被取出，并且对该文档进行打印
• 以此类推，直到队列中不再有新的文档

线程队列:

• 在开发中，为了让任务可以并行处理，通常会开启多个线程
• 但是，我们不能让大量的线程同时运行处理任务。（占用过多的资源）
• 这个时候，如果有需要开启线程处理任务的情况，我们就会使用线程队列
• 线程队列会依照次序来启动线程，并且处理对应的任务

当然队列还有很多其他应用，我们后续的很多算法中也会用到队列（比如二叉树的层序遍历）

队列操作

• enqueue(element)：向队列尾部添加一个（或多个）新的项
• dequeue()：移除队列的第一（即排在队列最前面的）项，并返回被移除的元素
• front/peek()：返回队列中第一个元素————最先被添加，也将是最先被移除的元素。队列不做任何变动 （不移除元素，只返回元素信息一一与 Stack 类的 peek 方法非常类似）
• isEmpty()：如果队列中不包含任何元素，返回 true，否则返回 false
• size()：返回队列包含的元素个数，与数组的 length 属性类似

实现队列

队列的实现和栈一样，有两种方案：

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

import IQueue from './IQueue'class ArrayQueue<T> implements IQueue<T> {// 内部是通过数组保存private data: T[] = []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}
}export default ArrayQueue

泛型

interface IList<T> {peek(): T | undefinedisEmpty(): booleansize(): number
}
interface IQueue<T> extends IList<T> {enqueue(element: T): voiddequeue(): T | undefined
}

击鼓传花

原游戏规则

• 班级中玩一个游戏，所有学生围成一圈，从某位同学手里开始向旁边的同学传一束花
• 这个时候某个人（比如班长），在击鼓，鼓声停下的一颗，花落在谁手里，谁就出来表演节目

修改游戏规则

• 我们来修改一下这个游戏规则
• 几个朋友一起玩一个游戏，围成一圈，开始数数，数到某个数字的人自动淘汰
• 最后剩下的这个人会获得胜利，请问最后剩下的是原来在哪一个位置上的人

封装一个基于队列的函数

• 参数：所有参与人的姓名，基于的数字口结果：最终剩下的一人的姓名

function hotPotato(names: string[], num: number) {if (names.length === 0) return -1// 1.创建队列结构const queue = new ArrayQueue<string>()// 2.将所有的name入队操作for (const name of names) {queue.enqueue(name)}// 3.淘汰规则while (queue.size() > 1) {for (let i = 1; i < num; i++) {const name = queue.dequeue()if (name) queue.enqueue(name)}queue.dequeue()}return queue.dequeue()
}

约瑟夫环问题

阿桥问题（有时也称为约瑟夫斯置换），是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环

• 人们站在一个等待被处决的圈子里
• 计数从圆圈中的指定点开始，并沿指定方向围绕圆圈进行
• 在跳过指定数量的人之后，处刑下一个人
• 对剩下的人重复该过程，从下一个人开始，朝同一方向跳过相同数量的人，直到只剩下一个人，并被释放
• 在给定数量的情况下，站在第几个位置可以避免被处决?

这个问题是以弗拉维奥·约瑟夫命名的，他是1世纪的一名犹太历史学家口

• 他在自己的日记中写道，他和他的40个战友被罗马军队包围在洞中
• 他们讨论是自杀还是被俘，最终决定自杀，并以抽签的方式决定谁杀掉谁

剑指 Offer 62. 圆圈中最后剩下的数字

0,1,···,n-1 这 n 个数字排成一个圆圈，从数字 0 开始，每次从这个圆圈里删除第 m 个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字

例如，0、1、2、3、4 这 5 个数字组成一个圆圈，从数字 0 开始每次删除第 3 个数字，则删除的前 4 个数字依次是 2、0、4、1，因此最后剩下的数字是 3

import ArrayQueue from './queue'function lastRemaining(n: number, m: number) {// 1.创建队列const queue = new ArrayQueue<number>()// 2.将所有的数字加入队列中for (let i = 0; i < n; i++) {queue.enqueue(i)}// 3.判断队列中是否还有数字while (queue.size() > 1) {for (let i = 1; i < m; i++) {queue.enqueue(queue.dequeue()!)}queue.dequeue()}return queue.dequeue()
}console.log(lastRemaining(5, 3)) // 3
console.log(lastRemaining(10, 17)) // 2

动态规划

function lastRemaining(n: number, m: number) {let position = 0for (let i = 2; i <= n; i++) {position = (position + m) % i}return position
}

链表

链表与数组

链表和数组一样，可以用于存储一系列的元素，但是链表和数组的实现机制完全不同

数组有很多缺点:

• 数组的创建通常需要申请一段 连续的内存空间（一整块的内存），并且大小是固定的（大多数编程语言数组都是固定的），所以当当前数组 不能满足容量需求 时，需要 扩容。(一般情况下是申请一个更大的数组，比如 2 倍。然后将原数组中的元素复制过去)
• 而且在 数组开头或中间位置插入数据的成本很高，需要 进行大量元素的位移
• 尽管 JavaScript 的 Array 底层可以帮我们做这些事，但背后的原理依然是这样

要存储多个元素，另外一个选择就是链表

• 但不同于数组，链表中的元素在内存中不必是连续的空间
• 链表的每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（有些语言称为指针或者链接）组成

相对于数组，链表有一些优点:

• 内存空间不是必须连续的
  • 可以充分利用计算机的内存，实现灵活的内存动态管理口
• 链表不必在创建时就 确定大小，并且大小可以 无限的延伸 下去口
• 链表在 插入和删除 数据时，时间复杂度 可以达到 O(1)
  • 相对数组效率高很多

相对于数组，链表有一些缺点:

• 链表访问任何一个位置的元素时，都需要 从头开始访问。(无法跳过第一个元素访问任何一个元素)
• 无法通过下标直接访问元素，需要从头一个个访问，直到找到对应的元素

链表

什么是链表呢?

• 其实上面我们已经简单的提过了链表的结构，我们这里更加详细的分析一下
• 链表类似于火车：有一个火车头，火车头会连接一个节点，节点上有乘客（类似于数据），并且这个节点会连接下一个节点，以此类推

实现链表

• 封装一个 Node 类，用于封装每一个节点上的信息 (包括值和指向下一个节点的引用)，它是一个泛型类
• 封装一个 LinkedList 类，用于表示我们的链表结构。(和 Java 中的链表同名，不同 Java 中的这个类是一个双向链表)
• 链表中我们保存两个属性，一个是链表的长度，一个是链表中第一个节点

class Node<T> {value: Tnext: Node<T> | null = nullconstructor(value: T) {this.value = value}
}class LinkedList<T> {private head: Node<T> | null = nullprivate size: number = 0get length() {return this.size}
}

链表操作

• append(element)：向链表尾部添加一个新的项
• insert(position，element)：向链表的特定位置插入一个新的项
• get(position)：获取对应位置的元素indexOf(element): 返回元素在链表中的索引。如果链表中没有该元素则返回 -1
• update(position，element)：修改某个位置的元素
• removeAt(position)：从链表的特定位置移除一项
• remove(element)：从链表中移除一项
• isEmpty()：如果链表中不包含任何元素，返回 true，如果链表长度大于 0 则返回 false
• size()：返回链表包含的元素个数。与数组的 length 属性类似

向链表尾部追加数据可能有两种情况

• 链表本身为空，新添加的数据时唯一的节点
• 链表不为空，需要向其他节点后面追加节点

class Node<T> {value: Tnext: Node<T> | null = nullconstructor(value: T) {this.value = value}
}class LinkedList<T> {private head: Node<T> | null = nullprivate size: number = 0get length() {return this.size}// 根据position获取到当前的节点（不是节点的value，而是获取节点）private getNode(position: number): Node<T> | null {let index = 0let current = this.headwhile (index++ < position && current) {current = current.next}return current}append(value: T) {// 1.根据value创建一个新及诶单const newNode = new Node(value)// 2.判断this.heade是否为nullif (!this.head) {this.head = newNode} else {let current = this.headwhile (current.next) {current = current.next}current.next = newNode}this.size++}traverse() {const values: T[] = []let current = this.headwhile (current) {values.push(current.value)current = current.next}console.log(values.join('->'))}insert(value: T, position: number): boolean {// 1.越界的判断if (position < 0 || position > this.size) return false// 2.根据value创建新的节点const newNode = new Node(value)// 3.判断是否需要插入头部if (position === 0) {// 新节点next指向头部节点、头部newNode.next = this.headthis.head = newNode} else {const previous = this.getNode(position - 1)newNode.next = previous?.next ?? nullprevious!.next = newNode}this.size++return true}removeAt(position: number): T | null {// 1.越界的判断if (position < 0 || position >= this.size) return null// 2.判断是否是删除第一个节点let current = this.headif (position === 0) {this.head = current?.next ?? null} else {const previous = this.getNode(position - 1)previous!.next = previous?.next?.next ?? null}this.size--return current?.value ?? null}get(position: number): T | null {// 1.越界的判断if (position < 0 || position >= this.size) return null// 2.查找元素，并且返回元素return this.getNode(position)?.value ?? null}update(value: T, position: number): boolean {if (position < 0 || position >= this.size) return falseconst currentNode = this.getNode(position)// 获取对应位置的节点，直接更新即可currentNode!.value = valuereturn true}indexOf(value: T): number {let current = this.headlet index = 0while (current) {if (current.value === value) {return index}current = current.nextindex++}return -1}remove(value: T): T | null {const index = this.indexOf(value)return this.removeAt(index)}isEmpty() {return this.size === 0}
}

设计链表

707. 设计链表

你可以选择使用单链表或者双链表，设计并实现自己的链表

单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用

如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始

实现 MyLinkedList 类：

• MyLinkedList() 初始化 MyLinkedList 对象
• int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1
• void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点
• void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素
• void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中
• void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点

抽离接口方法

interface IList<T> {peek(): T | undefinedisEmpty(): booleansize(): number
}interface ILinkedList<T> extends IList<T> {append(value: T): voidtraverse(): voidinsert(value: T, position: number): booleanget(position: number): T | nullupdate(value: T, position: number): booleanindexOf(value: T): numberremove(value: T): T | null
}

删除链表中的节点

237. 删除链表中的节点

有一个单链表的 head，我们想删除它其中的一个节点 node

给你一个需要删除的节点 node 。你将 无法访问 第一个节点 head

链表的所有值都是 唯一的，并且保证给定的节点 node 不是链表中的最后一个节点

删除给定的节点。注意，删除节点并不是指从内存中删除它。这里的意思是：

• 给定节点的值不应该存在于链表中
• 链表中的节点数应该减少 1
• node 前面的所有值顺序相同
• node 后面的所有值顺序相同

class ListNode {val: numbernext: ListNode | nullconstructor(val?: number, next?: ListNode | null) {this.val = val === undefined ? 0 : valthis.next = next === undefined ? null : next}
}function deleteNode(node: ListNode | null): void {node!.val = node!.next!.valnode!.next = node!.next!.next
}

反转链表

206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表

利用栈结构解决

function reverseList(head: ListNode | null): ListNode | null {if (head === null) return nullif (head.next === null) return headconst stack: ListNode[] = []let current: ListNode | null = headwhile (current) {stack.push(current)current = current.next}let newHead: ListNode = stack.pop()!let newHeadCurrent = newHeadwhile (stack.length) {const node = stack.pop()!newHeadCurrent.next = nodenewHeadCurrent = newHeadCurrent.next}// 注意：获取到最后一个节点时，一定要将节点的 next 置为 nullnewHeadCurrent.next = nullreturn newHead
}const node1 = new ListNode(1)
node1.next = new ListNode(2)
node1.next.next = new ListNode(3)
const newHead = reverseList(node1)
let current = newHead
while (current) {console.log(current.val)current = current.next
}

非递归方式

1. 让 current 指向下一个节点

   • 目的：保留着下一个节点的引用，可以拿到，并且不会销毁

2. 改变 head 当前指向的节点，指向 newHead

   • 对于第一个节点来说，指向 newHead 就是指向 null

3. 让 newHead 指向 head 节点

   • 目的是下一次遍历时，第二步操作，可以让下一个节点指向第一个节点

4. 让 head 移向下一个节点，指向 current

function reverseList(head: ListNode | null): ListNode | null {if (head === null || head.next === null) return headlet newHead: ListNode | null = nullwhile (head) {let current: ListNode | null = head.nexthead.next = newHeadnewHead = headhead = current}return newHead
}

递归方式

• 第一次进入 const newHead 下面的代码是倒数第二个节点，因为倒数第一个节点的 next 为 null

function reverseList(head: ListNode | null): ListNode | null {if (head === null || head.next === null) return headconst newHead = reverseList(head.next)head.next.next = headhead.next = nullreturn newHead
}