前言
实现栈有很多种方式，在这里我们使用的方法是动态数组实现。
栈的概念及结构
一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。
进行数据插入和删除 操作的一端称为栈顶，另一端称为栈底。
栈中的数据元素遵守后进先出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：
输入：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; }
