AI 助理
备案控制台
开发者社区 云计算 文章 正文

【LeetCode题目详解】（四）20.有效的括号、225.用队列实现栈

2023-11-14 42
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【LeetCode题目详解】（四）20.有效的括号、225.用队列实现栈


一、力扣第20题：有效的括号

题目链接：20. 有效的括号 - 力扣（Leetcode）

题目描述：

1.解题思路

我们先分析一下题目，它一共只需要匹配三种情况，() [] {}。对于字符串的的一堆括号，我们其实可以将它想象成一共栈，当字符串是( [ { 也就是左括号的时候，就入栈。当遇到右括号的时候，我们就看这个右括号是否与栈顶元素匹配，顺便把栈顶元素给取出来。如果刚好匹配，那太好了，我们可以看下一个字符，是需要入栈还是需要进行匹配。我们进行重复判断，当刚好栈为空的时候，那么也就是说明这个字符串匹配成功了。如果不匹配的话，那我们直接返回false就可以了。

2.写出代码

我们的思路全部是利用栈的，所以我们必须得先实现一个栈出来。根据我们这些思路，我们需要使用的栈操作有初始化栈、入栈、销毁栈、判断栈是否为空、取出栈顶的元素、出栈这些操作。我们先来实现一下这些操作。

如下所示，因为该题是接口型的，所以我们无需写出头文件，这是我们栈的实现。注意这里一定要自己写出来

typedef char STDateType;
typedef struct Stack
{
    STDateType* a;
    int top;
    int capacity;
}Stack;
//初始化栈
void StackInit(Stack* ps)
{
    assert(ps);
    STDateType* tmp = (STDateType*)malloc(4*sizeof(STDateType));
    if(tmp==NULL)
    {
        printf("malloc is fail\n");
        exit(-1);
    }
    pa->a=tmp;
    ps->top=0;
    ps->capacity=4;
}
//入栈
void StackPush(Stack* ps,STDateType x)
{
    assert(ps);
    //判断容量是否满了
    if(ps->top==ps->capacity)
    {
        //扩容
        STDateType* tmp=(STDateType*)realloc(ps->a,2 * sizeof(STDateType)* ps->capacity);
        if(tmp==NULL)
        {
            printf("realloc is fail\n");
            exit(-1);
        }
        ps->a=tmp;
        ps->capacity*=2;
    }
    //入栈
    ps->a[ps->top]=x;
    ps->top++;
}
//出栈
void StackPop(Stack* ps)
{
    assert(ps);
    assert(ps->top>0);
    ps->top--;
}
//取出栈顶元素
STDateType StackTop(Stack* ps)
{
    assert(ps);
    assert(ps->top>0);
    return ps->a[ps->top-1];
}
//判断栈是否为空
bool StackEmpty(Stack* ps)
{
    assert(ps);
    return ps->top==0;
}
//销毁栈
void StackDestory(Stack* ps)
{
    assert(ps);
    free(ps->a);
    ps->a=NULL;
    ps->capacity=ps->top=0;
}

然后接下来就是我们要开始使用栈了

使用栈的话，要特别注意几个极端情况，如只有左括号，只有右括号，等情况的处理

bool isValid(char * s)
{
    Stack ST;
    StackInit(&ST);
    while(*s)
    {
        switch(*s)
        {
            case '(':
            case '[':
            case '{':
                StackPush(&ST,*s);
                break;
            case ')':
            case ']':
            case '}':
            {
                if(StackEmpty(&ST))
                {
                    StackDestory(&ST);
                    return false;
                }
                char tmp=StackTop(&ST);
                StackPop(&ST);
                if( *s==')'&& tmp!='('||
                    *s==']'&& tmp!='['||
                    *s=='}'&& tmp!='{')
                {
                    StackDestory(&ST);
                    return false;
                }
                break;
            }
            default:
                break;
        }
        s++;
    }
    if(!StackEmpty(&ST))
    {
        StackDestory(&ST);
        return false;
    }
    else
    {
        StackDestory(&ST);
        return true;
    }
}

3.完整代码

typedef char STDateType;
typedef struct Stack
{
    STDateType* a;
    int top;
    int capacity;
}Stack;
//初始化栈
void StackInit(Stack* ps)
{
    assert(ps);
    STDateType* tmp = (STDateType*)malloc(4*sizeof(STDateType));
    if(tmp==NULL)
    {
        printf("malloc is fail\n");
        exit(-1);
    }
    ps->a=tmp;
    ps->top=0;
    ps->capacity=4;
}
//入栈
void StackPush(Stack* ps,STDateType x)
{
    assert(ps);
    //判断容量是否满了
    if(ps->top==ps->capacity)
    {
        //扩容
        STDateType* tmp=(STDateType*)realloc(ps->a,2 * sizeof(STDateType)* ps->capacity);
        if(tmp==NULL)
        {
            printf("realloc is fail\n");
            exit(-1);
        }
        ps->a=tmp;
        ps->capacity*=2;
    }
    //入栈
    ps->a[ps->top]=x;
    ps->top++;
}
//出栈
void StackPop(Stack* ps)
{
    assert(ps);
    assert(ps->top>0);
    ps->top--;
}
//取出栈顶元素
STDateType StackTop(Stack* ps)
{
    assert(ps);
    assert(ps->top>0);
    return ps->a[ps->top-1];
}
//判断栈是否为空
bool StackEmpty(Stack* ps)
{
    assert(ps);
    return ps->top==0;
}
//销毁栈
void StackDestory(Stack* ps)
{
    assert(ps);
    free(ps->a);
    ps->a=NULL;
    ps->capacity=ps->top=0;
}
bool isValid(char * s)
{
    Stack ST;
    StackInit(&ST);
    while(*s)
    {
        switch(*s)
        {
            case '(':
            case '[':
            case '{':
                StackPush(&ST,*s);
                break;
            case ')':
            case ']':
            case '}':
            {
                if(StackEmpty(&ST))
                {
                    StackDestory(&ST);
                    return false;
                }
                char tmp=StackTop(&ST);
                StackPop(&ST);
                if( *s==')'&& tmp!='('||
                    *s==']'&& tmp!='['||
                    *s=='}'&& tmp!='{')
                {
                    StackDestory(&ST);
                    return false;
                }
                break;
            }
            default:
                break;
        }
        s++;
    }
    if(!StackEmpty(&ST))
    {
        StackDestory(&ST);
        return false;
    }
    else
    {
        StackDestory(&ST);
        return true;
    }
}

二、力扣第225题：用队列实现栈

题目链接：225. 用队列实现栈 - 力扣（Leetcode）

题目描述：

1.思路分析

我们现在有两个队列，队列的性质是先进先出，而栈的性质是先进后出。那么我们该如何实现呢？我们可以这样做，假如说这是两个队列，我们先将数据都放入一个队列中

当我们想要出去一共数据的时候，那么栈的性质是先出4。所以我们可以先将1 2 3都放入第二个队列中，然后4就可以出去了。

当我们想要插入一共数据的时候，我们直接插入到有数据的一个队列中，这样就能模拟对栈的性质了。

2.代码实现

既然要运用到队列，那么我们得先实现一下队列。才可以去使用

如下所示，是本题的队列的实现部分

typedef int QDateType;
typedef struct QNode
{
    struct QNode* next;
    QDateType date;
}QNode;
typedef struct Queue
{
    QNode* head;
    QNode* tail;
}Queue;
//队列的初始化
void QueueInit(Queue* pq)
{
    assert(pq);
    pq->head=NULL;
    Pq->tail=NULL;
}
//队列的插入
void QueuePush(Queue* pq,QDateType x)
{
    assert(pq);
    //创建结点
    QNode* newnode=(QNode*)malloc(sizeof(QNode));
    if(newnode==NULL)
    {
        printf("malloc is fail\n");
        exit(-1);
    }
    newnode->next=NULL;
    newnode->date=x;
    //第一个结点的插入
    if(pq->head==NULL)
    {
        pq->head=pq->tail=newnode;
    }
    //非第一个结点的插入
    else
    {
        pq->tail->next=newnode;
        pq->tail=newnode;
    }
}
//出队列
void QueuePop(Queue* pq)
{
    assert(pq);
    assert(pq->head);
    //如果只有一个结点，那么tail会形成野指针
    if(pq->head->next==NULL)
    {
        free(pq->head);
        pq->head=pq->tail=NULL;
    }
    else
    {
        QNode* second=pq->head->next;
        free(pq->head);
        pq->head=second;
    }
}
//队头的元素
QDateType QueueFront(Queue* pq)
{
    assert(pq);
    assert(pq->head);
    return pq->head->date;
}
//队尾的元素
QDateType QueueBack(Queue* pq)
{
    assert(pq);
    assert(pq->head);
    return pq->tail->date;
}
//队列的元素个数
int QueueSize(Queue* pq)
{
    assert(pq);
    int size=0;
    QNode* cur=pq->head;
    while(cur)
    {
        size++;
        cur=cur->next;
    }
    return size;
}
//队列是否为空
bool QueueEmpty(Queue* pq)
{
    assert(pq);
    return pq->head==NULL;
}
//队列的销毁
void QueueDestory(Queue* pq)
{
    assert(pq);
    QNode* cur=pq->head;
    while(cur)
    {
        QNode* next=cur->next;
        free(cur);
        cur=next;
    }
    pq->head=NULL;
    pq->tail=NULL;
}

有了这个队列，我们才可以去完成这道题。

typedef struct {
    Queue q1;
    Queue q2;
} MyStack;
MyStack* myStackCreate() {
    MyStack* ps=(MyStack*)malloc(sizeof(MyStack));
    if(ps==NULL)
    {
        printf("malloc is fail\n");
        exit(-1);
    }
    //初始化队列
    QueueInit(&ps->q1);
    QueueInit(&ps->q2);
    return ps;
}
void myStackPush(MyStack* obj, int x) {
    if(QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q2,x);
    }
    else
    {
        QueuePush(&obj->q1,x);
    }
}
int myStackPop(MyStack* obj) {
    Queue* emptyQueue=&obj->q1;
    Queue* noemptyQueue=&obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        emptyQueue=&obj->q2;
        noemptyQueue=&obj->q1;
    }
    while(QueueSize(noemptyQueue) >1)
    {
        QueuePush(emptyQueue,QueueFront(noemptyQueue));
        QueuePop(noemptyQueue);
    }
    int ret=QueueFront(noemptyQueue);
    QueuePop(noemptyQueue);
    return ret;
}
int myStackTop(MyStack* obj) {
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }
}
bool myStackEmpty(MyStack* obj) {
    if(QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2))
    {
        return true;
    }
    else
    {
        return false;
    }
}
void myStackFree(MyStack* obj) {
    QueueDestory(&obj->q1);
    QueueDestory(&obj->q2);
    free(obj);
}

