栈----数据结构

🔆栈的概念

• 栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。**进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。**栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
• 压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
• 出栈：栈的删除操作叫做出栈。出数据也在栈顶。

🔆栈的结构

🔆栈的实现

数组栈gitt代码链接

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

• 数组栈
  
• 链式栈
  

🔆括号匹配问题

OJ链接

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例一：

输入：s = “()”
输出：true

示例二：

输入：s = “()[]{}”
输出：true

示例三：

输入：s = “(]”
输出：false

• 解题思路：

• 答案：

//动态栈的实现
typedef char STDataType;typedef struct Stack {STDataType* a;//top 指向栈顶int top;//capacity表示栈的容量int capacity;
}ST;//创建栈
ST* STCreate() {ST* stack = (ST*)malloc(sizeof(ST));if (stack == NULL) {perror("malloc::");return NULL;}STInit(stack);return stack;
}//栈的初始化
void STInit(ST* ps) {assert(ps);ps->a = NULL;//top为-1时表示指向栈顶，top为0时表示指向栈顶的下一个ps->top = -1;ps->capacity = 0;
}//栈的判空
bool STEmpty(ST* ps) {assert(ps);return ps->top == -1;
}//栈的判满
bool STFull(ST* ps) {assert(ps);return (ps->top + 1 == ps->capacity);
}//入栈
void STPush(ST* ps, STDataType val) {assert(ps);if (STFull(ps)) {int newcapacity = ((ps->capacity == 0) ? 4 : (2 * ps->capacity));STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));if (tmp == NULL) {perror("realloc::");exit(-1);}ps->a = tmp;ps->capacity = newcapacity;}(ps->top)++;ps->a[ps->top] = val;
}//出栈
void STPop(ST* ps) {assert(ps);assert(!STEmpty(ps));(ps->top)--;
}//获取栈元素个数
int STSize(ST* ps) {assert(ps);return (ps->top) + 1;
}//获取栈顶元素
STDataType STTop(ST* ps) {assert(ps);return ps->a[ps->top];
}//销毁栈
void STDestroy(ST* ps) {assert(ps);free(ps->a);ps->a = NULL;ps->top = -1;ps->capacity = 0;free(ps);
}bool isValid(char* s){int len = strlen(s);if (len <= 1) {return false;}ST* st = STCreate();char* cur = s;while (*cur) {if (*cur == '(' || *cur == '[' || *cur == '{') {STPush(st, *cur);}else if (*cur == ')' || *cur ==']' || *cur == '}') {if (STEmpty(st) || (*cur == ')' && STTop(st) != '(') || (*cur == ']' && STTop(st) != '[') || (*cur == '}' && STTop(st) != '{')) {return false;}STPop(st);}cur++;}if (!STEmpty(st)) {return false;}STDestroy(st);st = NULL;return true;
}

🔆结语

到这里这篇博客已经结束啦。
这份博客👍如果对你有帮助，给博主一个免费的点赞以示鼓励欢迎各位🔎点赞👍评论收藏⭐️，谢谢！！！
如果有什么疑问或不同的见解，欢迎评论区留言欧👀