国外怎么做直播网站,广州seo好找工作吗,wordpress多说读者墙,网站建设工程师工资文章目录 前言一、栈的概念二、栈的代码实现Stack.hStack.c 三、使用栈解决有效的括号问题总结 前言
小伙伴们#xff0c;大家好哇#xff01;#xff01;欢迎来到我的博客#xff01; 今天来分享一下另外一种数据结构—栈。主要包括栈的基本概念与其代码实现#xff0c… 文章目录 前言一、栈的概念二、栈的代码实现Stack.hStack.c 三、使用栈解决有效的括号问题总结 前言
小伙伴们大家好哇欢迎来到我的博客 今天来分享一下另外一种数据结构—栈。主要包括栈的基本概念与其代码实现最后使用该数据结构巧妙地解决一道算法题。
一、栈的概念
栈stack是一种特殊的线性表它只允许从一段插入删除数据进行插入删除操作的一端称为栈顶另一端则称之为栈底。所以栈中的数据始终遵从先进后出 LINOLast In First Out的原则。
看到这小伙伴们可能会联想到一些日常生活中的例子比如一包抽纸我们每次抽出的纸肯定是最顶部一张逐渐往下抽直到抽到底这里的顶部便相当于栈顶而底部则相当于栈底。而且在纸巾实际放入包装袋中也是从底部开始放进去的。 又比如一个装了东西的箱子我们要取出其中的物品肯定是要从最上面的东西开始拿出当然也不排除有些人将箱子里的东西全部暴力地倒出直到找到自己要找的。 而像前面的插入数据的操作就叫压栈也可以叫入栈或进栈删除数据的操作则是出栈在栈中插入与删除数据的位置都是栈顶。
二、栈的代码实现
讲完了栈的基本概念与思想那么就又到了紧张刺激手撕代码的时间了。 但在实现栈之前我们应思考一下应使用数组还是链表实现 其实栈一般既可以使用数组也可以使用链表实现。但相对而言使用数组结构实现更优。因为数组在尾部插入数据的代价更小。
那么接下来就让我们使用数组来手搓一个栈吧
Stack.h
首先是栈的结构体声明与之前的顺序表【数据结构—顺序表C语言实现】类似的是我们当然可以使用静态栈的结构即在声明是确定数组的长度但这种栈在实际中并不实用
typedef int STDataType;
#define N 10
typedef struct Stack
{STDataType _a[N];int _top; // 栈顶
}Stack;所以我们依然是要实现可以支持动态增长的栈
typedef int STDataType;typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;然后是头文件包含与栈的结构体声明top指向栈顶元素
#pragma once#include stdio.h
#include assert.h
#include stdlib.h
#include stdbool.htypedef int STDataType;typedef struct Stack
{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);Stack.c
接下来就是栈的增删查改的基本方法的实现了 首先最为基本的当然是栈的头文件包含了
#include Stack.h然后是栈的初始化与销毁
void STInit(ST* pst)
{assert(pst);pst-a NULL;pst-top 0;pst-capacity 0;
}void STDestroy(ST* pst)
{assert(pst pst-capacity);free(pst-a);pst-a NULL;pst-top pst-capacity 0;
}入栈这里我们使用与之前顺序表相同的方法对栈进行扩容
void STPush(ST* pst, STDataType x)
{assert(pst);if (pst-top pst-capacity){int newcapacity pst-capacity 0 ? 4 : pst-capacity * 2;STDataType* tmp (STDataType*)realloc(pst-a, newcapacity * sizeof(STDataType));if (tmp NULL){perror(realloc fail!);exit(1);}pst-a tmp;pst-capacity newcapacity;}pst-a[pst-top] x;pst-top;
}使用动画解释入栈操作 出栈这就非常简单了只需要将栈的size–即可
void STPop(ST* pst)
{assert(pst pst-top);pst-top--;
}动画解释出栈操作由于只是将size–实际上栈中的数据并没有消失 最后就是栈的判空获取栈顶数据获取栈的数据大小这里就很简单了基本一行代码即可解决
bool STEmpty(ST* pst)
{assert(pst);return pst-top 0;
}STDataType STTop(ST* pst)
{assert(pst pst-top);return pst-a[pst-top - 1];
}int STSize(ST* pst)
{assert(pst);return pst-top;
}三、使用栈解决有效的括号问题
讲完了栈的数据结构接下来我们就可以使用栈的特性来巧妙地解决一道力扣上的算法题附上题目链接有效的括号。 由题意可知与我们日常学习可知只有最近的两括号是同种比如都是花括号{}并且前一个是左括号而后一个是右括号才能称之为有效的括号。
此时就是栈这一数据结构的回合了我们可以先判断第一个字符是否为左括号是就直接让该括号入栈然后判断下一个字符是左括号就入栈不是则说明是右括号这时就需要判断这个右括号与栈顶的括号是否匹配匹配就让栈顶出栈否则就直接返回false。但在判断第一个字符时是可能就为右括号的此时我们就需要在判断括号是否匹配之前对栈进行判空操作并返回false。而这些出栈与入栈的操作肯定是需要放到一个循环中的。 然后在出了循环我们就只需要判断此时栈中是否为空即可为空就说明所有的括号都匹配。
接下来就是关于这道题的代码实现了。由于我们使用的是C语言解决我们肯定需要在首先主逻辑之前手搓一个栈。但是如果我们已经在编译器中实现了一个栈那我们就可以直接使用CV大法10秒内完成当然没有实现过栈的小伙伴最好在做这题前手撕一个栈有助于对栈的理解
以下是题中的主要逻辑部分的代码当然在这之前肯定得包含栈的实现代码
bool isValid(char* s) {ST st;STInit(st);while (*s){if (*s ( || *s [ || *s {) STPush(st, *s);else{if (STEmpty(st)){STDestroy(st);return false;}if (STTop(st) ( *s ! ) ||STTop(st) [ *s ! ] ||STTop(st) { *s ! }){STDestroy(st);return false;}STPop(st);}s;}bool ret STEmpty(st);STDestroy(st);return ret;
}总结
以上就是有关栈这一数据结构的问题分享如果觉得对你有帮助的话希望小伙伴们可以点点“栈”赞 ☆*: .. o(≧▽≦)o ..:*☆
