typescript模拟实现特殊数据

双向链表(DoublyLinkedList): 头插入/尾插入/头删除/尾删除/指定插入/指定删除/获取指定项

class ListNode<T> {
    public val: T;
    public prev: ListNode<T> | null = null;
    public next: ListNode<T> | null = null;
    constructor(val: T) {
        this.val = val;
    }
}
class DoublyLinkedList<T> {
    private head: ListNode<T> | null = null;
    private tail: ListNode<T> | null = null;
    private size: number = 0;
    
    /** 获取链表长度 */
    public getSize(): number {
        return this.size;
    }
    
    /** 判断链表是否为空 */
    public isEmpty(): boolean {
        return this.size === 0;
    }
    
    /** 在链表头部插入节点 */
    public addFirst(val: T): void {
        const newNode = new ListNode(val);
        if (this.isEmpty()) {
            this.head = this.tail = newNode;
        } else {
            newNode.next = this.head;
            this.head!.prev = newNode;
            this.head = newNode;
        }
        this.size++;
    }
    
    /** 在链表尾部插入节点 */
    public addLast(val: T): void {
        const newNode = new ListNode(val);

        if (this.isEmpty()) {
            this.head = this.tail = newNode;
        } else {
            newNode.prev = this.tail;
            this.tail!.next = newNode;
            this.tail = newNode;
        }
        this.size++;
    }
    
    /** 在指定索引位置插入节点 */
    public insert(index: number, val: T): void {
        if (index < 0 || index > this.size) {
            throw new Error("Index out of bounds");
        }
        if (index === 0) {
            this.addFirst(val);
            return;
        }
        if (index === this.size) {
            this.addLast(val);
            return;
        }
        const newNode = new ListNode(val);
        let current = this.head;
        // 找到要插入位置的前一个节点
        for (let i = 0; i < index - 1; i++) {
            current = current!.next;
        }
        newNode.prev = current;
        newNode.next = current!.next;
        current!.next!.prev = newNode;
        current!.next = newNode;
        this.size++;
    }
    
    /** 删除头部节点 */
    public removeFirst(): T | null {
        if (this.isEmpty()) return null;

        const val = this.head!.val;
        this.head = this.head!.next;

        if (this.head) {
            this.head.prev = null;
        } else {
            this.tail = null; // 链表变空
        }
        this.size--;
        return val;
    }

    /** 删除尾部节点 */
    public removeLast(): T | null {
        if (this.isEmpty()) return null;
        if (this.size === 1) return this.removeFirst();
        const val = this.tail!.val;
        this.tail = this.tail!.prev;
        this.tail!.next = null;
        this.size--;
        return val;
    }

    /** 删除指定索引的节点 */
    public remove(index: number): T | null {
        if (index < 0 || index >= this.size) {
            throw new Error("Index out of bounds");
        }
        if (index === 0) return this.removeFirst();
        if (index === this.size - 1) return this.removeLast();

        let current = this.head;
        for (let i = 0; i < index; i++) {
            current = current!.next;
        }
        const val = current!.val;
        current!.prev!.next = current!.next;
        current!.next!.prev = current!.prev;
        this.size--;
        return val;
    }

    /** 获取指定索引的节点值 */
    public get(index: number): T | null {
        if (index < 0 || index >= this.size) {
            throw new Error("Index out of bounds");
        }
        let current = this.head;
        for (let i = 0; i < index; i++) {
            current = current!.next;
        }
        return current!.val;
    }

    /** 查找元素是否在链表中 */
    public contains(val: T): boolean {
        let current = this.head;
        while (current) {
            if (current.val === val) return true;
            current = current.next;
        }
        return false;
    }

    /** 打印链表（从头到尾） */
    public printForward(): void {
        let current = this.head;
        const result: T[] = [];
        while (current) {
            result.push(current.val);
            current = current.next;
        }
        console.log("→", result.join(" → "), "→ null");
    }

    /** 打印链表（从尾到头） */
    public printBackward(): void {
        let current = this.tail;
        const result: T[] = [];
        while (current) {
            result.push(current.val);
            current = current.prev;
        }
        console.log("←", result.join(" ← "), "← null");
    }

    /** 清空链表 */
    public clear(): void {
        this.head = this.tail = null;
        this.size = 0;
    }
}

队列(Queue)

class Node<T> {
    public value: T;
    public next: Node<T> | null = null;

    constructor(value: T) {
        this.value = value;
    }
}

class Queue0<T> {
    private head: Node<T> | null = null;
    private tail: Node<T> | null = null;
    private length: number = 0;

