本文详细介绍了如何使用迭代堆栈（stack）方法，从复杂的深度嵌套对象数组中提取所有具有特定type属性的对象。该教程通过清晰的算法步骤和typescript代码示例，演示了如何有效遍历多层数据结构，避免了递归可能导致的栈溢出问题，适用于处理层级不定的数据。
在现代Web应用开发中，我们经常需要处理复杂的数据结构，其中包含多层嵌套的对象和数组。例如，一个UI组件树、一个文档对象模型（DOM）的表示，或者像本例中所示的具有items子属性的“组”结构。当我们需要从这种深度嵌套的数据中筛选出所有满足特定条件的元素时，传统的数组方法（如filter）往往力不从心，因为它只能处理当前层级的元素。
本教程将提供一种健壮且高效的方法来解决这个问题：使用迭代式的深度优先遍历（DFS）结合堆栈（Stack）数据结构。这种方法能够确保遍历到所有层级的元素，并且避免了递归深度过大可能导致的栈溢出问题。
挑战：深度嵌套数据中的特定元素提取
假设我们有一个JSON数组，其中每个对象可能包含一个type属性，并且一些对象还可能包含一个items数组，而items数组中的元素又可能遵循相同的结构，形成一个深层嵌套的树状结构。我们的目标是从这个复杂的结构中找出所有type属性值为 "text" 的对象。
以下是一个示例数据结构：
[
{
"index": 3,
"uid": "188960ecb29_00562b0c",
"type": "group",
"items": [
{
"uid": "18895f59b1a_2c5a5c7a",
"type": "text", // 这是一个目标对象
"text": ["abc"]
},
{
"index": 1,
"type": "group",
"items": [
{
"uid": "18895ecc7c7_2d5440b6",
"type": "text", // 另一个目标对象
"text": ["xyz"]
}
]
}
]
}
// ... 更多类似的嵌套结构
]解决方案：迭代式堆栈遍历算法
为了遍历所有层级的元素，我们可以采用类似深度优先搜索（DFS）的策略，但通过显式管理一个堆栈来避免函数调用栈的限制。
算法步骤
- 初始化结果数组： 创建一个空数组，用于存储所有符合条件的对象。
- 初始化堆栈： 创建一个堆栈，并将输入数组中的所有顶层元素压入堆栈。
-
循环遍历： 当堆栈不为空时，重复以下操作：
- 弹出元素： 从堆栈顶部弹出一个当前元素。
- 条件检查： 检查当前元素的 type 属性是否与目标类型（例如 "text"）匹配。如果匹配，则将此元素添加到结果数组中。
- 压入子元素： 如果当前元素包含一个 items 属性（表示它有子元素），则将 items 数组中的所有子元素压入堆栈。这样可以确保在下一轮循环中，这些子元素也会被处理。
- 返回结果： 循环结束后，返回包含所有符合条件对象的结果数组。
TypeScript 实现示例
下面是基于上述算法的 TypeScript 实现代码。为了方便演示，我们假设 data 是一个全局或传入的数组变量。
// 假设这是我们的输入数据结构
interface NestedItem {
uid: string;
type: string;
items?: NestedItem[]; // 子元素可能也是NestedItem类型
[key: string]: any; // 允许其他任意属性
}
const data: NestedItem[] = [
{
"index": 3,
"uid": "188960ecb29_00562b0c",
"x": 18.65,
"y": 44.14,
"width": 180.14,
"height": 53.33,
"items": [
{
"uid": "18895f59b1a_2c5a5c7a",
"locked": false,
"rotation": 0,
"type": "text", // 目标对象
"text": ["abc"],
"x": 154.37,
"y": 0,
"width": 25.76,
"height": 20.90
},
{
"index": 1,
"uid": "1889607cfdf_091e59ca",
"x": 0,
"y": 32.43,
"width": 22.17,
"height": 20.90,
"items": [
{
"uid": "18895ecc7c7_2d5440b6",
"locked": false,
"rotation": 0,
"type": "text", // 目标对象
"text": ["xyz"],
"x": 0,
"y": 0,
"width": 22.17,
"height": 20.90
}
],
"type": "group",
"rotation": 0
},
{
"index": 2,
"uid": "188960e945c_35ab99fa",
"x": 44.10,
"y": 15.56,
"width": 56.72,
"height": 35.17,
"items": [
{
"uid": "18896072844_1298562b",
"locked": false,
"rotation": 0,
"type": "text", // 目标对象
"text": ["group"],
"x": 15.56,
"y": 14.27,
"width": 41.15,
"height": 20.90
},
{
"index": 3,
"uid": "188960e5f49_2341c362",
"x": 0,
"y": 0,
"width": 29.80,
"height": 20.90,
"items": [
{
"uid": "188958badfe_3a73220b",
"locked": false,
"rotation": 0,
"type": "text", // 目标对象
"text": ["Text"],
"x": 0,
"y": 0,
"width": 29.80,
"height": 20.90
}
],
"type": "group",
"rotation": 0
}
],
"type": "group",
"rotation": 0
}
],
"type": "group",
"rotation": 0
}
];
/**
* 从深度嵌套的数组中提取所有指定类型的对象。
* @param targetType 要查找的对象类型字符串。
* @param initialData 初始的嵌套数据数组。
* @returns 包含所有匹配对象的数组。
*/
const getSpecificType = (targetType: string, initialData: NestedItem[]): NestedItem[] => {
const result: NestedItem[] = []; // 存储结果的数组
// 使用展开运算符将初始数据复制到堆栈中，避免修改原始数据
const stack: NestedItem[] = [...initialData];
// 当堆栈不为空时，持续处理
while (stack.length > 0) {
const current = stack.pop(); // 弹出堆栈顶部的元素
// 检查弹出的元素是否有效，防止undefined或null
if (!current) {
continue;
}
// 如果当前元素的type属性与目标类型匹配，则将其添加到结果数组
if (current.type === targetType) {
result.push(current);
}
// 如果当前元素有子元素（即有items属性），则将这些子元素压入堆栈
// 使用 ?? [] 确保即使items为null或undefined也能安全操作
if (current.items && current.items.length > 0) {
stack.push(...current.items);
}
}
return result; // 返回所有找到的匹配对象
};
// 调用函数并打印结果
const textObjects = getSpecificType("text", data);
console.log(textObjects);
/* 预期输出示例 (部分):
[
{ uid: '18895f59b1a_2c5a5c7a', locked: false, rotation: 0, type: 'text', text: [ 'abc' ], ... },
{ uid: '18895ecc7c7_2d5440b6', locked: false, rotation: 0, type: 'text', text: [ 'xyz' ], ... },
{ uid: '18896072844_1298562b', locked: false, rotation: 0, type: 'text', text: [ 'group' ], ... },
{ uid: '188958badfe_3a73220b', locked: false, rotation: 0, type: 'text', text: [ 'Text' ], ... }
]
*/你可以在 [TypeScript Playground](https://www.php.cn/link/603a99469d867c85df8c8e940f3ed965
