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

🕺作者@启明星使

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

🏇分享一句话：

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

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

希望得到大家的支持，如果有帮助希望得到的大家三连~~~

目录

前言

思路

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 仅由括号 '()[]{}' 组成

题解

• 在这里我们使用了栈的思想，首先定义一个栈，然后拿栈顶和字符串的值配对
• 所以我们使用了循环遍历，直到字符串结束为止打破循环，在循环里面，使用Swich语句
• 如果是左括号则入栈，字符串遍历下一个
• 如果是右括号，则先判断是否为空
• 如果为空，则无需继续不可能配对成功了，打破循环结束，返回false
• 如果不是空，则拿栈顶的元素和字符串中的元素配对，这里要记得出栈
• 判断是否不匹配，如果不匹配则销毁栈，返回false，否则匹配继续遍历字符串，直到结束为止
• 最后判断栈内是否为空，若为空则说明全部匹配成功返回true，否则返回false。

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;
        
}