目录
1. 栈
编辑
1.2 栈的实现
2. 代码的实现
2.1 初始化栈和销毁栈
2.2栈顶元素的插入
2.3栈顶元素的删除
栈元素删除
2.4栈顶元素的获取和栈元素的个数
1. 栈
1.1 栈的概念和结构
栈(Stack)是一种线性存储结构,它具有如下特点:
(1)栈中的数据元素遵守”先进后出”(First In Last Out)的原则,简称FILO结构。
(2)限定只能在栈顶进行插入和删除操作。
压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
出栈:栈的删除操作叫做出栈。出数据也在栈顶
注意:我们在进行数据插入和删除操作中,都是在栈顶实现的,而另一端叫做栈底。
我们借用一下这个图来说明:
1.2 栈的实现
我们这里可以通过两种方法实现,顺序表或链表。
这里我们会发现链表要尾插或者尾删需要便利一遍链表,效率低;顺序表尾插尾删很快,但是还要解决扩容问题。
所以这里我们就引出了栈这个东西
2. 代码的实现
这里我们需要说明一下,之前我们在实现链表或者顺序表双向链表中都用的是size,为了更好的明确个数。
这里top指的是栈顶元素,如果初始化为 ” -1 “ ,指的是栈顶元素;如果为 “ 0 ” ,指的是栈顶的下一个元素。
这里面我建议是初始化为0:
- top还可以表示元素的个数,可以用来判断栈是否满了
- 插入元素的时候直接在top的位置插入就行,然后再top++即可
废话不多先来个头文件
typedef 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);
STDataType STTop(ST* pst);
bool STEmpty(ST* pst);
int STSize(ST* pst);
2.1 初始化栈和销毁栈
我们首先要检查一下结构体是否为空,这里我们要注意一下
void STInit(ST* pst)
{
assert(pst);
pst->a = NULL;
//pst->top = -1; // top 指向栈顶数据
pst->top = 0; // top 指向栈顶数据的下一个位置
pst->capacity = 0;
}
这里我们断言结构体不为空在继续,释放我们开辟的空间,将其他数据置为0
void STDestroy(ST* pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
pst->top = pst->capacity = 0;
}
2.2栈顶元素的插入
这里面我们要判断储存空间是否足够,如果没有开辟,我们可以先开辟一些空间出来;如果栈空间满了,直接将栈空间扩大二倍
void STPush(ST* pst, STDataType x)
{
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");
return;
}
pst->a = tmp;
pst->capacity = newCapacity;
}
pst->a[pst->top] = x;
pst->top++;
}
2.3栈顶元素的删除
注意:当top为0,代表我们没有元素,不能再减下去,需要一个函数判断一下
判断函数
bool STEmpty(ST* pst)
{
assert(pst);
/*if (pst->top == 0)
{
return true;
}
else
{
return false;
}*/
return pst->top == 0;
}
栈元素删除
void STPop(ST* pst)
{
assert(pst);
assert(!STEmpty(pst));
pst->top--;
}
2.4栈顶元素的获取和栈元素的个数
这里面我们初始化为0,所以我们返回栈顶元素前一个元素即可;如果为空,需要我们断言一下
STDataType STTop(ST* pst)
{
assert(pst);
assert(!STEmpty(pst));
return pst->a[pst->top - 1];
}
元素个数文章来源:https://www.toymoban.com/news/detail-456525.html
int STSize(ST* pst)
{
assert(pst);
return pst->top;
}
以上就是今天栈实现的分享,如果喜欢的话请三联支持一下吧,感谢你的收看,我们下期再见!!!文章来源地址https://www.toymoban.com/news/detail-456525.html
到了这里,关于(数据结构)栈的实现——再一次保姆级教学的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!