文章目录
- 前言
- 一、什么是栈?
-
二、栈的实现
- 1.栈的结构
- 2.栈的接口实现过程
- 总结
前言
栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。
一、什么是栈?
栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。
进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。
栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。
压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
出栈:栈的删除操作叫做出栈。出数据也在栈顶。
二、栈的实现
1.栈的结构
//栈--用数组实现,后进先出
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;//栈元素的下标
int capacity;//栈元素的个数
}ST;
栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
2.栈的接口
1.初始化
//初始化
void STInit(ST* pst)
{
assert(pst);
pst->a = (STDataType*)malloc(sizeof(STDataType) * 4);
if (pst->a == NULL)
{
perror("malloc fail");
return;
}
pst->capacity = 4;
//top不同的初始化方式导致了不同的栈顶元素下标的表示
//1.top初始化为0,则最终top代表栈顶元素的下一个位置的下标
//2.top初始化为-1,则最终top代表栈顶元素的下标
pst->top = 0;
}
2. 销毁
//销毁
void STDestroy(ST* pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
pst->top = pst->capacity = 0;
}
3. 插入--入栈
//扩容
void CheckCapacity(ST* pst)
{
assert(pst);
if (pst->top == pst->capacity)
{
STDataType* tmp = (STDataType*)realloc
(pst->a, sizeof(STDataType) * pst->capacity * 2);
if (tmp == NULL)
{
perror("realloc fail");
return;
}
pst->a = tmp;
pst->capacity *= 2;
}
}
//插入数据
void STPush(ST* pst, STDataType x)
{
assert(pst);
CheckCapacity(pst);
pst->a[pst->top] = x;
pst->top++;
}
插入数据,需要对数组容量进行判断,检测是否需要进行扩容
4. 删除--出栈
//判空
bool STEmpty(ST* pst)
{
//空的话,返回true
assert(pst);
return pst->top == 0;
}
//删除
void STPop(ST* pst)
{
assert(pst);
//空的栈,不能删除
assert(STEmpty(pst) != true);
pst->top--;
}
删除一般配合判空使用,因为空的栈无法进行删除操作
5. 返回栈顶元素
//返回栈顶元素
STDataType STTop(ST* pst)
{
assert(pst);
//空的栈不能返回
assert(STEmpty(pst) != true);
STDataType ret = pst->a[pst->top - 1];
return ret;
}
top不同的初始化方式导致了不同的栈顶元素下标的表示
1.top初始化为0,则最终top代表栈顶元素的下一个位置的下标
2.top初始化为-1,则最终top代表栈顶元素的下标
6.返回元素个数及打印
//返回元素个数
int STSize(ST* pst)
{
assert(pst);
//top初始化为0,则最终top代表栈顶元素的下一个位置的下标
//同时,也代表前面的元素的个数
return pst->top;
}
//打印
void Print(ST* pst)
{
while (!STEmpty(pst))
{
printf("%d ", STTop(pst));
STPop(pst);
}
printf("\n");
}
栈的性质,导致其无法进行普通的打印,需要利用其接口实现文章来源:https://www.toymoban.com/news/detail-434710.html
总结
栈,数据结构的基本结构,它的特殊性质,导致其有着独特的使用场景,后进先出的方式,适用于各种情境,身为学习者的我们,需要充分了解其接口的实现,做到可以独立完成其复刻过程。文章来源地址https://www.toymoban.com/news/detail-434710.html
到了这里,关于数据结构---栈的实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!