🌈个人主页:秦jh__https://blog.csdn.net/qinjh_?spm=1010.2135.3001.5343
🔥 系列专栏:《数据结构》https://blog.csdn.net/qinjh_/category_12536791.html?spm=1001.2014.3001.5482
目录
前言
栈
栈的概念和结构
栈的实现
编辑
数组栈的实现
总的声明
初始化
插入
删除
取栈顶元素
销毁
判断是否为空
返回栈的大小
栈的一对多关系
不同的栈
前言
💬 hello! 各位铁子们大家好哇。
这是2023年的最后一篇博客啦。
🎉 欢迎大家关注🔍点赞👍收藏⭐️留言📝
栈
栈的概念和结构
栈的实现
栈有数组栈和链式栈。数据结构没有规定栈的实现要用数组还是链式,根据自身需要选择即可。
在数组栈中,左边是栈底,右边是栈顶。因为数组尾插尾删方便,也符合栈顶元素先出。
在用单链表实现时,栈顶只能是左边。因为单链表的头插头删方便。
数组栈的实现
总的声明
#include#include #include #include typedef int STDataType; typedef struct Stack { int* a; int top; //标识栈的位置 int capacity; }ST; void STInit(ST* pst); void STDestroy(ST* pst); //栈顶插入删除 void STPush(ST* pst, STDataType x); void STPop(ST* pst); STDataType STTop(ST* pst); bool STEmpty(ST* pst); int STSize(ST* pst);
初始化
void STInit(ST* pst) { assert(pst); pst->a = NULL; pst->capacity = 0; pst->top = 0; //pst->top = -1; }
上方代码中,pst->top可以初始化为0,也可以为-1。不过两种方法需要区分:
第一种
top指向栈顶元素,当top初始化为0时,会产生歧义,即当有一个数据或者为空时,top都等于0。
下面是解决方法:
分析:当它为空时,top==0。当有一个数据时,top==1,即top是指向栈顶元素的下一个位置。
如果我们想用这种方式实现数组栈,尾插时,就直接把x赋给top位置,然后再让top指向下一位置。
第二种:
分析:我们初始化top为-1,此时为空。当有一个数据时,top==0,刚好指向栈顶元素。尾插时,需要先让top指向下一位置,再插入元素。
两种方法都可以使用,这里我们使用初始化top为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, sizeof(STDataType) * newcapacity); if (tmp == NULL) { perror("realloc fail"); return; } pst->a = tmp; pst->capacity = newcapacity; } pst->a[pst->top] = x; pst->top++; }
删除
void STPop(ST* pst) { assert(pst); assert(pst->top > 0); pst->top--; }
取栈顶元素
STDataType STTop(ST* pst) { assert(pst); assert(pst->top > 0); return pst->a[pst->top - 1]; }
销毁
void STDestroy(ST* pst) { free(pst->a); pst->a = NULL; pst->capacity = pst->top = 0; }
判断是否为空
bool STEmpty(ST* pst) { assert(pst); //if (pst->top == 0) //{ // return true; //} //else //{ // return false; //} return pst->top == 0; }
返回栈的大小
int STSize(ST* pst) { assert(pst); return pst->top; }
栈的一对多关系
如上图,我们的入栈顺序是123456,出栈顺序是346521。可知入栈顺序和出栈顺序是一对多的关系。入栈顺序只有一种,但出栈的顺序是多样的,不过出栈顺序也要符合先出栈顶元素,不是想出啥就出啥 。
不同的栈
栈有两种,一种是数据结构的栈,一种是内存区域的栈。我们这里的栈是数据结构的栈。而我们所说的栈溢出是指内存区域的栈,在递归中,返回条件出现问题时,容易出现栈溢出。