手撕数据结构:栈+例题
目录
一、栈的概念及结构
栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出的原则。
如同子弹夹,我们进行添子弹和出子弹,很形象。
压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
出栈:栈的删除操作叫做出栈。出数据也在栈顶。
接下来,我们以数组栈的形式去模拟。
二、栈的头文件及基本框架
-
-
-
-
-
-
-
typedef int STDataType;
-
-
typedef struct Stack
-
{
-
STDataType* a;//就是以a开头的一段连续的空间
-
int top;//定义栈顶位置
-
int capacity;
-
}ST;
-
-
void SLInit(ST* ps);
-
void SLDestroy(ST* ps);
-
void STPush(ST* ps, STDataType x);
-
void STPop(ST* ps);
-
int STSize(ST* ps);
-
bool STEmpty(ST* ps);
-
STDataType STTop(ST* ps);//获取栈顶元素
三、接口实现
1、对栈的初始化
-
void SLInit(ST* ps)
-
{
-
ST* ret = (ST*)malloc(4 * sizeof(ST));
-
if (ret == NULL)
-
{
-
perror(malloc);
-
exit(-1);
-
}
-
ps->a = ret;
-
ps->capacity = 4;
-
ps->top = 0;
-
}
2、栈的销毁
-
void SLDestroy(ST* ps)
-
{
-
free(ps->a);
-
ps->a = NULL;
-
ps->capacity = 0;
-
ps->top = 0;
-
}
3、入栈操作
-
void STPush(ST* ps, STDataType x)
-
{
-
assert(ps != NULL);
-
//检查需不需要扩容
-
if (ps->top == ps->capacity)
-
{
-
ps->capacity = 4;
-
ST* ret = (ST*)realloc( ps->a, sizeof(ST) * ps->capacity);
-
if (ret == NULL)
-
{
-
perror(realloc);
-
exit(-1);
-
}
-
ps->a = ret;
-
}
-
ps->a[ps->top] = x;
-
ps->top ;
-
}
4、出栈操作
-
void STPop(ST* ps)
-
{
-
assert(ps);
-
ps->top--;
-
}
5、判断栈是否为空
-
bool STEmpty(ST* ps)
-
{
-
assert(ps);
-
return ps->top == 0;
-
如果右边等式成立返回true,反之返回false
-
}
6、返回栈顶元素
-
STDataType STTop(ST* ps)
-
{
-
assert(ps);
-
assert(ps->top > 0);
-
return ps->a[ps->top - 1];
-
}
7、遍历栈
不同于其他数据结构,遍历栈不用print
-
//遍历栈的特殊方式
-
while (!STEmpty(&ps))
-
{
-
printf("%d ", STTop(&ps));
-
STPop(&ps);
-
}
四、有效的括号 - 力扣(LeetCode)
题目描述:
给定一个只包括 '('
,')'
,'{'
,'}'
,'['
,']'
的字符串 s
,判断字符串是否有效。
有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
思路:
如果是左括号就入栈,如果是右括号就与栈顶元素进行比较。这样就正好匹配题目的要求,但博主目前没有学过STL库,所以只能将上面的手撕栈CV一下啦,下面的代码为了避免冗余去除掉这一部分~
代码:
-
bool isValid(char * s)
-
{
-
char* ret = s;
-
int num = 0;
-
//利用奇数偶数判断数量是否匹配
-
while(*ret)
-
{
-
num ;
-
ret ;
-
}
-
if(num%2 != 0)
-
{
-
return false;
-
}
-
ST ps;
-
SLInit(&ps);
-
while(*s)
-
{
-
switch(*s)
-
{
-
case '{':
-
case '[':
-
case '(':
-
STPush(&ps,*s);
-
break;
-
case ')':
-
case ']':
-
case '}':
-
if(STSize(&ps) == 0)
-
return false;
-
if(*s == ']' && STTop(&ps) != '['||
-
*s == ')' && STTop(&ps) != '('||
-
*s == '}' && STTop(&ps) != '{')
-
{
-
SLDestroy(&ps);
-
return false;
-
}
-
STPop(&ps);
-
break;
-
}
-
s ;
-
}
-
//防止((出现
-
if(!STEmpty(&ps))
-
return false;
-
return true;
-
}
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgfaicb
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01