第2章 线性结构

2.1 数组 (Array)

数组是一种非常基础且广泛支持的数据结构，在大多数编程语言中都有直接或类似的实现。因此数组结构不需要我们从零实现，只需要了解如何使用及对应特点。

2.1.1 线性结构的定义

线性结构（英文：Linear List）是由n（n≥0）个数据元素（结点）a[0]，a[1]，a[2]…，a[n-1]组成的有限序列。

线性结构的特性如下3点：

（1）数据元素的个数n定义为表的长度 = “list”.length() （“list”.length() = 0（表里没有一个元素）时称为空表）。

（2）将非空的线性表（n>=1）记作：（a[0]，a[1]，a[2]，…，a[n-1]）。

（3）数据元素a[i]（0≤i≤n-1）只是个抽象符号，其具体含义在不同情况下可以不同。

以上是维基百科对于线性结构的定义，是最严谨直接的说明方式。

在数据结构中，存在诸多结构，线性结构是数据结构中的较大分支。“线性结构”中的 “线性”，指数据元素之间排列得像一条线一样，想象一下日常生活中排成的一条直线队伍，队伍中除了第一个和最后一个人，每个人前面都有且仅有一个直接的前驱者，后面都有且仅有一个直接的后继者。这种“一个接一个”的、一对一的序列关系，就是“线性”最本质的特征。

因此在数据结构中，“线性”意味着数据元素之间存在 “一对一” 的逻辑关系。除了第一个元素，每个元素都有且仅有一个直接前驱；除了最后一个元素，每个元素都有且仅有一个直接后继。所有数据元素可以排列在一个单一的序列中，就像被串成一条线。

总结线性结构的如下3点核心特征：

（1）有序性：元素是按照某种顺序排列的，有头有尾，有明确的先后次序。

（2）唯一的前驱和后继：每个元素在序列中的位置是固定的，和它相邻的元素是确定的。

（3）遍历的单一路径：从头到尾（或从尾到头）遍历整个结构时，你只有一条路可走，没有分支，没有环路（除非是循环链表等特殊设计）。

在诸多数据结构与算法相关的文章或者课程中，看见或者听说过数组/链表结构是一种线性结构；栈/队列结构是一种受限的线性结构。

数组在内存空间中通常占据一段连续的内存，在这段连续的数组内存中可以存在多个且不同的元素，以有序的方式组织。链表在内存空间中不占据连续内存，以多块小内存的形式存在，每块小内存的内部存储一个元素以及指向下一节点（下一内存块）的指针信息。链表（单向）中每一块指向下一节点的信息都是没有回头路且单一指向的，线性地从头奔到尾。

因此数组与链表都是线性结构，不同之处在于内存中的表达形式是连贯还是分裂。

栈类似一端开口的桶，元素只能从顶部放入和取出，遵循后进先出的规则。队列类似单行管道，元素从尾部进入，从头部离开，遵循先进先出的规则。无论是栈还是队列，每次放入或者取出元素都只能单个放入取出，不能并列放入取出，每个元素最多只能拥有一个直接前驱与直接后继，是线性的表达方式。且由于栈与队列操作元素的放入取出都有所限制，需要遵循一定的规则（后进先出、先进先出），因此将栈与队列称为受限的线性结构。4类线性结构有序图如图2-1所示。

PS：栈与队列的受限是特性，不是缺陷，受限在特定场景具备更大的优势。

图2-1 4类线性结构有序图

主要的线性结构有数组、链表、栈、队列与字符串。在本章会学习数组、栈与队列，在第3章会学习链表。

2.1.2 数组的特性与内存模型

数组（Array）结构是一种重要的数据结构，几乎是每种编程语言都会提供的一种原生数据结构（语言自带的），并且我们可以借助于数组结构来实现其他的数据结构，例如栈（Stack）、队列（Queue）、堆（Heap）。

通常数组的内存是连续的，这更有利于内存寻址，所以数组在知道下标值的情况下，访问效率非常高。通过数组与链表比对说明数组在内存寻址的优势：

（1）数组：由于数组内存是连续的，所以数组的内存寻址可以依赖地址计算公式：元素内存地址 = 数组首地址 + 索引 × 每个元素占用的字节数。假设数组首地址为0x1000，每个元素占据4字节，现在需要访问arr[5]，arr[5] 的地址 = 0x1000 + 5 × 4 = 0x1000 + 20 = 0x1014。

PS：数组首地址是一个十六进制数，索引与元素大小是十进制数，需要偏移量计算。20的十六进制表示是0x14。

数组这个地址计算只涉及一次乘法和一次加法。无论数组有多大（是有1万个元素还是10亿个元素），这个计算步骤都是固定的，其时间复杂度是 O(1)，且CPU 和内存控制器对这种简单的算术运算有着极强的优化能力，可以在一个或几个时钟周期内完成。相比之下，从内存中读取数据本身所需的时间要比这个地址计算的时间长得多。

