数据结构和算法学习记录——特殊线性表之栈（下）-销毁栈函数、判断栈是否为空、压栈函数、出栈函数、取栈顶元素、计算栈中有多少个元素、栈有关习题-有效的括号-阿里云开发者社区

数据结构和算法学习记录——特殊线性表之栈（下）-销毁栈函数、判断栈是否为空、压栈函数、出栈函数、取栈顶元素、计算栈中有多少个元素、栈有关习题-有效的括号

2024-06-06 11

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 数据结构和算法学习记录——特殊线性表之栈（下）-销毁栈函数、判断栈是否为空、压栈函数、出栈函数、取栈顶元素、计算栈中有多少个元素、栈有关习题-有效的括号

特殊线性表之栈（上）

销毁栈函数

void StackDestroy(ST* ps)
{
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->capacity = ps->top = 0;
}

判断栈是否为空

bool StackEmpty(ST* ps)
{
    assert(ps);
    return ps->top == 0;//top为0返回真，否则返回假
}

压栈函数

void StackPush(ST* ps, STDataType x)
{
    assert(ps);
 
    if (ps->top == ps->capacity) //判断扩容
    {
        int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
        STDataType* tmp = realloc(ps->a, sizeof(STDataType) * newCapacity);
        if (tmp == NULL)
        {
            printf("realloc fail\n");
            exit(-1);
        }
        ps->a = tmp;
        ps->capacity = newCapacity;
    }
 
    ps->a[ps->top] = x;
    ps->top++;
}

出栈函数

void StackPop(ST* ps)
{
    assert(ps);
    assert(!StackEmpty(ps));
 
    ps->top--;
}

取栈顶元素

STDataType StackTop(ST* ps)//取出栈顶元素
{
    assert(ps);
    assert(!StackEmpty(ps));
    return ps->a[ps->top - 1];
}

计算栈中有多少个元素

int StackSize(ST* ps)//计算栈中有多少个元素
{
    assert(ps);
    return ps->top;
}

入栈出栈操作

int main()
{
    ST st;
    StackInit(&st);
    StackPush(&st, 1);  //入栈出栈操作
    StackPush(&st, 2);
    StackPush(&st, 3);
    StackPush(&st, 4);
    while (!StackEmpty(&st))
    {
        printf("%d\t", StackTop(&st));
        StackPop(&st);
    }
    StackDestroy(&st);
    return 0;
}

入栈序列为1、2、3、4，那么连续的出栈序列就为4、3、2、1

故运行结果为：

习题（有效的括号）

题目描述

给定一个只包括 '(' ，')' ，'{' ，'}' ，'[' ，']' 的字符串 s ，判断字符串是否有效。有效字符串需满足：左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。左括号必须用相同类型的右括号闭合。

题目示例

示例 1： 输入：s = "()" 输出：

示例 2： 输入：s = "()[]{}" 输出：true

示例 3： 输入：s = "(]" 输出：false true

题目思路

用一个栈来解题，如果是左括号则入栈；如果是右括号，则进行出栈操作，与该右括号匹配。

（但C语言的库中没有栈，需要我们自己定义一个栈）

题目代码

//上面加一个栈
bool isValid(char* s)
{
    ST st;
    StackInit(&st);
    while (*s)
    {
        if (*s == '('
         || *s == '['
         || *s == '{')  //遇到左括号，进行入栈操作
        {
            StackPush(&st, *s);
        }
        else     //遇到右括号
        {
            if (StackEmpty(&st))  //遇到右括号时栈中没有数据的情况，即匹配失败
            {
                StackDestroy(&st);
                return false;
            }
 
            STDataType top = StackTop(&st);
            StackPop(&st);
            if ((*s == '}' && top != '{')
                || (*s == ']' && top != '[')
                || (*s == ')' && top != '('))  //把左括号出栈，与右括号进行匹配
            {
                StackDestroy(&st);
                return false;
            }
            else
            {
                s++;
            }
        }
    }
 
    //while循环结束之后，判断栈中是否为空
    //如果栈不为空，则说明栈中的括号没有被成功匹配
    //也返回false
    bool ret = StackEmpty(&st);
    StackDestroy(&st);
    return ret;
}

end