建立一个网站需要人员,wordpress 连接微博,站长之家alexa排名,2022年互联网公司排名汇总代码见#xff1a;登录 - Gitee.com
上一篇文章#xff1a;数据结构#xff1a;双向链表-CSDN博客
与本文相关的结构体传参#xff1a;自定义类型#xff1a;结构体-CSDN博客
1.栈
1.1概念和结构
栈#xff1a;一种特殊的线性表#xff0c;其只允许在固定的一端…汇总代码见登录 - Gitee.com
上一篇文章数据结构双向链表-CSDN博客
与本文相关的结构体传参自定义类型结构体-CSDN博客
1.栈
1.1概念和结构
栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFOLastInFirstOut的原则。 压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。 出栈栈的删除操作叫做出栈。出数据也在栈顶。 栈底层结构选型
栈的实现一般可以使用数组或者链表实现相对而言数组的结构实现更优一些。
原因在入栈和出栈的时间复杂度均为O(1)的前提条件下数组的内存利用率远高于链表尤其是在存储小数据类型时。
1.2栈的实现
依旧建立三个文件 1.2.1定义栈的结构 //定义栈的结构
typedef int STDataType;
typedef struct Stack {STDataType* arr;int top;//指向当前栈顶元素的索引--正好为栈中有效的数据个数int capacity;//栈的空间大小
}ST;1.2.2初始化
//初始化
void STInit(ST* ps)
{ps-arr NULL;ps-capacity ps-size 0;
}
调用调试
1.2.3销毁
//销毁
void STDesTroy(ST* ps)
{if (ps-arr)free(ps-arr);ps-arr NULL;ps-size ps-capacity 0;
}
1.2.4入栈 // ⼊栈
void STPush(ST* ps, STDataType x)
{assert(ps);//判断空间是否足够if (ps-top ps-capacity){//增容int newCapacity ps-capacity 0 ? 4 : 2 * ps-capacity;STDataType* tmp (STDataType*)realloc(ps-arr, newCapacity * sizeof(STDataType));if (tmp NULL){perror(realloc fail!);exit(1);}ps-arr tmp;ps-capacity newCapacity;}//空间足够ps-arr[ps-top] x;
}
调用测试
STPush(st, 1);
STPush(st, 2);
STPush(st, 3);
STPush(st, 4);
STPush(st, 5);
1.2.5判空
//栈是否为空
bool STEmpty(ST* ps)
{assert(ps);return ps-top 0;
}
1.2.6出栈 //出栈
void STPop(ST* ps)
{assert(!STEmpty(ps));ps-top--;
}
调用测试 1.2.7取栈顶元素
top为指向当前栈顶元素的索引所以需要-1。 //取栈顶元素
STDataType STTop(ST* ps)
{assert(!STEmpty(ps));return ps-arr[ps-top - 1];
}
调用测试
while (!STEmpty(st))
{//取栈顶STDataType top STTop(st);printf(%d , top);//出栈STPop(st);
}
printf(\n);
1.2.8获取栈中有效元素个数
//获取栈中有效元素个数
int STSize(ST* ps)
{assert(ps);return ps-top;
}
调用测试
printf(size:%d\n,STSize(st));
1.3解释assert(ps)与assert(!STEmpty)
assert(ps)保证传入的为有效的栈结构体变量。限制参数不能为空。
assert(!STEmpty)保证栈中的有效个数不能为空。
2.力扣算法题有效的括号
20. 有效的括号 - 力扣LeetCode
理解题意 思路借助栈遍历字符串如果遇到左括号就将字符串入栈如果遇到右括号就取栈顶将其与右括号相比较相同则出栈。
编程中遇到的问题有空字符串或者遇到一开始就是右括号的需要判断栈是否为空以及对于条件表达式的使用错误。
代码如下
// 需要借助栈
// 定义栈的结构
typedef char STDataType;
typedef struct Stack {STDataType* arr;int top; // 指向当前栈顶元素的索引--正好为栈中有效的数据个数int capacity; // 栈的空间大小
} ST;
// 初始化
void STInit(ST* ps) {ps-arr NULL;ps-capacity ps-top 0;
}// 销毁
void STDesTroy(ST* ps) {if (ps-arr)free(ps-arr);ps-arr NULL;ps-top ps-capacity 0;
}// ⼊栈
void STPush(ST* ps, STDataType x) {assert(ps);// 判断空间是否足够if (ps-top ps-capacity) {// 增容int newCapacity ps-capacity 0 ? 4 : 2 * ps-capacity;STDataType* tmp (STDataType*)realloc(ps-arr, newCapacity * sizeof(STDataType));if (tmp NULL) {perror(realloc fail!);exit(1);}ps-arr tmp;ps-capacity newCapacity;}// 空间足够ps-arr[ps-top] x;
}// 栈是否为空
bool STEmpty(ST* ps) {assert(ps);return ps-top 0;
}// 出栈
void STPop(ST* ps) {assert(!STEmpty(ps));ps-top--;
}// 取栈顶元素
STDataType STTop(ST* ps) {assert(!STEmpty(ps));return ps-arr[ps-top - 1];
}// 获取栈中有效元素个数
int STSize(ST* ps) {assert(ps);return ps-top;
}
// 以上为栈结构的定义与常见方法
bool isValid(char* s) {ST st;STInit(st);char* i s;while (*i ! \0) {// 左括号入栈if (*i ( || *i [ || *i {) {STPush(st, *i);} else {// 右括号取栈顶出栈或返回false// 若第一个为右括号为空栈if (STEmpty(st)) {STDesTroy(st);return false;}char top STTop(st);if((top [ *i ! ]) || (top { *i ! })|| (top ( *i ! ))){STDesTroy(st);return false;} //匹配-出栈STPop(st);}i;}// 栈是否为空// if(STEmpty(st))// {// STDesTroy(st);// return true;// }// STDesTroy(st);// return false;bool ret STEmpty(st) ? true : false;STDesTroy(st);return ret;
}
最终通过测试。
本章完。
