TypeScript算法题实战——栈与队列篇(栈和队列的实现,括号表达式,逆波兰表达式)

举报
中杯可乐多加冰 发表于 2022/11/22 16:11:29 2022/11/22
【摘要】 栈和队列是数据结构中极为重要的基础,栈和队列都是一种线性表, 和链表顺序表相同, 但栈和队列各自具有各自的特性, 所以是一种特殊的线性表。队列是先进先出,栈是先进后出。本系列博文将通过一些力扣算法题目学习TypeScirpt,这篇将以栈和队列为主题边学习TypeScipt边实战算法。(部分算法思想参考于程序员Carl:代码随想录)首先,TS里是没有栈、没有队列这些数据结构的,只能使用数组代替...

栈和队列是数据结构中极为重要的基础,栈和队列都是一种线性表, 和链表顺序表相同, 但栈和队列各自具有各自的特性, 所以是一种特殊的线性表。队列是先进先出,栈是先进后出。

本系列博文将通过一些力扣算法题目学习TypeScirpt,这篇将以栈和队列为主题边学习TypeScipt边实战算法。(部分算法思想参考于程序员Carl:代码随想录
首先,TS里是没有栈、没有队列这些数据结构的,只能使用数组代替,数组在实现栈或者队列时可以调用以下:

  • pop(): 从数组中删除最后一个元素,并返回该元素的值,改变原数组。
  • push(): 将一个或多个元素添加到数组的末尾,并返回该数组的新长度,改变原数组。
  • shift(): 从数组中删除第一个元素,并返回该元素的值,改变原数组。
  • unshift(): 将一个或多个元素添加到数组的开头,并返回该数组的新长度,,改变原数组。

零、TS实现栈和队列功能

0.1、实现栈

栈的核心思想为后进先出(LIFO),那么我们可以用数组来描述栈。

一个栈都需要具备哪些功能:
入栈,添加一个新元素至栈顶(数组的末尾)。
出栈,将栈顶的元素移除并返回被移除的元素。
获取栈顶元素,获取当前栈顶元素返回。
判断栈是否为空,判断栈(数组)内是否有数据。
清空栈,移除栈内所有的元素。
获取栈大小,返回栈里的元素个数。
输出栈内数据,将栈中的所有元素以字符串的形式返回。

思路:

入栈(push),可以使用数组的push方法直接往数组的末尾添加元素。
出栈(pop),可以使用数组的pop方法直接移除栈中的元素,该方法会返回当前被移除的元素。
栈顶元素(peek),可以通过数组的长度-1获取到数组中的最后一个元素。
栈是否为空(isEmpty),可以通过判断数组的长度是否为0来实现。
清空栈(clear),可以将数组直接赋值为空或者调用出栈方法直至栈中的数据为空。 栈大小(size),可以返回数组的长度。
输出栈内数据,可以调用数组的toString方法将数组转换为字符串。

class MyStack {
  private items: any[];
  constructor() {
    this.items = [];
  }
  // 入栈
  push(item: any) {
    this.items.push(item);
  }
  // 出栈
  pop() {
    return this.items.pop();
  }
  // 返回栈顶元素
  peek() {
    return this.items[this.items.length - 1];
  }
  // 判断栈是否为空
  isEmpty() {
    return this.items.length === 0;
  }
  // 清空栈栈内元素
  clear() {
    this.items = [];
  }
  // 获取栈内元素数量
  size(): number {
    return this.items.length;
  }
  // 将栈内元素转为字符串
  toString() {
    return this.items.toString();
  }
}

一、用栈实现队列

1.1、题目描述

题目链接:https://leetcode.cn/problems/implement-queue-using-stacks/
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty):

实现 MyQueue 类:
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空,返回 true;否则,返回 false

1.2、示例

![在这里插入图片描述](https://img-blog.csdnimg.cn/c84c9d22e13d4d3d96dd5c3850ca12bb.png#pic_center =x320)

1.3、题解

使用两个栈实现队列,一个A栈负责进队列,一个B栈负责出队列,当要进队列时很简单,压入A栈就好了;当要出队列时,如果B栈为空,就需要先把A栈挨个弹出,并且将弹出的元素挨个压到B栈,这样两次的先入后出就形成了先入先出的队列。

class MyQueue {
    private stackIn: number[];
    private stackOut: number[];
    constructor() {
        this.stackIn = [];
        this.stackOut = [];
    }

    push(x: number): void {
        this.stackIn.push(x);
    }

    pop(): number {
        if(this.stackOut.length === 0){
            while(this.stackIn.length > 0){
                this.stackOut.push(this.stackIn.pop());
            }
        }
        return this.stackOut.pop();
    }

    peek(): number { // 返回队列开头的元素 指的是只得到开头的元素但是不弹出,这里可以先弹出再放进去
        let temp: number = this.pop();
        this.stackOut.push(temp);
        return temp;
    }

    empty(): boolean {
        return this.stackIn.length === 0 && this.stackOut.length === 0;
    }
}
/**
 * Your MyQueue object will be instantiated and called as such:
 * var obj = new MyQueue()
 * obj.push(x)
 * var param_2 = obj.pop()
 * var param_3 = obj.peek()
 * var param_4 = obj.empty()
 */

二、用队列实现栈

2.1、题目描述

力扣链接:https://leetcode.cn/problems/implement-stack-using-queues/
请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty)。

