首页 > 编程学习 > 数据结构之栈的实现及相关OJ题

数据结构之栈的实现及相关OJ题

发布时间:2022/11/19 22:01:43

🕺作者@启明星使

🎃专栏:《数据库》《C语言》

🏇分享一句话:

对的人会站在你的前途里 志同道合的人才看得懂同一片风景

大家一起加油🏄‍♂️🏄‍♂️🏄‍♂️

希望得到大家的支持,如果有帮助希望得到的大家三连~~~afbae359ff6c469aa4242bd6dcb5e558.jpeg

目录

前言

思路

1. 定义结构体

2.初始化

3. 销毁

4. 入栈

2 容量足够:

利用数组的性质将值赋给栈顶

栈顶自增

5. 出栈

6. 栈长

7. 栈空

代码实现

1. 定义结构体

2. 初始化

3. 销毁

4. 入栈

5. 出栈

6. 栈长

7. 栈空

OJ题(简单)

题解


前言

实现栈有很多种方式,在这里我们使用的方法是动态数组实现。

栈的概念及结构 

  • 一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。
  • 进行数据插入和删除 操作的一端称为栈顶,另一端称为栈底。
  • 栈中的数据元素遵守后进先出LIFO(Last In First Out) 的原则。

思路

  • 拓展:assert()内的条件若返回错误则停止程序 非必要只是方便Debug
  • tips:主函数中得先定义一个结构体变量

1. 定义结构体

  • 数组
  • 栈顶
  • 记录存储容量的变量

2.初始化

  • assert()断言:判断结构体是否存在
  • 先给数组开辟一个初始空间4
  • 判断开辟空间是否成功
  • 存储容量为4
  • 栈顶为0

3. 销毁

  • assert()断言:判断结构体是否存在
  • 销毁数组,将数组置为NULL
  • 将栈顶的值和存储容量的变量置为0

4. 入栈

  • assert()断言:判断结构体是否存在
    • 先判断容量是否足够:
    • 不够则增容(假设增两倍)
      这里用的是realloc
      会先将原数组的值先拷贝,开辟一个新空间增容
      • 增容后判断是否成功增容
      •  失败则打印增容失败
      •  成功则把新空间的地址赋给结构体变量里的数组
      •  存储容量的变量*2
    • 容量足够入栈:
      • 利用数组的性质将值赋给栈顶
      •  栈顶自增

5. 出栈

  • 取栈顶值
    • assert()断言:判断结构体是否存在
    • assert()断言:判断栈顶是否大于0
    • 利用数组性质返回栈顶元素的值
  • 删去栈顶
    • assert()断言:判断结构体是否存在 a
    • ssert()断言:判断栈顶是否大于0
    • 栈顶位置减一

6. 栈长

  • assert()断言:判断结构体是否存在
  • 返回栈顶下标即为栈长

7. 栈空

  • assert()断言:判断结构体是否存在
  • 返回一个bool值 根据栈顶下标是否为0判断栈是否为空

代码实现

1. 定义结构体

typedef struct Sqstack
{
    Elemtype* a;
    int top;
    int capacity;
}Sq;

2. 初始化

void Initstack(Sq*st) {
    assert(st);
    st->a = (Elemtype*)malloc(sizeof(Elemtype) * 4);
    if (st->a == NULL) {
        printf("malloc fail\n");
        exit(-1);
    }
    st->capacity = 4;
    st->top = 0;
} 

3. 销毁

void DestroySt(Sq* st) {
    assert(st);
    free(st->a);
    st->a = NULL;
    st->top = st->capacity = 0;
}

4. 入栈

void InsertSt(Sq* st,Elemtype x) {
    assert(st);
    if (st->top == st->capacity) {
        Elemtype* tem = (Elemtype*)realloc(st->a, st->capacity * 2 * sizeof(Elemtype));
        if (tem == NULL) {
            printf("realloc fail\n");
            exit(-1);
        }
        else
        {
            st->a = tem;
            st->capacity *= 2;
        }
    }
    st->a[st->top] = x;
    st->top++;
}
​

5. 出栈

Elemtype TopSt(Sq* st) {
    assert(st);
    assert(st->top > 0);
    return st->a[st->top -1];
}
void PopSt(Sq* st) {
    assert(st);
    assert(st->top > 0);
    st->top--;
}

6. 栈长

int Stsize(Sq* st) {
    assert(st);
    return st->top;
}

7. 栈空

bool StEmpty(Sq* st) {
    assert(st);
    return st->top == 0;
}

OJ题(简单)

有效的括号

给定一个只包括 '('')''{''}''['']' 的字符串 s ,判断字符串是否有效。

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。

  2. 左括号必须以正确的顺序闭合。

  3. 每个右括号都有一个对应的相同类型的左括号。

示例 1:

输入:s = "()"
输出:true

示例 2:

输入:s = "()[]{}"
输出:true

示例 3:

输入:s = "(]"
输出:false

提示:

  • 1 <= s.length <= 104

  • s 仅由括号 '()[]{}' 组成

题解

typedef char Elemtype;
typedef struct Sqstack
{
    Elemtype* a;
    int top;
    int capacity;
}Sq;
void Initstack(Sq*st) {
    assert(st);
    st->a = (Elemtype*)malloc(sizeof(Elemtype) * 4);
    if (st->a == NULL) {
        printf("malloc fail\n");
        exit(-1);
    }
    st->capacity = 4;
    st->top = 0;
} 
void DestroySt(Sq* st) {
    assert(st);
    free(st->a);
    st->a = NULL;
    st->top = st->capacity = 0;
}
void InsertSt(Sq* st,Elemtype x) {
    assert(st);
    if (st->top == st->capacity) {
        Elemtype* tem = (Elemtype*)realloc(st->a, st->capacity * 2 * sizeof(Elemtype));
        if (tem == NULL) {
            printf("realloc fail\n");
            exit(-1);
        }
        else
        {
            st->a = tem;
            st->capacity *= 2;
        }
    }
    st->a[st->top] = x;
    st->top++;
}
​
Elemtype TopSt(Sq* st) {
    assert(st);
    assert(st->top > 0);
​
    return st->a[st->top -1];
}
void PopSt(Sq* st) {
    assert(st);
    assert(st->top > 0);
    st->top--;
}
int Stsize(Sq* st) {
    assert(st);
    return st->top;
}
bool StEmpty(Sq* st) {
    assert(st);
    return st->top == 0;
}
int lengths(char*s){
    int i=0;
    while(s[i]!='\0'){
        i++;
    }
    return i;
}
bool isValid(char * s){
    Sq st;
    Initstack(&st);
    
    while(*s !='\0'){
        switch(*s)
        {
            case '{':
            case '[':
            case '(':
            {
                InsertSt(&st,*s);
                ++s;
                break;
            }
            case '}':
            case ')':
            case ']':
            {
                if(StEmpty(&st)){
                    DestroySt(&st);
                    return false;
                }
                char top=TopSt(&st);
                PopSt(&st);
​
                if((*s=='}'&&top!='{')
                ||(*s==']'&&top!='[')
                ||(*s==')'&&top!='('))
                {
                    DestroySt(&st);
                    return false;
                }
                else{
                    ++s;
                }
                break;
            }
            default:
                break;
        }
    }
​
    bool ret=StEmpty(&st);
    DestroySt(&st);
    return ret;
        
}

Copyright © 2010-2022 dgrt.cn 版权所有 |关于我们| 联系方式