（2）链表：链表恰恰缺少这种“连续性”，由于链表的节点分散在内存的各个角落，要访问链表中第 i 个节点，CPU 没有直接的公式可以计算出它的地址，唯一的办法是从头节点开始，沿着 next 指针一个一个地遍历，直到第 i 个节点。这是一个 O(n) 的操作。

数组与链表的区别在于读取数据次数为O(1)与O(n)，而从内存中读取数据是主要的耗时操作。因此数组通过下标可以计算所需的元素内存地址，从而实现一次读取，这是数组访问效率非常高的原因。

数组与链表具备的优势不同，数组读取方便，但由于数组有序性特点（连续），每一块内存中都有对应元素，替换元素简单，而插入元素会导致后继所有元素都需要向后移动，产生大量数据搬迁的开销，因此数组插入数据不如链表方便。数据与链表的对比如图2-2所示。

图2-2 数组与链表对比

不同的数据结构运用的场景也不同，数据结构没有绝对的好坏，我们真正需要学习的，是在合适的场景下运用合适的数据结构。

早期的JavaScript有很多语言缺陷，那时候实现的数组实际是一个对象，下标被视为"字符串"属性名，其对应的内存不是连续的（类似链表的形式），因此读取性能较低。现代JavaScript引擎（如V8）已经进行了优化，当数组元素类型一致且连续时，引擎会使用连续的内存来存储数组，以提高性能。如果数组变得稀疏或者元素类型不同，引擎可能会切换到另一种表示方式（例如哈希表或链表式的结构）。关于稀疏数组处理方式与说明在《JavaScript高级编程权威指南》的23.4.1小节中有具体说明。

TypeScript中数组的各种用法，和JavaScript保持一致，不再详细讲解。MDN文档（Array）：Array - JavaScript | MDN。后续学习数组和链表的关系区别时，会通过大O表示法来分析数组操作元素的时间复杂度问题。

2.2 栈结构 (Stack)

栈是一种常见的数据结构， 并且在程序中的应用非常广泛。在2.1.2小节中了解数组是一种线性结构，并且可以在数组的任意位置插入和删除数据，但有些时候为了实现某些功能，我们必须对这种任意性加以限制，而栈与队列就是较为常见的受限的线性结构，我们先学习栈结构。

2.2.1 栈的特性与LIFO原则

栈结构每次放入与取出都只能作用于栈顶元素，即后进先出特性。放入与取出的过程被称为进栈（入栈、压栈）与出栈（退栈）。因为栈只能从栈顶一端弹出数据，所以栈底元素想弹出则需要满足栈底上方所有元素先行出栈并且无进栈的前置条件（即栈底成为栈顶）。前置条件即栈结构的受限特性，受限特性在特定场景下有独特的使用需求，因此受限特性并不归类于设计缺陷。

LIFO（last in first out）表示最后进入的元素， 第一个弹出栈空间。 类似于自动餐托盘， 最后放上的托盘， 往往先把拿出去使用。对表的一端进行插入和删除运算，这一端被称为栈顶，相对另一端被称为栈底。把新元素放到栈顶元素的上面。新元素会称为栈顶元素；把栈顶元素删除掉，相邻的元素会成为新的栈顶元素。因此栈顶元素与栈底元素并不具体指某一元素，而是位置上的概念。栈结构示意图如图2-3所示。

图2-3 栈结构示意图

生活中类似栈的如收实体邮件，从上往下依次处理这些邮件，最新到的邮件最先处理。这不允许改变邮件的处理次序，例如从最早到的或者最紧急的邮件开始处理，否则就不是栈结构，而是队列或者优先级队列结构。

了解栈的概念后，来完成一道栈结构的面试题：

题目：有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？

A：5、4、3、6、1、2。

B：4、5、3、2、1、6。

C：3、4、6、5、2、1。

D：2、3、4、1、5、6。

六个元素的顺序进栈，很容易想到1、2、3、4、5、6的出栈序列，但选项中并没有这一答案。1~6的出栈序列只是众多合理出栈序列的其中一种，我们不应该使用排除法一个个计算，因为排除法的效率过低。需要根据入栈与出栈的受限特性，来推断怎么样的逻辑是不合理的。

进栈与出栈不强制要求一次性进栈后再一次性出栈（这种做法只有一种结果），只规定进栈顺序需要按6到1的顺序。

正规做法（以A为例）：进栈6、5，出栈5；进栈4，出栈4；进栈3，出栈3；出栈6；进栈2、1，出栈1，出栈2。

快速做法（以A为例）：进栈写下，出栈删除，不合理的地方会自动冒出来（例如当你想删6，结果6不是栈顶时为不合理），多动笔，不空想。用笔或者键盘来模拟过程。

快速做法模拟：

