【栈与队列】——栈的实现及应用
目录
概念
栈
栈是一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。
压栈
栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
出栈
栈的删除操作叫做出栈。出数据也在栈顶。
总结起来,即栈是一种特殊的线性表,数据的插入以及删除操作都在栈顶,遵循后进先出的原则,即后进来的元素在进行出栈时先于早进来的元素。
栈的实现
这里我们发现,实现栈的话,用单链表或者数组都可以,单链表的头插与头删就满足后进先出,而数组即我们前面写过的顺序表,数组的尾插与尾删也满足后进先出的原则。这两种实现方式的时间复杂度都为O(1),并无什么差别,这里我们就用顺序表(数组)来实现。
// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
STDataType* _a;
int _top; // 栈顶
int _capacity; // 容量
}Stack;
初始化栈
首先是初始化,这里我们先初始化为一个容量为4的栈,
// 初始化栈
void StackInit(Stack* ps)
{
assert(ps);
ps->_a = (STDataType*)malloc(sizeof(STDataType)*4);
ps->_top = 0;//栈顶元素的下一个
ps->_capacity = 4;//栈的初始容量为4
}
这里需要注意的是,我们用_top来表示栈顶,_top== 0 和 top == -1是两个概念, 等于0时表示的是栈顶的下一个,等于-1时才表示栈顶。如下图: _top=-1
_top=0
注意两者区别即可。
入栈
接下来是入栈,这里我们由于是写的一个能动态增长的栈,所以我们再进行入元素之前,要先判断这个栈是否满了,如果满了的话,就要进行扩容。
// 入栈
void StackPush(Stack* ps, STDataType data)
{
assert(ps);
//判断增容
//_top==_capacity说明已经满了,要进行扩容
if (ps->_top == ps->_capacity)
{
//容量调整为原来的二倍
STDataType* tmp = realloc(ps->_a, 2 * ps->_capacity * sizeof(STDataType));
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);
}
ps->_a = tmp;
ps->_capacity *= 2;//记得更新_capacity
}
//接下来才是入栈,先入元素,_top再++。(假如_top初始化是-1的话,要先++,再入元素)
ps->_a[ps->_top] = data;
ps->_top++;
}
出栈
出栈的实现也很简单,就相当于数组尾删,直接_top- - 即可,不过要注意的是,假如栈是个空栈,就不能进行出栈操作了。这里我们用assert进行判断
// 出栈
void StackPop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));//判断是否为空
ps->_top--;
}
获取栈顶元素
这里需要注意的是,由于我们一开始初始化的_top=0,它表示的是栈顶的下一个元素,原因上面也已经解释过了,所以我们获取栈顶元素时的下标实际为_top-1,不过注意空栈是不能获取栈顶元素的。
// 获取栈顶元素
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->_a[ps->_top - 1];
}
获取栈中有效元素个数
我们的_top其实就表示了我们的元素个数,因为我们是从0开始的,进一个元素之前就++了,假如是从-1开始的话,有效元素个数应为_top+1个。
// 获取栈中有效元素个数
int StackSize(Stack* ps)
{
assert(ps);
return ps->_top;
}
判断栈是否为空
空栈就是_top等于0的情况下。
// 检测栈是否为空,如果为空返回true,否则false
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->_top == 0;
}
栈的销毁
释放malloc开辟的空间后,将所有元素置空置0
// 销毁栈
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->_a);
ps->_capacity = ps->_top = 0;
ps->_a = NULL;
}
栈的应用
有人可能会问,这个东西能干嘛啊,其实它的作用也很大的,就比如后面要学的一些知识,比如二叉树的层序遍历、快排的非递归实现等等,都会用得到,这里我们拿一道力扣上的题来举个应用例子。 题目如下:
对于该题,以我们的水平,假如不知道栈的话,做这个可能有点小麻烦,可能有人说用双指针遍历等等,其实都很难解决,但是用栈的特点,就很好做了。
我们直接左括号入栈,当遇到右括号时出栈进行匹配,这里就用到了后进先出的特点完美解决问题。如下:
代码实现:(由于这里我们是用C语言写的,不像C++等语言可以直接调用库来使用,所以该题我们要自己创造出一个栈,就用我们上面写的,同时由于是字符串类型,所以记得将typedef int 改为char类型…)
这里由于为了不再重复的占用字数,我只将实现的代码写在下面,上面栈的实现直接拷贝到该函数上面即可。
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->_a);
ps->_capacity = ps->_top = 0;
ps->_a = NULL;
}
bool isValid(char * s){
Stack st;
//初始化栈
StackInit(&st);
while(*s)
{
//左括号入栈
if(*s == '[' || *s=='('|| *s== '{')
{
StackPush(&st,*s);
s++;
}
else
{
//假如没有左括号,空栈
if(StackEmpty(&st))
{
return false;
}
//top存放栈顶元素
char top=StackTop(&st);
StackPop(&st);//出栈
//进行对比
if((*s==']'&& top !='[')
||(*s==')'&& top !='(')
||(*s=='}'&& top !='{'))
{
StackDestroy(&st);
return false;
}
else
{
s++;
}
}
}
//栈不为空
bool ret=StackEmpty(&st);
StackDestroy(&st);
return ret;
}
相关文章
- LibreOffice 7.5 发布:漂亮的新应用图标和酷炫功能
- elementary OS 7 发布
- Windows 应用兼容层 Wine 8.1 发布:默认启用“Windows 10”前缀
- 微软正测试新功能:当 Windows 11 有新的小组件可用时会提醒通知
- 解析分布式存储选型和应用九个典型问题
- ClickHouse在自助行为分析场景的实践应用
- Chrome DevTools 远程调试安卓网页的原理
- Uni-app + Vue3 页面如何跳转及传参?
- 微软证实系统还原点会损坏 Windows 11 22H2 版本应用程序
- 巧用 Transition 实现短视频 APP 点赞动画
- 初学者试试,HarmonyOS应用开发者基础认证
- 媒体实测微软 Windows 开发工具包 2023:存在不兼容 HDR 显示器、某些应用无法运行等问题
- 快速了解Navigator API SetAppBadge
- 微软 Windows 11 Dev 预览版 Build 25276 发布,应用兼容问题对话框 UI 改进
- 基于Next.js、Prisma、Postgres和Fastfy构建全栈APP
- 开始菜单搜索框变圆角,微软 Windows 11 Beta 预览版 22621.1095 和 22623.1095 发布
- 2022-2023 十大应用开发趋势
- 观远数据发布业内首部《移动BI白皮书》,深入业务数字化场景重新定义移动BI
- Windows 10 学院:不借助第三方工具如何卸载 Windows 10 预装应用
- 正处高质量发展期,我国大数据产业突破1.3万亿元