推广 高端网站设计,.我爱你 网站,广告买卖网,群晖服务器可做网站服务器么文章目录 一、物理结构和逻辑结构二、栈1、什么是栈2、栈中一些基本操作的实现Stack.hStack.c栈的初始化栈的销毁入栈出栈获得栈顶元素获得栈的元素数判断栈空 三、利用栈解决问题 一、物理结构和逻辑结构 栈和队列都属于逻辑结构#xff0c;它们既可以用数组实现也可以用链表… 文章目录 一、物理结构和逻辑结构二、栈1、什么是栈2、栈中一些基本操作的实现Stack.hStack.c栈的初始化栈的销毁入栈出栈获得栈顶元素获得栈的元素数判断栈空 三、利用栈解决问题 一、物理结构和逻辑结构 栈和队列都属于逻辑结构它们既可以用数组实现也可以用链表实现。
二、栈
1、什么是栈 栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出Last In First Out简称LIFO的原则。 进栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。 出栈栈的删除操作叫做出栈。出数据也在栈顶。 2、栈中一些基本操作的实现
利用数组来实现栈的基本操作 代码结构设计
Stack.h: 存放链表结构及需要用到的头文件函数声明等Stack.c: 各种操作函数的具体实现
Stack.h
#pragma once#include stdio.h
#include stdlib.h
#include assert.h
#includestdbool.h
//方便修改类型
typedef int STDataType;
//栈
typedef struct Stack
{STDataType* a;//实现栈的数组int top;//栈顶int capacity;//栈容量
}ST;//栈的初始化
void STInit(ST* ps);
//栈的销毁
void STDestroy(ST* ps);
//入栈
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);
//获得栈顶元素
STDataType STTop(ST* ps);
//获得栈的元素数
int STSize(ST* ps);
//判断栈空
bool STEmpty(ST* ps);Stack.c
#include Stack.h栈的初始化
void STInit(ST* ps)
{assert(ps);ps-a NULL;//栈顶元素的下一个ps-top 0;ps-capacity 0;
}栈的销毁
void STDestroy(ST* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-top 0;ps-capacity 0;
}入栈
void STPush(ST* ps, STDataType x)
{assert(ps);//空间不足扩容if (ps-capacity ps-top){int newCapacity ps-capacity 0 ? 4 : 2 * ps-capacity;STDataType* tmp (STDataType*)realloc(ps-a, sizeof(STDataType)*newCapacity);if (tmp NULL){perror(realloc fail);exit(-1);}ps-a tmp;ps-capacity newCapacity;}//更新入栈后内容ps-a[ps-top] x;ps-top;
}出栈
void STPop(ST* ps)
{assert(ps);assert(ps-top 0);ps-top--;
}获得栈顶元素
top初始化时是0是栈顶元素的下一个位置所以栈顶元素下标是top-1
STDataType STTop(ST* ps)
{assert(ps);assert(ps-top 0);return ps-a[ps-top - 1];
}获得栈的元素数
top从0开始栈内多一个元素它就加1所以top与元素树大小一致
int STSize(ST* ps)
{assert(ps);return ps-top;
}判断栈空
top等于0时栈空
bool STEmpty(ST* ps)
{return ps-top 0 ;
}三、利用栈解决问题
本题来自LeetCode有效的括号
有效的括号 示例1 输入s“( )” 输出true 示例2 输入s“( )[ ]{ }” 输出true 示例3 输入s“( ]” 输出false 1 s.length 104s 仅由括号 ‘( )[ ]{ }’ 组成
题目分析
对于这个题我们需要将字符串内括号的左一半与右一半进行匹配有( { [ ] })“、”( ) [ ] { }“等多种情况都是符合情况的也有像”( { ) }这种不符合情况的都需要考虑。如果是左括号则入栈如果是右括号取出栈顶元素与之匹配如果右边括号匹配时栈内已经空了则数量不匹配匹配结束后栈内不为空则数量不匹配
代码
这里我们用上面实现的栈操作来完成
bool isValid(char * s){ST st;STInit(st);char topval;while(*s){if(*s(||*s{||*s[){STPush(st,*s);}else{//如果栈内为空说明数量不匹配if(STEmpty(st)){STDestroy(st);return false;}//取出栈顶元素然后栈顶元素出栈topvalSTTop(st);STPop(st);//匹配不成功的情况if((*s)topval!()|| (*s}topval!{)|| (*s]topval