65 => 进栈6、5。

6 => 出栈5。

64 => 进栈4。

6 => 出栈4。

63 => 进栈3。

6 => 出栈3。

21 => 出栈6，进栈2、1。

2 => 出栈1。

出栈2，清空。

快速做法类似于珠算的过程，完美利用栈结构的受限特性，只需要遵循后进先出的规则对最右侧内容进行增删，当运算熟练，可在几秒内得出结果，无需真正思考。

选项B：4、5、3、2、1、6。 模拟过程：进栈6、5、4，出栈4；出栈5；进栈3，出栈3；进栈2，出栈2；进栈1，出栈1；出栈6。合法。

选项C：3、4、6、5、2、1。 模拟过程：进栈6、5、4、3，出栈3；出栈4；此时栈顶为5，但出栈序列要求出栈6，而6在栈底，无法直接出栈，必须先出栈5。但出栈序列中6在5之前，因此不合法。

选项D：2、3、4、1、5、6。 模拟过程：进栈6、5、4、3、2，出栈2；出栈3；出栈4；进栈1，出栈1；出栈5；出栈6。合法。

2.2.2 栈结构的实现（基于数组）

在JavaScript/TypeScript中使用Stack（栈），往往会直接使用数组。数组与栈有所不同，如果想把数组当栈来使用，只需要避免在数组中去增删元素，永远只对数组最后一个元素进行操作。数组天生就拥有栈所需的方法，我们不需要改变数组本身，只是选择性地使用它的部分功能。

实现栈结构有以下2种常见方式：

（1）基于数组实现。

（2）基于链表实现。

链表也是一种数据结构，目前我们尚未学习，并且JavaScript中并没有自带链表结构，后续我们会在第3章从零实现链表结构，并对比数组与链表的区别。因此，我们此处实现的栈结构底层基于数组。

首先我们需要创建一个栈的类，用于封装栈相关的操作。后续需要使用栈时，就能够通过创建实例对象来复用栈结构。

▼
ts
复制代码
// 封装一个栈
class ArrayStack {
  // 定义一个数组/链表，用于存储数据
  private data: any[] = []
}

// 使用栈结构
const stack1 = new ArrayStack()

2.2.3 栈的常见操作方法

在栈中需要实现以下6点功能：

（1）定义一个数组，用于存储数据。

（2）实现push(element)方法：添加新元素到栈顶位置（进栈）。

（3）实现pop()方法：移除栈顶元素，同时返回被移除元素（出栈）。

（4）实现peek()方法：返回栈顶元素，不对栈做任何修改（不移除栈顶元素，仅返回栈顶元素信息）。

（5）实现isEmpty()方法：判断栈内元素是否为空，返回布尔值。

（6）实现size()方法：获取栈内元素个数，返回阿拉伯数字，与数组length属性类同。

使用数组存储元素，暂时将数组定义为any类型，后续采用泛型重构。目前完成最基础的栈结构模型，接下来在栈结构模型中实现栈所对应的方法。

▼
ts
复制代码
// 封装一个栈（第一版栈封装）
class ArrayStack {
  // 定义一个数组/链表, 用于存储元素
  private data: any[] = []

  // 实现栈中相关的操作方法
  // push(element)方法：添加新元素到栈顶位置（进栈）
  push(element: any): void {
    this.data.push(element)
  }

  // pop()方法：移除栈顶元素，同时返回被移除元素（出栈）
  pop(): any {
    return this.data.pop()
  }

  // peek()方法: 返回栈顶元素，不对栈做任何修改（不移除栈顶元素，仅返回栈顶元素信息）
  peek(): any {
    return this.data.at(-1)
  }

  // isEmpty()方法：判断栈内元素是否为空，返回布尔值
  isEmpty(): boolean {
    return this.data.length === 0
  }

  // size()方法：获取栈内元素个数，返回阿拉伯数字
  size(): number {
    return this.data.length
  }
}


// 创建ArrayStack的实例对象
const stack1 = new ArrayStack()
stack1.push("coderwhy")
stack1.push("XiaoYu")
stack1.push("数据结构与算法")

console.log(stack1.peek())
console.log(stack1.pop())
console.log(stack1.pop())
console.log(stack1.pop())

console.log(stack1.isEmpty())
console.log(stack1.size())

export { }

实现push(element)、pop()、peek()、isEmpty()，size()方法较为简单，很多都是数组本身所拥有的方法。但正如2.2.2小节开头所说数组天生就拥有栈所需的方法，我们封装栈最主要的目的是做出限制，令ArrayStack类的实例对象只能使用封装中的方法，而不能直接操作ArrayStack类中的data数组。

注意：TypeScript代码不能在浏览器与Node.js中运行，需要全局安装ts-node。

▼
ts
复制代码
// 全局安装ts-node
pnpm install -g ts-node
// 检查是否安装成功 or 之前是否安装过
ts-node --version
//运行代码
ts-node xxx.ts

