前端算法之TypeScript包含min函数的栈实例详解

前端算法之TypeScript包含min函数的栈实例详解

一、前言

本篇文章将介绍一种栈（Stack）的实现，同时在栈中加入一个min函数，用来返回栈中最小的值。

栈是一种线性数据结构，具有“后进先出”（LIFO）的特性，它只允许在表的一端进行插入和删除操作。这个在实际生活中比较类似于一个弹簧式的球点笔，通过一个“中心轴”的作用，可以让笔芯向上或向下转动。

有很多不同的编程语言可以用来实现这个Stack栈，本文主要采用TypeScript来进行实现。

二、栈Stack的实现

通过一个简单的类来定义一个Stack类，主要包括以下几个方法：

• push(item: T)：向栈中添加新的元素；
• pop(): T | undefined：移除栈顶的元素；
• peek(): T | undefined：返回栈顶的元素，不对栈做修改；
• size(): number：返回栈中元素的个数；
• isEmpty(): boolean：判断栈是否为空。

TypeScript中定义Stack具体实现代码：

class Stack<T> {
    private items: T[] = [];

    push(item: T) {
        this.items.push(item);
    }

    pop(): T | undefined {
        return this.items.pop();
    }

    peek(): T | undefined {
        return this.items[this.items.length - 1];
    }

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

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

三、包含min函数的Stack

在上面的基础上，实现一个新的Stack类，用来完成包含min函数的要求。

在Stack中添加一个新的成员变量minItems，用来记录每次push操作后Stack中的最小值缓存，减少查找最小值的开销。同时重写push方法，在每次push的时候，保存当前Stack中最小值。

具体实现代码如下：

class MinStack<T extends number> {
    private items: T[] = [];
    private minItems: T[] = [];

    push(item: T) {
        this.items.push(item);
        const min = this.minItems[this.minItems.length - 1];
        if (min === undefined || item <= min) {
            this.minItems.push(item);
        }
    }

    pop(): T | undefined {
        const item = this.items.pop();
        const min = this.minItems[this.minItems.length - 1];
        if (item === min) {
            this.minItems.pop();
        }
        return item;
    }

    getMin(): T | undefined {
        return this.minItems[this.minItems.length - 1];
    }

    peek(): T | undefined {
        return this.items[this.items.length - 1];
    }

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

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

• push方法：每次向Stack中添加元素的时候，保存当前Stack中最小值;
• pop方法：移除栈顶的元素，并且根据最小值进行更新;
• getMin方法：返回当前Stack中最小值。

四、使用示例

通过以下两个示例，其中一个是正常的取出栈顶元素；第二个例子是在pop出栈顶元素的时候，同时也pop出最小值。

const minStack = new MinStack<number>();
minStack.push(3);
minStack.push(2);
minStack.push(4);
console.log(minStack.getMin());// 2

console.log(minStack.pop());// 4
console.log(minStack.getMin());// 2
console.log(minStack.pop());// 2
console.log(minStack.getMin());// 3

const minStack2 = new MinStack<number>();
minStack2.push(3);
minStack2.push(2);
minStack2.push(4);
console.log(minStack2.pop());// 4
console.log(minStack2.pop());// 2
console.log(minStack2.pop());// 3
console.log(minStack2.getMin());// undefined

通过以上两个示例，我们可以看到：

第一个示例中，先给MinStack插入了3、2、4三个数，利用getMin方法分别输出了最小数2。
后续通过pop方法，弹出了4、2两个数，分别输出了正确的数字，并且在每次pop结束后，利用getMin方法返回正确的最小值，证明该Stack是正确的。

第二个示例中，先给MinStack2插入了3、2、4三个数，在依次进行pop操作，同时发现当前Stack中最小值也被pop出，最后导致getMin方法返回undefined。

五、结语

本文详细阐述了如何在TypeScript中实现一个包含min函数的栈，让开发者不仅可以实现基础的栈操作，还可以更加便捷地获取栈中最小值。同时对于学习和理解数据结构也有很大的帮助。