TypeScript 数据结构与算法库

一个 TypeScript 实现的数据结构与算法库，包含高性能的最大栈（MaxStack）数据结构和多种排序算法。

安装

npm install @zhoujiale.zerg/maxstack-ts

快速开始

MaxStack 使用示例

import { MaxStack } from '@zhoujiale.zerg/maxstack-ts';

const stack = new MaxStack();

// 基本操作
stack.push(5);
stack.push(1);
stack.push(5);

console.log(stack.top());      // 5 (栈顶元素)
console.log(stack.peekMax());  // 5 (最大元素)
console.log(stack.popMax());   // 5 (弹出最大元素)
console.log(stack.top());      // 1 (新的栈顶)

排序算法使用示例

import { bubbleSort, insertionSort, selectionSort } from '@zhoujiale.zerg/maxstack-ts';

const numbers = [5, 3, 8, 4, 2];

// 冒泡排序
const bubbleSorted = bubbleSort(numbers);
console.log(bubbleSorted);  // [2, 3, 4, 5, 8]

// 插入排序
const insertionSorted = insertionSort(numbers);
console.log(insertionSorted);  // [2, 3, 4, 5, 8]

// 选择排序
const selectionSorted = selectionSort(numbers);
console.log(selectionSorted);  // [2, 3, 4, 5, 8]

// 降序排序（所有排序算法都支持）
const descendingOrder = bubbleSort(numbers, false);
console.log(descendingOrder);  // [8, 5, 4, 3, 2]

最大栈 (MaxStack) 特性

最大栈是一个支持以下操作的数据结构：

• push(x) - 将元素 x 压入栈顶
• pop() - 弹出并返回栈顶元素
• top() - 返回栈顶元素（不弹出）
• peekMax() - 返回栈中最大元素（不弹出）
• popMax() - 弹出并返回栈中最大元素
• isEmpty() - 检查栈是否为空
• size() - 返回栈中元素数量

时间复杂度

• 所有操作的时间复杂度都是 O(log n)
• 使用了堆和延迟删除技术来实现高效操作

排序算法

本库提供了三种常用的排序算法实现：

冒泡排序 (Bubble Sort)

• 时间复杂度：O(n²)
• 空间复杂度：O(1)
• 稳定性：稳定
• 特点：实现简单，对于小数据集或接近有序的数据效率较高

插入排序 (Insertion Sort)

• 时间复杂度：O(n²)
• 空间复杂度：O(1)
• 稳定性：稳定
• 特点：对于小数据集和部分有序数据效率较高，实现简单

选择排序 (Selection Sort)

• 时间复杂度：O(n²)
• 空间复杂度：O(1)
• 稳定性：不稳定
• 特点：交换次数少，但比较次数固定

MaxStack API 文档

构造函数

const stack = new MaxStack();

方法

| 方法 | 描述 | 时间复杂度 | | --------------------- | ---------------------------- | ---------- | | push(x: number) | 将元素 x 压入栈顶 | O(log n) | | pop(): number | 弹出并返回栈顶元素 | O(log n) | | top(): number | 返回栈顶元素（不弹出） | O(log n) | | peekMax(): number | 返回栈中最大元素（不弹出） | O(log n) | | popMax(): number | 弹出并返回栈中最大元素 | O(log n) | | isEmpty(): boolean | 检查栈是否为空 | O(log n) | | size(): number | 返回栈中元素数量 | O(log n) | | toArray(): number[] | 返回栈的数组表示（用于调试） | O(n) |

示例

import { MaxStack } from '@zhoujiale.zerg/maxstack-ts';

const stack = new MaxStack();

// 添加元素
stack.push(3);
stack.push(1);
stack.push(4);
stack.push(1);
stack.push(5);

console.log(stack.size());     // 5
console.log(stack.peekMax());  // 5
console.log(stack.top());      // 5

// 弹出最大元素
console.log(stack.popMax());   // 5
console.log(stack.top());      // 1
console.log(stack.peekMax());  // 4

// 正常栈操作
console.log(stack.pop());      // 1
console.log(stack.top());      // 4

技术特性

• ✅ TypeScript 支持
• ✅ Node.js 类型定义
• ✅ 源码映射 (Source Maps)
• ✅ 声明文件生成
• ✅ 严格类型检查
• ✅ 完整的单元测试
• ✅ 性能测试