且由于peek()方法中使用ES13中的Array.prototype.at()方法，因此需要将在tsconfig.json文件中更新lib和target配置。

▼
ts
复制代码
{
  "compilerOptions": {
    "target": "ES2022",
    "lib": ["ES2022", "DOM"]
  }
}

完成栈的类封装后，我们对栈进行重构，使用泛型替代any实现类型约束。

目前ArrayStack类的私密属性data与各个方法采用any定义，而any实际无约束力，过多的any做法会使TypeScript与JavaScript区分不开。

栈结构-优化1：在使用栈方法，即进栈/出栈/获取元素时，使用泛型得知元素的具体类型，从而获取更友好的代码提示。

TypeScript泛型语法为<T>，T可以理解为Type（类型）的缩写，但同时也可以是任何有效的标识符，使用方式类似参数，T是"形参"，在使用时传入具体类型"实参"。我们将第一版栈封装的any类型全部替换为泛型，将传入与传出的类型交由使用者决定。但泛型在作用于pop()与peek()实例方法时出现类型报错，如图2-4所示。

因为栈内部是有可能空的，而Array.prototype.pop()实例方法从空数组中删除元素时返回undefined。any类型包括了undefined，而泛型T是"某种具体的类型"，默认不包含undefined。Array.prototype.at()实例方法的返回值也是类似原因，如果index < -array.length或index >= array.length，则总是返回undefined，而不会尝试访问相应的属性。

图2-4 pop()与peek()实例方法的类型报错

pop()与peek()实例方法的类型报错使用联合类型 T | undefined 处理解决。

▼
ts
复制代码
// 封装一个栈
class ArrayStack<T> {
  // 定义一个数组/链表, 用于存储元素
  private data: T[] = []

  // 实现栈中相关的操作方法
  // push(element)方法：添加新元素到栈顶位置（进栈）
  push(element: T): void {
    this.data.push(element)
  }

  // pop()方法：移除栈顶元素，同时返回被移除元素（出栈）
  pop(): T | undefined {
    return this.data.pop()
  }

  // peek()方法: 返回栈顶元素，不对栈做任何修改（不移除栈顶元素，仅返回栈顶元素信息）
  peek(): T | undefined {
    return this.data.at(-1)
  }

  // isEmpty()方法：判断栈内元素是否为空，返回布尔值
  isEmpty(): boolean {
    return this.data.length === 0
  }

  // size()方法：获取栈内元素个数，返回阿拉伯数字
  size(): number {
    return this.data.length
  }
}

// 创建ArrayStack的实例对象
const stack1 = new ArrayStack<String>()
stack1.push("coderwhy")
stack1.push("XiaoYu")
stack1.push("数据结构与算法")

由于栈结构除了使用数组实现，还可以通过链表或者其余方式实现。无论通过哪种方式实现栈结构，都需要满足栈结构所必要的5个实例方法以及对应的数据存储模式。如果需要多次通过不同方式实现栈结构，那每一次实现栈结构都需要回顾所需实现的实例方法等，这会有所不便。

▼
ts
复制代码
// 使用链表实现栈结构
class LinkedStack<T> {
  push(element: T) { }
  pop() { }
  peek() { }
  isEmpty() { }
  size() { }
}

栈结构-优化2：对于多次实现栈结构的不便问题，可以使用TypeScript定义接口来解决。定义接口及使用如下3步骤：

（1）创建IStack.ts文件用于存放接口代码。

（2）编写接口代码并导出。

（3）导入需实现栈结构的文件，并通过implements使用接口。

使用接口后，实现的栈结构若未满足接口所需的方法定义需求，则栈结构报错。

▼
ts
复制代码
// IStack.ts文件
// 定义栈的结构
interface IStack<T> {
  push(element: T): void
  pop(): T | undefined
  peek(): T | undefined
  isEmpty(): boolean
  size(): number
}
// 导出接口
export default IStack

// 需实现栈结构的文件
import IStack from "./IStack"
class ArrayStack<T> implements IStack<T> {
  // ...ArrayStack内部实例方法省略
}

export default ArrayStack

TypeScript的接口（interface）和继承（class extends）是不同的概念，最核心的理念区分为：

• 接口关注"做什么"，即只有声明无实现。
• 继承关注"如何做"。

2.2.4 栈的面试题：十进制转二进制

我们已经学会了如何使用Stack类，现在就用它解决一些计算机科学中的问题。

人类习惯使用十进制，所以我们在编程、输入数据、显示数据时，通常使用十进制。但在计算机科学中，二进制非常重要，因为计算机里的所有内容都由二进制数字表示（0与1）。如果没有十进制与二进制相互转换的能力，与计算机交流就会很得困难。因此将各类进制（十六、十、八进制）转为二进制是计算机科学和编程领域中经常使用的算法，至今为止仍有很多网站专门帮助开发者进行进制转换，如图2-5所示。

