广州网站制作工作室,商城图片,新网站建设流程,网页域名解析错误前言#xff1a;哈喽小伙伴们#xff0c;今天我们将一起进入数据结构线性表的第四篇章——栈的讲解#xff0c;栈还是比较简单的哦#xff0c;跟紧博主的思路#xff0c;不要掉队哦。 目录
一.什么是栈
二.如何实现栈
三.栈的实现
栈的初始化
四.栈的操作
1.数据入栈…前言哈喽小伙伴们今天我们将一起进入数据结构线性表的第四篇章——栈的讲解栈还是比较简单的哦跟紧博主的思路不要掉队哦。 目录
一.什么是栈
二.如何实现栈
三.栈的实现
栈的初始化
四.栈的操作
1.数据入栈
2.数据出栈
3.返回栈顶数据
4.判断空栈
5.销毁栈
6.测试栈
五.完整代码展示
1.Stack.h
2.Stack.c
3.test.c
六.总结 一.什么是栈
栈其实是一种特殊的线性表他只允许在线性表固定的一端进行插入和删除元素的操作。
进行插入和删除的一端称为栈顶另一端则称为栈底。
栈中的元素遵循后进先出的原则。
其中有两个对栈中元素进行操作的专业名词
压栈栈的插入操作也可以叫入栈或进栈入数据在栈顶。出栈栈的删除操作叫做出栈出数据也在栈顶。 二.如何实现栈
经过我们前边的学习我们已经掌握了数据结构实现的两种方式数组和链表。
那么对于栈我们是用数组还是用链表呢不妨来分析一下
关于栈的操作主要是要方便栈顶的操作。
如果是数组栈 数组可以直接通过下标来实现访问方便快捷。
如果是单链表栈 如果追求高效就需要让单链表的头作为栈顶因为单链表的尾部操作比较复杂。
如果是双链表栈那么无论头尾都可。但是双链表的设计更加麻烦空间占用也更大。
综合全局因素考虑用数组实现栈是最合适的。 三.栈的实现
栈的初始化
//初始化
void StackInit(ST* pst)
{assert(pst);pst-data NULL;pst-capacity 0;pst-top -1;
}
栈的初始化和顺序表一样但是不同于顺序表的是栈需要一个top表示栈顶的当前位置方便对栈顶数据的操作。
值得注意的是栈是以数组为基础的而数组的下标是从0开始的所以我们如果想让top指向当前栈顶的位置就要初始化为-1这样每输入一个数据top就可以完全等同于数组下标啦。 四.栈的操作
1.数据入栈
数据入栈之前我们还是要提前判断一下栈当前空间是否已满满了则扩容
//数据入栈
void StackPush(ST* pst, STDataType x)
{assert(pst);if (pst-top 1 pst-capacity){int newcapacity pst-capacity 0 ? 4 : pst-capacity * 2;STDataType* tmp (STDataType*)realloc(pst-data, sizeof(STDataType) * newcapacity);if (tmp NULL){perror(StackBush-realloc);exit(-1);}pst-data tmp;pst-capacity newcapacity;}pst-data[pst-top 1] x;pst-top;
}
这些操作我们都已经很熟悉了唯一值得注意的就是对top当前值的判断及后续操作。 2.数据出栈
//数据出栈
void StackPop(ST* pst)
{assert(pst);assert(pst-top 0);pst-top--;
}
出栈就很简单了要注意的就是要断言一下是否为空栈。 3.返回栈顶数据
//返回栈顶数据
STDataType StackTop(ST* pst)
{assert(pst);assert(pst-top 0);return pst-data[pst-top];
}
同样需要断言一下是否为空栈。 4.判断空栈
//判断空栈
bool StackEmpty(ST* pst)
{assert(pst);if (pst-top 0){return true;}else{return false;}
}
这里我们造一个函数来判断栈是否为空并返回bool型数据用于我们后续遍历栈的操作。 5.销毁栈
//销毁栈
void StackDestroy(ST* pst)
{assert(pst);free(pst-data);pst-data NULL;pst-capacity 0;pst-top -1;
}
销毁也是不变的操作将所有数据复原。 6.测试栈
是的栈总共就上边的5种基础操作方式因为栈仅允许在栈顶操作数据所以没有任意位置的入栈出栈这些操作。
下面我们就来测试
int main()
{ST st;StackInit(st);StackPush(st, 1);StackPush(st, 2);StackPush(st, 3);StackPush(st, 4);while (StackEmpty(st)){STDataType top StackTop(st);printf(%d , top);StackPop(st);}StackDestroy(st);return 0;
}
能够看出我们直接将所有的操作整合在一起。
想要遍历栈的数据就需要返回一个栈顶数据就让它出栈再进行循环出栈直到栈为空也就是while循环的判断条件。
结果如下 五.完整代码展示
1.Stack.h
#includestdio.h
#includeassert.h
#includestdlib.h
#includestdbool.htypedef int STDataType;typedef struct Stack
{STDataType* data;int top;int capacity;
}ST;
//初始化
void StackInit(ST* pst);
//入栈
void StackPush(ST* pst, STDataType x);
//出栈
void StackPop(ST* pst);
//栈顶数据
STDataType StackTop(ST* pst);
//判断空栈
bool StackEmpty(ST* pst);
//销毁栈
void StackDestroy(ST* pst); 2.Stack.c
#include Stack.h//初始化
void StackInit(ST* pst)
{assert(pst);pst-data NULL;pst-capacity 0;pst-top -1;
}
//入栈
void StackPush(ST* pst, STDataType x)
{assert(pst);if (pst-top 1 pst-capacity){int newcapacity pst-capacity 0 ? 4 : pst-capacity * 2;STDataType* tmp (STDataType*)realloc(pst-data, sizeof(STDataType) * newcapacity);if (tmp NULL){perror(StackBush-realloc);exit(-1);}pst-data tmp;pst-capacity newcapacity;}pst-data[pst-top 1] x;pst-top;
}
//出栈
void StackPop(ST* pst)
{assert(pst);assert(pst-top 0);pst-top--;
}
//栈顶数据
STDataType StackTop(ST* pst)
{assert(pst);assert(pst-top 0);return pst-data[pst-top];
}
//判断空栈
bool StackEmpty(ST* pst)
{assert(pst);if (pst-top 0){return true;}else{return false;}
}
//销毁栈
void StackDestroy(ST* pst)
{assert(pst);free(pst-data);pst-data NULL;pst-capacity 0;pst-top -1;
} 3.test.c
#include Stack.h
int main()
{ST st;StackInit(st);StackPush(st, 1);StacKPush(st, 2);StackPush(st, 3);StackPush(st, 4);while (StackEmpty(st)){STDataType top StackTop(st);printf(%d , top);StackPop(st);}StackDestroy(st);return 0;
} 六.总结
栈就是在顺序表的基础上进行一些整改如果顺序表小伙伴们已经掌握那么栈就是小趴菜
最后喜欢博主文章的小伙伴不要忘记一键三连哦
我们下期再见啦
