目录
1.栈的概念及结构
2.栈的实现
2.1 初始化栈
2.2 入栈
2.3 出栈
2.4 获取栈顶元素
2.5 获取栈中有效元素个数
2.6 检测栈是否为空,如果为空返回非零结果,如果不为空返回0
2.7 销毁栈
3. 完整代码
test.c
Stack.h
Stack.c
1.栈的概念及结构
栈(后进先出,先进后出):
一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作
进行数据插入和删除操作的一端 称为栈顶,另一端称为栈底
栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则
压栈:栈的插入操作叫做进栈/压栈/入栈。入数据在栈顶
出栈:栈的删除操作叫做出栈,出数据也在栈顶
在内存区域中也有一个区域叫做栈 ,它们一个是数据结构,一个是内存区域
2.栈的实现
栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小
// 下面是定长的静态栈的结构,实际中一般不实用,所以我们主要实现下面的支持动态增长的栈 typedef int STDataType; #define N 10 typedef struct Stack { STDataType a[N]; int top; // 栈顶 }ST; // 支持动态增长的栈 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->capacity = 0;//栈容量 // 如果top=0,表示top指向栈顶元素的下一个位置 pst->top = 0;//栈顶 // 如果top=-1,表示top指向栈顶元素 //pst->top = -1; }
在栈实现中top的初始值的选择是最关键的一点,top既可以初始化为0,也可以初始化为-1,如果top=0,表示top指向栈顶元素的下一个位置 ,如果top=-1,表示top指向栈顶元素,这里我们top取0,如果top取-1,下面的一些条件也要发生变化
2.2 入栈
void STPush(ST* pst, STDataType x) { //断言出现空指针 assert(pst); //判断空间大小是否足够,如果不够,则扩容 if (pst->capacity == pst->top) { //如果初始空间为0,则赋为4,如果不是则扩容为原来的2倍 int newcapacity = pst->capacity == 0 ? 4:pst->capacity * 2; //将扩容的新空间存起来 STDataType* tmp = realloc(pst->a, sizeof(newcapacity)*newcapacity); //判定新空间是否开辟成功 if (tmp == NULL) { perror("realloc fail"); return; } //将开辟的新空间和空间大小赋给a和capacity pst->a = tmp; pst->capacity = newcapacity; } //赋值 pst->a[pst->top] = x; pst->top++; }
注:数据结构中动态内存开辟非常重要,如果感觉不太熟悉的话可以看看我之前的文章(感谢支持!)C语言:动态内存管理-CSDN博客
2.3 出栈
void STPop(ST* pst) { 断言出现空指针 assert(pst); //这里top指向栈顶的下一个元素,top减一,看似没有删除元素,实则top已经指向要删除元素的下一个,要删除的元素变成了无效元素,从而达到删除的目的 pst->top--; }
这里top指向栈顶的下一个元素,top减一,看似没有删除元素,实则top已经指向要删除元素的下一个,要删除的元素变成了无效元素,从而达到删除的目的,这种思想以后我们在数据结构中会经常遇到 。
2.4 获取栈顶元素
STDataType STTop(ST* pst) { //断言出现空指针 assert(pst); return pst->a[pst->top - 1]; }
2.5 获取栈中有效元素个数
int STSize(ST* pst) { //断言出现空指针 assert(pst); return pst->top; }
2.6 检测栈是否为空,如果为空返回非零结果,如果不为空返回0
bool STEmpty(ST* pst) { //断言出现空指针 assert(pst); return pst->top == 0; }
2.7 销毁栈
void STDestroy(ST* pst) { //断言出现空指针 assert(pst); free(pst->a); pst->capacity = pst->top = 0; }
3. 完整代码
test.c
#include"Stack.h" int main() { ST s; STInit(&s); STPush(&s, 1); STPush(&s, 2); STPush(&s, 3); //printf("%d ", STTop(&s)); //STPop(&s); //printf("%d ", STTop(&s)); //STPop(&s); STPush(&s, 4); STPush(&s, 5); // 一 对 多 // 入栈顺序 -- 出栈顺序 while (!STEmpty(&s)) { printf("%d ", STTop(&s)); STPop(&s); } printf("\n"); return 0; }
Stack.h
#include#include #include #include 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);
Stack.c
#include "Stack.h" void STInit(ST* pst) { //断言出现空指针 assert(pst); pst->a = NULL; pst->capacity = 0;//栈容量 // 如果top=0,表示top指向栈顶元素的下一个位置 pst->top = 0;//栈顶 // 如果top=-1,表示top指向栈顶元素 //pst->top = -1; } void STDestroy(ST* pst) { //断言出现空指针 assert(pst); free(pst->a); pst->capacity = pst->top = 0; } // 栈顶插入删除 void STPush(ST* pst, STDataType x) { //断言出现空指针 assert(pst); //判断空间大小是否足够,如果不够,则扩容 if (pst->capacity == pst->top) { //如果初始空间为0,则赋为4,如果不是则扩容为原来的2倍 int newcapacity = pst->capacity == 0 ? 4:pst->capacity * 2; //将扩容的新空间存起来 STDataType* tmp = realloc(pst->a, sizeof(newcapacity)*newcapacity); //判定新空间是否开辟成功 if (tmp == NULL) { perror("realloc fail"); return; } //将开辟的新空间和空间大小赋给a和capacity pst->a = tmp; pst->capacity = newcapacity; } //赋值 pst->a[pst->top] = x; pst->top++; } void STPop(ST* pst) { //断言出现空指针 assert(pst); //这里top指向栈顶的下一个元素,top减一,看似没有删除元素,实则top已经指向要删除元素的下一个,要删除的元素变成了无效元素,从而达到删除的目的 pst->top--; } STDataType STTop(ST* pst) { //断言出现空指针 assert(pst); return pst->a[pst->top - 1]; } bool STEmpty(ST* pst) { //断言出现空指针 assert(pst); return pst->top == 0; } int STSize(ST* pst) { //断言出现空指针 assert(pst); return pst->top; }
感谢观看,希望能对你有所帮助 !