图2-5 十进制转二进制网站

2.2.4小节的面试题就需要我们利用栈结构来实现十进制转二进制，要将十进制转为二进制，可将该十进制数字和2整除（二进制为满二进一），直到结果是0为止。

将十进制数字35转换为二进制数字，过程示例如下：

（1）35除2，余1，结17。

（2）17除2，余1，结8。

（3）8除2，余0，结4。

（4）4除2，余0，结2。

（5）2除2，余0，结1。

（6）1除2，余1，结0。

以上整除示例一共分六步，则十进制转为二进制为6位数，位数具体数字为步骤逆序的余数，因此十进制35等同二进制100011。

通过该十进制35转换示例的位数具体数字为步骤逆序的余数信息，可利用栈结构的后进先出规则，将计算的余数结果进栈，当结为0视为计算结束，将栈内数据出栈，出栈组成结果即为二进制结果。

涉及计算的部分，可翻阅MDN文档中的Math内置对象中的静态方法。让我们自己来设计十进制转二进制的函数方法，传入十进制信息，返回传入十进制所对应的二进制结果。设计过程需分4步：

（1）获取传入十进制信息。

（2）对十进制信息整除2，获取整除余数填入栈，获取整除结果继续整除2，当整除结果为0结束运算。

（3）将栈结构内容弹出并拼接。

（4）返回拼接结果。

返回值以字符串形式表达来避免二进制结果自动转换为十进制表达。

▼
ts
复制代码
function decimalToBinary(decimal: number): string {
  // 1.创建一个栈, 用于存放余数
  const stack = new ArrayStack<number>()

  // 2.使用循环: 
  // while: 不确定次数, 只知道循环结束跳转 
  // for: 知道循环的次数时
  while (decimal > 0) { // 整除结果为0结束运算
    // 对十进制信息整除2
    const result = decimal % 2
    // 获取整除余数填入栈
    stack.push(result)
    // 获取整除结果继续整除2
    decimal = Math.floor(decimal / 2)
  }

  // 3.所有的余数都已经放在stack中, 以此取出即可
  let binary = ''
  while (!stack.isEmpty()) { // 栈空结束拼接
    binary += stack.pop() // 将栈结构内容弹出并拼接
  }

  return binary // 返回拼接结果
}

console.log(decimalToBinary(35))

除栈结构的写法之外，还可以采用递归与Math内置对象的静态方法来简化步骤。由于递归会执行到整除2的最深层再从最深处往外依次返回结果，因此可以直接得出进制结果，而无需利用栈的特性。

▼
ts
复制代码
function decimalToBinary(decimal: number): string {
  return decimal === 0 ? '0' : decimalToBinary(Math.floor(decimal / 2)) + (decimal % 2);
}

console.log(decimalToBinary(35)); // "0100011"

在实际使用中，可利用高度内聚的Array.prototype.toString()实例方法来快速完成进制转换（该实例方法封装了多种进制转换方式，进制转换取决于传入的数字，当数字为2即二进制转换，数字为8即八进制转换），但Array.prototype.toString()实例方法的核心算法依旧是重复除法取余 + 逆序排列。除此之外还有高性能的位运算做法，因此实现进制转换的方式有多种，可在课余时间再额外探索。

▼
ts
复制代码
const decimalToBinary = (n: number): string => n.toString(2);
console.log(decimalToBinary(35)); // "100011"

2.2.5 栈的面试题：有效括号匹配

题目：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

来源：LeetCode 20：20. 有效的括号 - 力扣（LeetCode）

有效字符串需满足以下3点：

（1）左括号必须用相同类型的右括号闭合。

（2）左括号必须以正确的顺序闭合。

（3）每个右括号都有一个对应的相同类型的左括号。

一句话概括：同类型括号按左右顺序成对且正确嵌套即视为有效字符串。有效括号匹配示例如图2-6所示。

图2-6 有效括号匹配示例

做好题目的前提是足够了解题目，总结有效括号匹配示例的规律，可见有效匹配有三种情况：简单配对、多种括号独立配对，正确的嵌套配对。该题目考验的核心能力为以下3点：

（1）理解能力。

（2）解析能力。

（3）对数据结构的掌握力。

算法题目更多考验的是面试者在面对题目时的思考逻辑、表达力、理解力以及解析力等多维度能力，因此在学习数据结构与算法的过程中，更应该侧重锻炼这些能力，而非直接拿取他人优解来照抄。

▼
ts
复制代码
"()" // 简单配对
"()[]{}" // 多种括号独立配对  
"([{}])" // 正确嵌套：最后开的括号最先闭合

在概括总结中体现理解题目的能力；在有效括号匹配示例中体现解析规则的能力；那对数据结构的掌握力体现在哪里？这是一道关于栈的面试题，我们要将栈的特性与该题目联系在一起。