    // 入队（从尾部添加）
    enqueue(value: T): void {
        const newNode = new Node(value);
        if (this.isEmpty()) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            this.tail!.next = newNode;
            this.tail = newNode;
        }
        this.length++;
    }

    // 出队（从头部移除）
    dequeue(): T | undefined {
        if (this.isEmpty()) return undefined;
        const value = this.head!.value;
        this.head = this.head!.next;
        if (this.head === null) {
            this.tail = null;
        }
        this.length--;
        return value;
    }

    peek(): T | undefined {
        return this.head?.value;
    }

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

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

    clear(): void {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
}

环形缓冲区(RingBuffer)

// 首尾插入移除的时间复杂度都是O(1)

class RingBuffer<T> {
  private buffer: T[];
  private capacity: number;
  private head: number = 0;   // 读指针（下一个要读取的位置）
  private tail: number = 0;   // 写指针（下一个要写入的位置）
  private count: number = 0;  // 当前元素数量

  constructor(capacity: number) {
    if (capacity <= 0) {
      throw new Error("容量必须大于 0");
    }
    this.capacity = capacity;
    this.buffer = new Array(capacity);
  }

  /** 添加元素（写入） */
  push(item: T): boolean {
    if (this.isFull()) {
      return false; // 满了，返回 false（或者你可以选择覆盖旧数据）
    }
    this.buffer[this.tail] = item;
    //  上面full检查保证还有空位   %取余确保指针指向下一位,如果满了会重新回到0   比如01234 环形则变成了0123401234 就像旋转寿司 核心就是指针循环
    this.tail = (this.tail + 1) % this.capacity;  
    this.count++;
    return true;
  }

  /** 取出元素（读取并移除） */
  pop(): T | null {
    if (this.isEmpty()) {
      return null;
    }
    const item = this.buffer[this.head];
    this.head = (this.head + 1) % this.capacity;
    this.count--;
    return item;
  }

  /** 查看下一个元素，但不移除 */
  peek(): T | null {
    if (this.isEmpty()) {
      return null;
    }
    return this.buffer[this.head];
  }

  /** 是否为空 */
  isEmpty(): boolean {
    return this.count === 0;
  }

  /** 是否已满 */
  isFull(): boolean {
    return this.count === this.capacity;
  }

  /** 当前元素数量 */
  size(): number {
    return this.count;
  }

  /** 清空缓冲区 */
  clear(): void {
    this.head = 0;
    this.tail = 0;
    this.count = 0;
    // 可选：把数组清空
    // this.buffer.fill(undefined as T);
  }

  /** 转为普通数组（用于调试） */
  toArray(): T[] {
    const result: T[] = [];
    let idx = this.head;
    for (let i = 0; i < this.count; i++) {
      result.push(this.buffer[idx]);
      idx = (idx + 1) % this.capacity;
    }
    return result;
  }
}

栈(Stack)

class Node<T> {
    public value: T;
    public next: Node<T> | null = null;
    constructor(value: T) {
        this.value = value;
    }
}

export default class Stack<T> {
    private top: Node<T> | null = null;
    public length: number = 0;

    // 入栈
    push(value: T): void {
        const newNode = new Node(value);
        newNode.next = this.top;
        this.top = newNode;
        this.length++;
    }

    // 出栈
    pop(): T | undefined {
        if (this.isEmpty()) return undefined;

        const value = this.top!.value;
        this.top = this.top!.next;
        this.length--;
        return value;
    }

    // 查看栈顶
    peek(): T | undefined {
        return this.top?.value;
    }
    isEmpty(): boolean {
        return this.length === 0;
    }
    size(): number {
        return this.length;
    }
    clear(): void {
        this.top = null;
        this.length = 0;
    }
}

堆(Heap): 二叉堆是完全二叉树

/*   最小堆（MinHeap）：pop() 永远返回并删除 当前堆中最小的元素（堆顶）。
最大堆（MaxHeap）：pop() 永远返回并删除 当前堆中最大的元素（堆顶）。
*/
class BinaryHeap<T> {
    private heap: T[] = [];
    private compare: (a: T, b: T) => number;
    constructor(compareFn?: (a: T, b: T) => number) {
        // 默认最小堆
        this.compare = compareFn || ((a, b) => (a as any) - (b as any));
    }

    /** 获取堆的大小 */
    public size(): number {
        return this.heap.length;
    }

    /** 判断堆是否为空 */
    public isEmpty(): boolean {
        return this.heap.length === 0;
    }

    /** 获取堆顶元素（不移除） */
    public peek(): T | undefined {
        return this.heap[0];
    }

    /** 插入元素 */
    public push(value: T): void {
        this.heap.push(value);
        this.bubbleUp(this.heap.length - 1);
    }

