栈
- 1. 栈的概念和结构
- 2. 栈的实现
- 2.1 原型声明
- 2.2 初始化和销毁
- 2.3 入栈 出栈
- 2.4 取栈顶数据
- 2.5 判空
- 2.6 获取数据个数
- 3. 总结
🔥 博客主页: 偷心编程
🎥 系列专栏: 《Java学习》 《C语言学习》 《数据结构C语言版》
❤️ 感谢大家点赞👍收藏⭐评论✍️
1. 栈的概念和结构
栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守 后进先出LIFO(Last In First Out)的原则 。
压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
出栈:栈的删除操作叫做出栈。出数据也在栈顶。
我们在前面学习了“顺序表、单链表、双向链表”,在它们的结构原型下,我们都可以实现栈,但是相对来说,用顺序表实现栈会更好,因为顺序表可以很快的找到最后一个元素,进行“进栈”和“出栈”。
2. 栈的实现
2.1 原型声明
typedef int STDataType;typedef struct Stack
{STDataType* a;int top; //其实top就是顺序表里的size,刚好size就是栈顶的下一个元素int capacity;
}ST;
注意这里的top(栈顶),有两种处理方法。1. 等同于size,也就是栈中最后一个有效元素的一下个位置,严格意义上来说是栈顶的下一个元素;2. 就是栈顶,最后一个有效元素
对top的处理方法不同,我们在栈的初始化的时候也就不同,前者top要初始化为0;后者要初始化为-1
但是为了更好的契合顺序表,所以我们采用第一个处理方案(top=size)
2.2 初始化和销毁
// 初始化和销毁
void STInit(ST* pst)
{assert(pst);pst->a = NULL;pst->capacity = pst->top = 0;
}void STDestroy(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->capacity = pst->top = 0;
}
2.3 入栈 出栈
// 入栈
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,newcapacity * sizeof(STDataType));if (!tmp){perror("malloc:");exit(1);}pst->a = tmp;pst->capacity = newcapacity;}//处理一般情况pst->a[pst->top++] = x;
}
//出栈
void STPop(ST* pst)
{assert(pst);assert(pst->top != 0);pst->top--;
}
2.4 取栈顶数据
// 取栈顶数据
STDataType STTop(ST* pst)
{assert(pst);assert(pst->top != 0);return pst->a[pst->top - 1];
}
2.5 判空
// 判空
bool STEmpty(ST* pst)
{return pst->top == 0;
}
2.6 获取数据个数
// 获取数据个数
int STSize(ST* pst)
{return pst->top;
}
3. 总结
我们主要是学习好栈的结构特点——“后进先出”,我们可以用多种不同的方法来实现,但是用顺序表实现最简单。
我们为什么要定义这些接口呢,这是人们根据具体问题需要定义的,我们以后做的题目多了,自然会理解其用意。