正确嵌套：最后开的括号最先闭合。因此最后的右括号必先最先匹配同类型左括号，依次类推。由于左括号先，所以左括号判断条件在前。根据以上规则总结，可通过栈结构的最后进栈的元素最先出栈特性来匹配。

题目完成如下4步骤：

（1）获取传入字符串内容并遍历。

（2）对遍历元素判断左括号，是左括号则进栈一个同类型右括号。

（3）对遍历元素判断右括号，右括号与栈内弹出内容匹配，若不匹配则返回false结束循环，若匹配则继续后续判断。

（4）当栈为空时，结束判断。

▼
ts
复制代码
import { ArrayStack } from "./ArrayStack"
function isValid(s: string): Boolean {
  // 创建栈结构
  const stack = new ArrayStack<string>()
  // 获取传入字符串内容并遍历。
  for (let i = 0; i < s.length; i++) {
    // 对遍历元素判断左括号，是左括号则进栈一个同类型右括号
    if (s[i] === '(' || s[i] === '{' || s[i] === '[') {
      if (s[i] === '(') {
        stack.push(')')
      }
      if (s[i] === '{') {
        stack.push('}')
      }
      if (s[i] === '[') {
        stack.push(']')
      }
    } else {
      // 对遍历元素判断右括号，右括号与栈内弹出内容匹配，若不匹配则返回false结束循环，若匹配则继续后续判断。
      if (s[i] !== stack.pop()) {
        return false
      }
    }
  }
  // 当栈为空时，结束判断。
  return stack.isEmpty()
}
// 判断示例
console.log(isValid("()"));
console.log(isValid("()[]{}"));
console.log(isValid("(]"));
console.log(isValid("([])"));
console.log(isValid("([)]"));

大多数情况下，if语句没有switch语句性能高，但if语句可读性高。在后续实现数据结构，若条件数量多，可更多的使用switch语句，性能更高。

▼
ts
复制代码
for (let i = 0; i < s.length; i++) {
  const c = s[i]
  switch (c) {
    case "(":
      stack.push(")")
      break
    case "{":
      stack.push("}")
      break
    case "[":
      stack.push("]")
      break
    default:
      if (c !== stack.pop()) return false
      break
  }
}

在实际编写中，可采用Map结构作为左右同类型括号的映射关系，在编写代码时会更为精简。可在课余时间扩展更多写法，在LeetCode中测试性能指标等等。

▼
ts
复制代码
import { ArrayStack } from "./ArrayStack"
function isValid(s: string): boolean {
   const stack = new ArrayStack<string>()
  const map: { [key: string]: string } = {
    ')': '(',
    '}': '{',
    ']': '['
  };

  for (const char of s) {
    if (!map[char]) {
      // 左括号入栈
      stack.push(char);
    } else {
      // 右括号：检查栈顶是否匹配
      if (stack.pop() !== map[char]) return false;
    }
  }

  return stack.isEmpty()
}

通过十进制转二进制以及有效括号匹配这两道面试题，我们利用栈结构的受限特性来完成需求，更深刻的认识受限特性并非缺陷，而是精心设计的约束，在某些场景下更高效可靠。栈结构通过以下3点体现了"做一件事并做好"的Unix哲学：

（1）单一职责：只管理顺序访问。

（2）最小接口：减少认知负荷。

（3）可预测性：行为完全确定。

2.3 队列结构 (Queue)

我们在2.2小节学习栈结构这一受限的线性结构，并且基于该受限的数据结构解决某些特定问题，从而实现特别效果。接下来我们再来学习另外一个受限的数据结构：队列。

2.3.1 队列的特性与FIFO原则

队列(Queue)，它是一种受限的线性表，先进先出（FIFO First In First Out），队列受限之处在于以下两点：

（1）只允许在队列的前端（front）进行删除操作（出队）。

（2）只允许在队列的后端（rear）进行插入操作（入队）。

队列结构的受限操作（删除与插入）如图2-7所示。

图2-7 队列结构的受限操作

生活中的队列例如排队购票，先到窗口的先买票；餐厅取号，按号码顺序叫号就餐；打印机任务，先发送的文档先打印；高速公路收费站，先进入的车道先通过；客服热线，先拨打的电话先接通。生活中的队列通常体现的是先来先服务的公平规则，确保资源按到达次序分配，避免混乱与争执。

开发中的队列例如线程队列，为了让任务可以并行处理，通常会开启多个线程，但是我们不能让大量的线程同时运行处理任务 (占用过多的资源)。此刻如果有需要开启线程处理任务的情况，我们就会使用线程队列。线程队列用于控制并发线程数量，通过有序调度避免资源过载：当需要并行处理任务时，线程队列按提交顺序依次启动线程执行任务，既实现了并行计算的优势，又防止了同时运行过多线程导致的系统资源耗尽问题。