    /** 移除并返回堆顶元素 */
    public pop(): T | undefined {
        if (this.isEmpty()) return undefined;
        const root = this.heap[0];
        const last = this.heap.pop()!;
        if (!this.isEmpty()) {
            this.heap[0] = last;
            this.bubbleDown(0);
        }
        return root;
    }

    /** 获取父节点索引 */
    public parentIndex(index: number): number {
        return Math.floor((index - 1) / 2);
    }

    /** 获取左子节点索引 */
    public leftChildIndex(index: number): number {
        return 2 * index + 1;
    }

    /** 获取右子节点索引 */
    public rightChildIndex(index: number): number {
        return 2 * index + 2;
    }

    /** 获取父节点值 */
    public parent(index: number): T | undefined {
        const pIndex = this.parentIndex(index);
        return pIndex >= 0 ? this.heap[pIndex] : undefined;
    }

    /** 获取左子节点值 */
    public leftChild(index: number): T | undefined {
        const lIndex = this.leftChildIndex(index);
        return lIndex < this.size() ? this.heap[lIndex] : undefined;
    }

    /** 获取右子节点值 */
    public rightChild(index: number): T | undefined {
        const rIndex = this.rightChildIndex(index);
        return rIndex < this.size() ? this.heap[rIndex] : undefined;
    }

    /** 判断某个索引是否有父节点 */
    public hasParent(index: number): boolean {
        return this.parentIndex(index) >= 0;
    }

    /** 判断某个索引是否有左子节点 */
    public hasLeftChild(index: number): boolean {
        return this.leftChildIndex(index) < this.size();
    }

    /** 判断某个索引是否有右子节点 */
    public hasRightChild(index: number): boolean {
        return this.rightChildIndex(index) < this.size();
    }

    /** 获取某个索引的节点值（安全访问） */
    public get(index: number): T | undefined {
        return index >= 0 && index < this.size() ? this.heap[index] : undefined;
    }

    /** 将数组转换为堆（原地建堆，O(n)） */
    public buildHeap(arr: T[]): void {
        this.heap = [...arr];
        for (let i = Math.floor(this.heap.length / 2) - 1; i >= 0; i--) {
            this.bubbleDown(i);
        }
    }

    /** 清空堆 */
    public clear(): void {
        this.heap = [];
    }

    /** 返回堆的副本（用于调试或打印） */
    public toArray(): T[] {
        return [...this.heap];
    }

    // ==================== 内部方法 ====================
//  插入元素到堆最后一项 结构正常 但可能会破坏堆性质  需要上浮 将值放入合适的位置
    private bubbleUp(index: number): void {
        while (this.hasParent(index)) {
            const parentIdx = this.parentIndex(index);
            if (this.compare(this.heap[index], this.heap[parentIdx]) >= 0) {
                break;
            }
            this.swap(index, parentIdx);
            index = parentIdx;
        }
    }
    //  当我们 移除堆顶元素（pop）时，会把数组最后一个元素拿到根节点位置, 需要下沉恢复堆的性质
// 递归终止条件：到达根节点（索引0）或已经满足堆性质
    private bubbleDown(index: number): void {
        while (this.hasLeftChild(index)) {  // 因为堆始终是从左到右填充的,有左子叶才会有右子叶
            let smallest = index;
            const left = this.leftChildIndex(index);
            const right = this.rightChildIndex(index);
            if (this.hasLeftChild(index) && this.compare(this.heap[left], this.heap[smallest]) < 0) {
                smallest = left;
            }
            if (this.hasRightChild(index) && this.compare(this.heap[right], this.heap[smallest]) < 0) {
                smallest = right;
            }
            if (smallest === index) break;
            this.swap(index, smallest);
            index = smallest;
        }
    }
    
    //   上浮和下沉的递归版本
	private bubbleUpRecursive(index: number): void {
        if(index <= 0) return  //  // 递归终止条件：到达根节点（索引0）或已经满足堆性质
        const parentIdx = this.parentIndex(index);
        if (this.compare(this.heap[index], this.heap[parentIdx]) >= 0) return
        this.swap(index, parentIdx);
        this.bubbleUpRecursive(parentIdx)
    }
    
    private swap(i: number, j: number): void {
        [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
    }
}

// 最小堆（默认）
class MinHeap<T> extends BinaryHeap<T> {
    constructor() {
        super((a, b) => (a as any) - (b as any));
    }
}

// 最大堆
class MaxHeap<T> extends BinaryHeap<T> {
    constructor() {
        super((a, b) => (b as any) - (a as any));
    }
}