3.完整代码

typedef int QDateType;
typedef struct QNode
{
    struct QNode* next;
    QDateType date;
}QNode;
typedef struct Queue
{
    QNode* head;
    QNode* tail;
}Queue;
//队列的初始化
void QueueInit(Queue* pq)
{
    assert(pq);
    pq->head=NULL;
    pq->tail=NULL;
}
//队列的插入
void QueuePush(Queue* pq,QDateType x)
{
    assert(pq);
    //创建结点
    QNode* newnode=(QNode*)malloc(sizeof(QNode));
    if(newnode==NULL)
    {
        printf("malloc is fail\n");
        exit(-1);
    }
    newnode->next=NULL;
    newnode->date=x;
    //第一个结点的插入
    if(pq->head==NULL)
    {
        pq->head=pq->tail=newnode;
    }
    //非第一个结点的插入
    else
    {
        pq->tail->next=newnode;
        pq->tail=newnode;
    }
}
//出队列
void QueuePop(Queue* pq)
{
    assert(pq);
    assert(pq->head);
    //如果只有一个结点，那么tail会形成野指针
    if(pq->head->next==NULL)
    {
        free(pq->head);
        pq->head=pq->tail=NULL;
    }
    else
    {
        QNode* second=pq->head->next;
        free(pq->head);
        pq->head=second;
    }
}
//队头的元素
QDateType QueueFront(Queue* pq)
{
    assert(pq);
    assert(pq->head);
    return pq->head->date;
}
//队尾的元素
QDateType QueueBack(Queue* pq)
{
    assert(pq);
    assert(pq->head);
    return pq->tail->date;
}
//队列的元素个数
int QueueSize(Queue* pq)
{
    assert(pq);
    int size=0;
    QNode* cur=pq->head;
    while(cur)
    {
        size++;
        cur=cur->next;
    }
    return size;
}
//队列是否为空
bool QueueEmpty(Queue* pq)
{
    assert(pq);
    return pq->head==NULL;
}
//队列的销毁
void QueueDestory(Queue* pq)
{
    assert(pq);
    QNode* cur=pq->head;
    while(cur)
    {
        QNode* next=cur->next;
        free(cur);
        cur=next;
    }
    pq->head=NULL;
    pq->tail=NULL;
}
typedef struct {
    Queue q1;
    Queue q2;
} MyStack;
MyStack* myStackCreate() {
    MyStack* ps=(MyStack*)malloc(sizeof(MyStack));
    if(ps==NULL)
    {
        printf("malloc is fail\n");
        exit(-1);
    }
    //初始化队列
    QueueInit(&ps->q1);
    QueueInit(&ps->q2);
    return ps;
}
void myStackPush(MyStack* obj, int x) {
    if(QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q2,x);
    }
    else
    {
        QueuePush(&obj->q1,x);
    }
}
int myStackPop(MyStack* obj) {
    Queue* emptyQueue=&obj->q1;
    Queue* noemptyQueue=&obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        emptyQueue=&obj->q2;
        noemptyQueue=&obj->q1;
    }
    while(QueueSize(noemptyQueue) >1)
    {
        QueuePush(emptyQueue,QueueFront(noemptyQueue));
        QueuePop(noemptyQueue);
    }
    int ret=QueueFront(noemptyQueue);
    QueuePop(noemptyQueue);
    return ret;
}
int myStackTop(MyStack* obj) {
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }
}
bool myStackEmpty(MyStack* obj) {
    if(QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2))
    {
        return true;
    }
    else
    {
        return false;
    }
}
void myStackFree(MyStack* obj) {
    QueueDestory(&obj->q1);
    QueueDestory(&obj->q2);
    free(obj);
}
/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);
 * int param_2 = myStackPop(obj);
 * int param_3 = myStackTop(obj);
 * bool param_4 = myStackEmpty(obj);
 * myStackFree(obj);