队列还有很多其余应用，后续的很多算法中也会用到队列（例如第5章的二叉树层序遍历）。

2.3.2 队列的实现（基于数组）

队列的实现与栈相同，有以下两种方案：

（1）基于数组实现。

（2）基于链表实现。

队列基于链表实现会更好，因为在链表尾部添加节点（入队）和在链表头部移除节点（出队），无需元素搬移，操作直接完成。数组出队需要移动所有后续元素，队列中的出队后续元素越多，造成的性能影响越明显，在2.1.2小节中有详细说明。

接下来我们需要创建一个类来表示一个队列，目前尚未学习链表，因此队列仍先基于数组实现。

▼
js
复制代码
class ArrayQueue <T> {
  // 内部数据通过数组（链表）保存
  private data: T[] : [];
}

2.3.3 队列的常见操作方法

队列与栈类似，通过一些方法来实现队列的功能特性，队列应实现以下5个常见操作方法：

（1）实现enqueue(element) 方法：向队列尾部添加一个（或多个）新的项。

（2）实现dequeue()方法：移除队列的第一（即排在队列最前面的）项，并返回被移除的元素。

（3）实现front/peek()方法：返回队列中第一个元素信息——最先被添加，也将是最先被移除的元素。队列不做任何变动（不移除元素，只返回元素信息——与Stack类的peek()方法非常类似）。

（4）实现isEmpty()方法：如果队列中不包含任何元素，返回true，否则返回false。

（5）实现size()方法：返回队列包含的元素个数，与数组的length属性类似。

队列与栈的操作方法极其类似，最大的不同在于移除元素部分，队列采用dequeue()方法移除排在队列最前面的项。dequeue()方法复用Array.prototype.shift()实例方法，即从数组中删除第一个元素，并返回该元素的值，此方法更改数组的长度。

▼
ts
复制代码
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]  // 使用Array.prototype.at()实例方法也能做到同样效果
  }

  isEmpty(): boolean {
    return this.data.length === 0
  }

  size(): number {
    return this.data.length
  }
}

export default ArrayQueue

队列最重要的是enqueue(element)入队方法与dequeue()出队方法，因此可对队列实行接口约束。

▼
ts
复制代码
// IQueue.ts文件
import IList from "../types/IList"

interface IQueue<T> extends IList<T> {
  // 入队方法
  enqueue(element: T): void
  // 出队方法
  dequeue(): T | undefined
}

export default IQueue

对于队列与栈共通的方法，可进一步分层抽象为IList接口，然后由各自对应的Queue、Stack等接口继承。该分层做法会使结构定义与来源更为清晰。

▼
ts
复制代码
// /types/IList.ts文件
export default interface IList<T> {
  // peek
  peek(): T | undefined
  // 判断是否为空
  isEmpty(): boolean
  // 元素的个数
  size(): number
}

在使用ArrayQueue类中的size()实例方法获取元素个数时，所对照的是数组的length属性。将实例方法获取与属性获取等同起来是略显割裂的，因为获取元素个数应该是属性而非行为，方法调用通常暗示有计算或操作而非只读行为，因此获取元素个数采用实例方法调用就不太合适。可在IList接口与ArrayQueue类中，在size()实例方法前加上get访问器，则size()实例方法使用时不能方法调用，而是像属性一样访问，提供了更好的语义表达和类型安全。

▼
ts
复制代码
// IList接口
get size(): number
// ArrayQueue类
get size(): number {
  return this.data.length
}

//调用队列的size属性
const queue = new ArrayQueue<string>()
console.log(queue.size)

2.3.4 队列的面试题：击鼓传花

击鼓传花是一个常见的面试算法题，原规则：班级中玩一个游戏，所有学生围成一圈，从某位同学手里开始向旁边的同学传一束花。此时某个人(例如班长)，在击鼓，鼓声停下的一颗，花落在谁手里，谁就出来表演节目。

修改后的编程版规则：几个朋友一起玩一个游戏，围成一圈，开始数数，数到某个数字的人自动淘汰。最后剩下的人获得胜利，请问最后剩下的人，他最初的位置在哪?

击鼓传花若基于队列实现，封装对应函数需要基于以下2个条件：

（1）参数：所有参与人的名字以及对应的位置数字，淘汰规则。

（2）结果：最终剩余一人的姓名位置。

击鼓传花每一次数数，前端都有一个人出队，若鼓声未停，则出队的人从后端重新入队，前端再出队一人，依次循环，直到鼓声停止，出队的人不再重新入队。队列的击鼓传花如图2-8所示。

图2-8 队列的击鼓传花

