【追梦之旅】——栈居然还能这样玩？！+ 力扣 - 有效括号 ~😎
- 前言🙌
- 什么是栈？
- 栈的C语言实现
- 头文件编写源码：
- 功能文件编写源码：
- 测试文件编写源码：
- 力扣题解——有效的括号
- 总结撒花💞
😎博客昵称：博客小梦
😊最喜欢的座右铭：全神贯注的上吧！！！
😊作者简介：一名热爱C/C++，算法等技术、喜爱运动、热爱K歌、敢于追梦的小博主！
😘博主小留言：哈喽！😄各位CSDN的uu们，我是你的博客好友小梦，希望我的文章可以给您带来一定的帮助，话不多说，文章推上！欢迎大家在评论区唠嗑指正，觉得好的话别忘了一键三连哦！😘
前言🙌
哈喽各位友友们😊，我今天又学到了很多有趣的知识，现在迫不及待的想和大家分享一下！😘我仅已此文，手把手带领大家栈的实现和力扣题解知识~ 都是精华内容，可不要错过哟！！！😍😍😍
什么是栈？
栈和顺序表和链表一样，是线性结构的。栈可以用数组实现，也可以用链表实现。这里采用的是动态数组（顺序结构）实现的方式。栈的特点是LIFO。什么是“LIFO”呢？用中文简单的来说就是后进先出。也有人会叫先进后出，其实都是同一个意思。
栈的C语言实现
头文件编写源码：
#pragma once #include #include #include #include typedef int STDataType; //顺序栈 typedef struct STNode { STDataType* a; int top; int capacity; }ST; void STInit(ST* pst); void STDestroy(ST* pst); void STPush(ST* pst, STDataType x); void STPop(ST* pst); bool STEmpty(ST* pst); STDataType STTop(ST* pst); int STSize(ST* pst);功能文件编写源码：
#define _CRT_SECURE_NO_WARNINGS 1 #include"Stack.h" void STInit(ST* pst) { assert(pst); pst->a = NULL; //top指向栈顶元素的下一个位置 pst->capacity = pst->top = 0; } void STDestroy(ST* pst) { assert(pst); free(pst->a); pst->capacity = pst->top = 0; pst->a = NULL; } void STPush(ST* pst, STDataType x) { assert(pst); //扩容 if (pst->capacity == pst->top) { int newcapacity = pst->capacity == 0 ? 4 : 2 * (pst->capacity); STDataType* tem = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity); if (tem == NULL) { perror("realloc fail\n"); exit(-1); } pst->capacity = newcapacity; pst->a = tem; } pst->a[pst->top] = x; (pst->top)++; } bool STEmpty(ST* pst) { assert(pst); return pst->top == 0; } void STPop(ST* pst) { assert(pst); assert(!STEmpty(pst)); (pst->top)--; } STDataType STTop(ST* pst) { assert(pst); assert(!STEmpty(pst)); return pst->a[pst->top - 1]; } int STSize(ST* pst) { assert(pst); return pst->top; }测试文件编写源码：
#define _CRT_SECURE_NO_WARNINGS 1 #include"Stack.h" int main() { //ST s; //STInit(&s); //STPush(&s, 1); //STPush(&s, 2); //STPush(&s, 3); //STPush(&s, 4); //STPush(&s, 3); //STPush(&s, 4); //while (!STEmpty(&s)) //{ // printf("%d ", STTop(&s)); // STPop(&s); //} //printf("\n"); ST s; STInit(&s); STPush(&s, 1); STPush(&s, 2); STPush(&s, 3); STPush(&s, 4); STPop(&s); STPop(&s); while (!STEmpty(&s)) { printf("%d ", STTop(&s)); STPop(&s); } printf("\n"); return 0; }
力扣题解——有效的括号
谁说C语言不能“C”，接下来我用C语言手撕这道题目。这道题目非常巧妙的运用到了栈这个特点
我的做法是：
- 先让左括号入栈
- 遇到右括号在出栈
不理解上述思想的可以自己画图理解理解，这个我相信难不倒大家，下面是我画的一个比较粗糙的图解~
如果用C嘎嘎来写，则可以直接调用库函数的栈，而C语言就比较难受了。因为C语言没有这样的库函数，所以我们需要首先一个栈，但是不能说C语言就不能做，照样可以"C"! 。前面的栈我已经写好了，直接ctrl c + ctrl v ，复制一份到题目中即可。
题目源码：
typedef int STDataType; //顺序栈 typedef struct STNode { STDataType* a; int top; int capacity; }ST; void STInit(ST* pst); void STDestroy(ST* pst); void STPush(ST* pst, STDataType x); void STPop(ST* pst); bool STEmpty(ST* pst); STDataType STTop(ST* pst); int STSize(ST* pst); #define _CRT_SECURE_NO_WARNINGS 1 void STInit(ST* pst) { assert(pst); pst->a = NULL; //top指向栈顶元素的下一个位置 pst->capacity = pst->top = 0; } void STDestroy(ST* pst) { assert(pst); free(pst->a); pst->capacity = pst->top = 0; pst->a = NULL; } void STPush(ST* pst, STDataType x) { assert(pst); //扩容 if (pst->capacity == pst->top) { int newcapacity = pst->capacity == 0 ? 4 : 2 * (pst->capacity); STDataType* tem = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity); if (tem == NULL) { perror("realloc fail\n"); exit(-1); } pst->capacity = newcapacity; pst->a = tem; } pst->a[pst->top] = x; (pst->top)++; } bool STEmpty(ST* pst) { assert(pst); return pst->top == 0; } void STPop(ST* pst) { assert(pst); assert(!STEmpty(pst)); (pst->top)--; } STDataType STTop(ST* pst) { assert(pst); assert(!STEmpty(pst)); return pst->a[pst->top - 1]; } int STSize(ST* pst) { assert(pst); return pst->top; } bool isValid(char * s) { ST st; STInit(&st); //循环遍历字符串s，遇到\0结束 while(*s) { if(*s == '(' || *s == '[' || *s == '{') { STPush(&st,*s); } else { if(STEmpty(&st)) { STDestroy(&st); return false; } char Top = STTop(&st); STPop(&st); if(*s == ')' && Top != '(' || *s == ']' && Top != '[' || *s == '}' && Top != '{') { STDestroy(&st); return false; } } s++; } bool ret = STEmpty(&st); STDestroy(&st); return ret; }运行结果截图：
总结撒花💞
本篇文章旨在分享的是栈的C语言实现和力扣题解知识。希望大家通过阅读此文有所收获！
😘如果我写的有什么不好之处，请在文章下方给出你宝贵的意见😊。如果觉得我写的好的话请点个赞赞和关注哦~😘😘😘
