【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题目详解】（四）20.有效的括号、225.用队列实现栈

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

1.解题思路

2.写出代码

3.完整代码

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

1.思路分析

2.代码实现

3.完整代码

总结

热门文章

最新文章

相关电子书