击鼓传花的游戏想要进行下去，需要把控好淘汰节奏以及终止条件，即每次淘汰的鼓点停止时机节点，以及当最终剩余一人游戏结束。最终剩余一人的判定条件为queue.size为1时，但淘汰的节奏则可以多变，使用者可以根据自身实际情况选择适当的游戏节奏点进行暂停，以下代码示例采用固定的淘汰节奏，即每次都在固定次数后淘汰一人。

游戏的具体轮数为游戏人数-1，即多轮游戏。而多轮游戏可采用for语句或switch语句来循环游戏轮数，在2.2.5小节中有探索两者的区别，在此选择switch语句来循环游戏轮数。一开始将所有姓名入队的操作采用for...of语句或者Array.prototype.forEach()实例方法都行，但在初次学习数据结构与算法时，采用可读性更好的for...of语句会更好，当对数据结构与算法和TypeScript都足够熟悉后，可自由采用更简介明了的高阶函数写法。

最后让我们来复习一遍击鼓传花的函数逻辑为如下5步：

（1）创建击鼓传花函数，传入所有参与人的名字以及对应位置数字的数组和淘汰规则（每轮淘汰第num个位置的人）。

（2）在击鼓传花函数中创建队列结构并将所有参与人入队。

（3）利用淘汰规则淘汰至最后一人后终止击鼓传花游戏。

（4）从仅剩最后一人的队列中取出最后一人的姓名leftName常量。

（5）在一开始传入的所有参与人的数组中找到leftName常量的下标进行返回，展现给用户数组下标加1的位置。

▼
ts
复制代码
import ArrayQueue from './Queue'

function hotPotato(names: string[], num: number): number {
  // 传入的参与人数组内，至少长度为1（即击鼓传花游戏参与人数至少1人）
  if (names.length === 0) return -1

  // 1.创建队列结构
  const queue = new ArrayQueue<string>()

  // 2.将所有的name入队操作
  // forEach写法：names.forEach(name => queue.enqueue(name))
  for (const name of names) {
    queue.enqueue(name)
  }

  // 3.淘汰的规则
  while (queue.size() > 1) {
    // 1/2不淘汰
    for (let i = 1; i < num; i++) {
      // 先出队
      const name = queue.dequeue()
      // 鼓声没停则重新入队
      if (name) queue.enqueue(name)
    }
    // 鼓声停止则真正出队淘汰
    queue.dequeue()
  }

  // 4.取出最后一个人
  const leftName = queue.dequeue()!
  const index = names.indexOf(leftName)

  return index
}

const leftIndex = hotPotato(["coderwhy", "xiaoyu", "coderwhy666", "xiaoyu2002","why", "javaScript", "TypeScript", "data"], 4)
console.log(`获胜者在原始列表中的索引: ${leftIndex}`)
console.log(`从用户角度看是第 ${leftIndex + 1} 个人`)

Array.prototype.indexOf()实例方法用于返回数组中第一次出现给定元素的下标。而数组下标是从0开始，普通人理解的开始是"第1个人"而不是"第0个人"，因此最终展现位置时需要数组下标加1。

2.3.5 队列的面试题：约瑟夫环问题

阿桥问题（有时也称为约瑟夫斯置换），是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。公元1世纪，犹太历史学家弗拉维奥·约瑟夫和40名战友被罗马军队围困在洞穴中。他们面临选择：是被俘受辱还是集体自杀？

这些人最终决定自杀，并以抽签的方式决定谁杀掉谁——他们围成一个圆圈，按照固定规则依次处决同伴：

（1）从某个人开始报数。

（2）每数到指定数字就处决当前的人。

（3）然后从下一个人重新开始报数。

（4）循环直到只剩最后一人。

据说约瑟夫通过数学计算，提前找到了那个能活到最后的安全位置，从而保住了自己的性命。这就是著名的约瑟夫环问题——在n个人围成的圈中，从第k个人开始报数，数到m的人出局，求最后幸存者的原始位置。约瑟夫环问题可以用动态规划或者队列来解决，队列相对动态规划更方便实现，但消耗性能更多。动态规划会在第11章学习，在此处我们采用队列实现，与击鼓传花面试题类似。

题目需求：0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

▼
ts
复制代码
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

此时如果队列中的数字数量过大，不断的从队列前端进行出队操作和后端进行入队操作，对数组而言非常消耗性能。因此可在课下额外探索约瑟夫环的其余做法，例如链表、动态规划等。

▼
ts
复制代码
// 动态规划做法
function lastRemaining(n: number, m: number) {
  let position = 0;

  for (let i = 2; i <= n; i++) {
      position = (position + m) % i;
  }
  return position;
}

console.log(lastRemaining(5, 3)) // 3
console.log(lastRemaining(10, 17)) // 2

在本章线性结构中学习了数组结构、栈结构以及队列结构。下一章会学习链表结构。链表虽然也是线性结构，但实现方式（链式存储）与数组（顺序存储）有本质区别，且内容较多，因此我们放在第3章单独讲解。