实现 MyStack 类:
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的,返回 true ;否则,返回 false 。

注意:
你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。

2.2、示例

在这里插入图片描述

2.3、题解

使用一个队列,唯一麻烦的就是出队列时,把队列最里层元素拿出再压入队列,直至拿到最后一个,弹出队列。

class MyStack {
    private queue: number[];
    constructor() {
        this.queue =[];
    }

    push(x: number): void {
        this.queue.push(x);
    }

    pop(): number {
        for (let i = 0, length = this.queue.length - 1; i < length; i++) { //即把队列最里层元素拿出再压入队列,直至拿到最后一个,弹出队列
            this.queue.push(this.queue.shift()!);
        }
        return this.queue.shift()!;
    }

    top(): number {
        let res: number = this.pop();
        this.push(res);
        return res;
    }

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

三、有效的括号

3.1、 题目描述

力扣链接:https://leetcode.cn/problems/implement-stack-using-queues/
给定一个只包括 ‘(’,’)’,’{’,’}’,’[’,’]’ 的字符串 s ,判断字符串是否有效。

有效字符串需满足:

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

3.2、示例

在这里插入图片描述

3.3、题解

经典的括号判断题,使用栈进行判断,左括号则进栈,右括号出栈,出栈时判断对不对应,如果不对应就return false。
要注意的是有可能样例是"(","({","({{{{{{}",这种情况会导致出栈都是判断正确,但是括号字符串实际上不合理,所以最后还要判断一次栈是否还剩元素,这样就可以判断是否还有多余左括号。

function isValid(s: string): boolean {
    let myStack: string[] = [];
    for(let i:number = 0; i < s.length; i++){
        let x: string = s[i];
        if(x == '(' || x == '[' || x == '{')
            myStack.push(x);
        else{
            switch(x){
                case ')':
                    if(myStack.pop() !== '(')
                        return false;
                    break;
                case ']':
                    if(myStack.pop() !== '[')
                        return false;
                    break;
                case '}':
                    if(myStack.pop() !== '{')
                        return false;
                    break;
            }
        }
    }
    return myStack.length === 0;
};

四、逆波兰表达式求值

4.1、题目描述

力扣链接:https://leetcode.cn/problems/evaluate-reverse-polish-notation/

根据 逆波兰表示法,求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。
注意 两个整数之间的除法只保留整数部分。
可以保证给定的逆波兰表达式总是有效的。换句话说,表达式总会得出有效数值且不存在除数为 0 的情况。

4.2、示例

在这里插入图片描述

4.3、题解

逆波兰式也叫后缀表达式(将运算符写在操作数之后)
后缀表达式例如a b + ,运算符在两个操作数的后面。后缀表达式虽然看起来奇怪,不利于人阅读,但利于计算机处理。转换为后缀表达式的好处是:
1、去除原来表达式中的括号,因为括号只指示运算顺序,不是实际参与计算的元素。
2、使得运算顺序有规律可寻,计算机能编写出代码完成计算。

而要逆波兰形式进行运算时,使用栈的概念来解题会显得非常简便,数字则压栈,运算符则弹出栈。

要注意的是,在ts运算除法的时候,要使用Math.trunc(x)而不是Math.floor(x),两者在正数部分表现一致,在负数的时候有很大区别:
Math.floor(x):返回小于一个数的最大整数,即一个数向下取整后的值。
Math.trunc(x):返回一个数的整数部分,直接去除其小数点及之后的部分。

function evalRPN(tokens: string[]): number {
    let myStack:number[] = [];
    for(let i = 0; i < tokens.length; i++){
        if(tokens[i] == '+' || tokens[i] == '-' || tokens[i] == '*' || tokens[i] == '/'){
            let second: number = myStack.pop();
            let first: number = myStack.pop();
            switch(tokens[i]){
                case '+':
                    first = first + second;
                    myStack.push(first);
                    break;
                case '-':
                    first = first - second;
                    myStack.push(first);
                    break;
                case '*':
                    first = first * second;
                    myStack.push(first);
                    break;
                case '/':
                    first = Math.trunc(first / second);
                    myStack.push(first);
                    break;
            }
        }
        else{
            myStack.push(Number(tokens[i]));
        }
    }
    return myStack.pop();
};

进阶方法,我们可以使用一个map来设计+,-,*,/对应的函数操作。
在TS 的类型定义中,=> 用来表示函数的定义,左边是输入类型,需要用括号括起来,括号右边是输出类型。

function evalRPN(tokens: string[]): number {
    const helperStack: number[] = [];
    const operatorMap: Map<string, (a: number, b: number) => number> = new Map([
        ['+', (a, b) => a + b],
        ['-', (a, b) => a - b],
        ['/', (a, b) => Math.trunc(a / b)],
        ['*', (a, b) => a * b],
    ]);
    let a: number, b: number;
    for (let t of tokens) {
        if (operatorMap.has(t)) {
            b = helperStack.pop()!;
            a = helperStack.pop()!;
            helperStack.push(operatorMap.get(t)(a, b)); //operatorMap.get(t)返回的是一个函数 函数的参数为(a,b)
        } else {
            helperStack.push(Number(t));
        }
    }
    return helperStack.pop()!;
};
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。