前言
在之前的数据结构学习中,我们学习了顺序表、链表这两种结构
- 顺序表:博客链接1
- 单链表:博客链接2
- 链表OJ:博客链接3
除了单链表以外,还有一个结构,是双向带头循环链表
。这个链表的形式如下
- 头节点的prev指向尾部节点
- 尾节点的next指向头节点,构成循环
别看它的形式有些复杂,实际代码的实现,比单链表还简单!
因为head->prev
指向了尾节点,所以不需要找尾。尾删的时候也不需要遍历找尾节点的前一位,因为尾节点的prev就存放了前一位的地址。
所以这里就偷懒不写博客了!反正也没啥人看😭
好吧,最后我还是写了一篇水文👉点我
本篇博客讲述的是另外一个特别的线性表,栈
1.什么是栈
数据结构里的栈,和函数栈帧中的“栈”有一定相似,但实际上它们完全不同
栈作为一个特殊的线性表,它只允许在表的一头添加、删除数据。
所有的数据都遵循先进后出,后进先出
的原则
- 压栈:栈的插入操作叫做进栈/压栈/入栈,新的数据存放在栈顶
- 出栈:栈的删除操作,先删除栈顶的数据
2.栈的实现
栈可以用数组或者链表来实现,相对而言,数组的方法更优
因为数组在尾插数据的时候,可以很方便的找到尾。而单链表需要遍历找尾,耗时较长。
是不是有些似曾相识呢?没错,实际上栈区就是一个只能尾插+尾删的顺序表
3.敲代码!
3.1头文件
先用头文件写好咱们的大纲,然后在来一一实现这些代码
#include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> // 支持动态增长的栈 typedef int STDataType; typedef struct Stack {
STDataType* a; int top; // 栈顶 int capacity; // 容量 }Stack; // 初始化栈 void StackInit(Stack* ps); // 销毁栈 void StackDestroy(Stack* ps); // 入栈 void StackPush(Stack* ps, STDataType data); // 出栈 void StackPop(Stack* ps); // 获取栈顶素 STDataType StackTop(Stack* ps); // 获取栈中有效素个数 int StackSize(Stack* ps); // 检测栈是否为空,如果为空返回false,如果不为空返回true bool StackEmpty(Stack* ps); //打印 void StackPrint(Stack* ps);
和顺序表不同的是,我们需要写一个单独的函数来获取栈顶素,这一点在很多OJ题目中都需要用到。
3.2函数实现
如果你看过了我之前顺序表的博客,这部分对你来说想必不难。
如果有什么问题,欢迎在评论区提出!
#include"Stack.h" // 初始化 void StackInit(Stack* ps) {
STDataType* new = (STDataType*)malloc(4*sizeof(STDataType) ); if (new == NULL) exit(-1); else {
ps->a = new; ps->top = 0; ps->capacity = 4; } } // 销毁栈 void StackDestroy(Stack* ps) {
assert(ps); free(ps->a); ps->a = NULL; ps->capacity = 0; ps->top = 0; } // 入栈 void StackPush(Stack* ps, STDataType data) {
assert(ps); if (ps->top == ps->capacity)//容量检查 {
STDataType* new = (STDataType*)realloc(ps->a, sizeof(STDataType) * (ps->capacity) * 2); if (new == NULL) {
exit(-1); } else {
ps->a = new; ps->capacity *= 2; } } ps->a[ps->top] = data; ps->top++; } // 出栈 void StackPop(Stack* ps) {
assert(ps); if (ps->top > 0) (ps->top)--; } // 获取栈顶素 STDataType StackTop(Stack* ps) {
assert(ps); assert(ps->top > 0); return ps->a[ps->top - 1]; } // 获取栈中有效素个数 int StackSize(Stack* ps) {
assert(ps); return ps->top; } // 检测栈是否为空,如果为空返回true,如果不为空返回false bool StackEmpty(Stack* ps) {
assert(ps); if (ps->top == 0) return true; else return false; } void StackPrint(Stack* ps) {
assert(ps); int n = ps->top; for (int i = 0; i < n; i++) {
printf("%d ", ps->a[i]); } printf("\n"); }
大家在自己编写这种带多个板块的代码的时候,一定要一个板块写完就检查一遍!不要将问题都丢一块解决,那样会非常难受的!
在其他版块都确认无误之后,也要过来瞅一眼Destroy板块,避免出现free错误等情况。
这个板块我们可以通过打断点(VS快捷键F9)并调试的方法来检查该板块是否正确
4.知识巩固,来道OJ!
leetcode:20. 有效的括号
这道题就是一道非常使用用栈来解决的OJ题
题目要求我们判断给出的字符串中,括号是否一一对应
{
[]}//对应 {
[(])}//不对应 {
{
()}//少了一个右边括号,不对应
具体要怎么做呢?思路如下:
- 用一个指针来遍历字符串,如果是左括号
{([
其中一个,就入栈 - 如果是右边括号,说明左括号已经入栈完毕,开始比对
- 栈顶的括号一定是和当前右括号匹配的,如果不是则为false
- 每判断一次,就让栈顶的左括号出栈一次
最后的函数实现如下
需要注意的是,STDataType类型需要更改为char类型,此时存放的是括号字符,并不是数字
typedef char STDataType; typedef struct Stack {
STDataType* a; int top; // 栈顶 int capacity; // 容量 }Stack; // 初始化 void StackInit(Stack* ps) {
STDataType* new = (STDataType*)malloc(sizeof(STDataType) * 4); if (new == NULL) {
exit(-1); } else {
ps->a = new; ps->top = 0; ps->capacity = 4; } } // 销毁栈 void StackDestroy(Stack* ps) {
assert(ps); free(ps->a); ps->a = NULL; ps->capacity = 0; ps->top = 0; } // 入栈 void StackPush(Stack* ps, STDataType data) {
assert(ps); if (ps->top == ps->capacity) {
STDataType* new = (STDataType*)realloc(ps->a, sizeof(STDataType) * (ps->capacity) * 2); if (new == NULL) {
exit(-1); } else {
ps->a = new; ps->capacity *= 2; } } ps->a[ps->top] = data; ps->top++; } // 出栈 void StackPop(Stack* ps) {
assert(ps); if (ps->top > 0) (ps->top)--; } // 获取栈顶素 STDataType StackTop(Stack* ps) {
assert(ps); assert(ps->top > 0); return ps->a[ps->top - 1]; } // 检测栈是否为空,如果为空返回true,如果不为空返回false bool StackEmpty(Stack* ps) {
assert(ps); if (ps->top == 0) return true; else return false; } bool isValid(char * s){
Stack st; StackInit(&st); while(*s) {
if(*s=='{'||*s=='['||*s=='(') {
StackPush(&st,*s); s++; } else {
if(StackEmpty(&st)) {
return false; } char top=StackTop(&st);//取栈顶素 StackPop(&st);//把栈顶删除 //如( { 这两个,取了栈顶{,就立马pop掉它 if((*s=='}'&&top=='{') ||(*s==')'&&top=='(') ||(*s==']'&&top=='[')) {
s++; } else {
StackDestroy(&st); return false; } } } bool ret=StackEmpty(&st); //如果为空,说明匹配完毕;非空说明还有剩下的左括号 StackDestroy(&st); return ret; }
这个算法的用时还是非常短的!
结语
数据结构学到这里,其实在了解完这些结构的真正思路后,代码的实现反而并不是那么重要。
在学习这部分知识的时候,一定要多画图!
如果你不适应用鼠标画图,可以直接用纸笔画,一些非常简单的草图,也能极大帮助我们理解当前的代码,找出问题👍
今天的文章 【C语言】数据结构-栈(顺序表实现)分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/bian-cheng-ji-chu/85963.html