*/

总结

本小节完成了两道力扣题，20.有效的括号、225.用队列实现栈

如果对你有帮助的话，不要忘记一键三连哦！！！

想获得更多优质的内容，一定要关注我哦！！！

关键词：
LeetCode括号
LeetCode题目
LeetCode队列
LeetCode队列栈
LeetCode栈
青色忘川
目录
相关文章
小王老师呀
|
1月前
|
存储 算法 Java
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合，并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构，遍历字符串时将左括号压入栈中，遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
小王老师呀
40 4
可惜已不在
|
2月前
|
程序员 C语言
【C语言】LeetCode(力扣)上经典题目
【C语言】LeetCode(力扣)上经典题目
可惜已不在
34 1
石小浪♪
|
2月前
|
算法 C++
Leetcode第二十二题(括号生成)
这篇文章讨论了如何使用递归算法解决LeetCode第22题“括号生成”的问题，提供了两种C++的实现方法，目的是生成所有有效的括号组合。
石小浪♪
21 0
Leetcode第二十二题(括号生成)
Codelinghu
|
2月前
【LeetCode 24】225.用队列实现栈
【LeetCode 24】225.用队列实现栈
Codelinghu
12 0
石小浪♪
|
2月前
|
存储 C++ 容器
Leetcode第二十题(有效的括号)
这篇文章介绍了如何使用栈来解决LeetCode第20题“有效的括号”问题，提供了两种方法：数组栈和容器栈，以及相应的C++代码实现。
石小浪♪
19 0
Codelinghu
|
2月前
|
算法
【LeetCode 23】232.用栈实现队列
【LeetCode 23】232.用栈实现队列
Codelinghu
21 0
dream_ready
|
2月前
|
算法 Java C++
双指针算法(超详细带8道例题及算法解析) —— 包含力扣题目有283移动零、1089复写零、202快乐数、11盛水最多的容器、611有效三角形的个数、179双数之和、15三数之和、18四数之和
这篇文章详细介绍了双指针算法的概念、应用场景和八道力扣题目的解题思路及Java代码实现。
dream_ready
101 0
服务端技术栈
|
4月前
|
算法
LeetCode第22题括号生成
该文章介绍了 LeetCode 第 22 题括号生成的解法，通过回溯算法生成所有可能的括号组合，在递归过程中根据左右括号数量的条件进行剪枝，从而得到有效的括号组合。
服务端技术栈
42 3
LeetCode第22题括号生成
杀死一只知更鸟debug
|
3月前
|
SQL Oracle 关系型数据库
CASE WHEN 语句的语法及示例，LeetCode 题目 “确认率” 练习
本文介绍了SQL中CASE语句的两种形式和语法，并通过LeetCode题目“确认率”的SQL查询示例展示了CASE语句在实际问题中的应用，解释了如何使用CASE语句计算特定条件的比率。
杀死一只知更鸟debug
47 0
yantuguiguziPGJ
|
3月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案，包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行，每个问题都给出了至少一种实现方法。
yantuguiguziPGJ
60 6
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行