专门做旅游尾单的网站,ins做甜品网站,类似于百度快照的网站,搜索引擎排名20211.概念 压栈#xff1a;栈的插入操作叫做进栈/压栈/入栈#xff0c;入数据在栈顶。出栈#xff1a;栈的删除操作叫做出栈#xff0c;出数据也在栈顶。栈的元素遵循后进先出LIFO(Last In First Out)的原则。后面进来的数据先出去
2.栈的实现
三种实现方法#xff0c;数组…1.概念 压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。出栈栈的删除操作叫做出栈出数据也在栈顶。栈的元素遵循后进先出LIFO(Last In First Out)的原则。后面进来的数据先出去
2.栈的实现
三种实现方法数组单链表双链表这里我们采用数组因为数组的缓存利用率高而且基于结构更加容易访问异地扩容的时候会消耗时间但是这个开销对于栈来说很小。双链表虽然很方便有前后指针但是要多维护一个指针同时也会增加空间的浪费那还不然单链表。分为三个部分Stack.h 和 Stack.c 还有test.c;这里只说Stack.c的核心部分栈的基本结构
typedef struct Stack
{STDataType* pa;//数组int top;//栈顶int capacity;//有效个数
}ST;
2.1初始化销毁
这里的关键问题点在于初始化为0(下标位置) 的时候你要不要放入数据可是初始化本来就不用放数据在top位置放数据的时候需要 top指向下一个地方为下一个准备放数据 //初始化
void STInit(ST* ps)
{assert(ps);ps-pa NULL;ps-top ps-capacity 0;
}//销毁
void STDestroy(ST* ps)
{assert(ps);ps-top ps-capacity 0;free(ps);//删除元素不行销毁因为数组的空间是一次性开辟的ps NULL;
}
2.2压栈(push)删除(pop)
压栈就是插入到数组后面再插入之前需要看看有没有空间就在结构体里面的ps-size插入就行假如是2刚好放到数组下标2位置处防止数据丢失不要直接空间给ps-pa,而是先拿个tmp的临时空间来装着。如果还是不太熟悉看看我的单链表这篇文章更加详细
//压栈
void STPush(ST* ps,STDataType x)
{assert(ps);//为NULL你插入个屁if (ps-top ps-capacity)//相等说明没空间{int new ps-capacity 0 ? 4 : ps-capacity * 2;STDataType* tmp (STDataType*)realloc(ps-pa,sizeof(STDataType) * new);//假如pa 为NULL则 和malloc一样if (tmp NULL){perror(STPush()::realloc());return;}//不要让ps-pa 直接去接收新空间的地址ps-pa tmp;ps-capacity new;}ps-pa[ps-top] x;ps-top;
}
pop只有一行可不可不调用函数删除数据呢不行因为没有断言检查了这里直接有效个数top-- 就行入栈顺序不代表出栈顺寻可以边进变出或者入3个在途中出两个进栈顺序只有一种出栈顺序有很多种
//删除
void STPop(ST* ps)
{assert(ps);assert(ps-top);//为0 不能删了ps-top--;
}
2.3有效个数(size),栈顶数据(top)栈是否为NULLempty
//有效个数
int STSize(ST* ps)
{assert(ps);return ps-top;
}
//取栈顶元素
STDataType STTop(ST* ps)
{assert(ps);assert(ps-top 0);//不大于0你还怎么取栈顶元素return ps-pa[ps-top - 1];//因为是有效元素的前一个
}
bool STEmpty(ST* ps)
{assert(ps);return ps-top 0;//表达式为真返回1假返回0
}
2.4完整代码
2.4.1Stack.h
#define _CRT_SECURE_NO_WARNINGS 1
#include stdio.h
#include assert.h
#include stdlib.h
#include stdbool.h
//可任意更换类型
typedef int STDataType;
typedef struct Stack
{STDataType* pa;//数组int top;//栈顶int capacity;//有效个数
}ST;//初始化和销毁
void STInit(ST* ps);
void STDestroy(ST* ps);//压栈和出栈
void STPush(ST* ps, STDataType x);
void STPop(ST* ps);//栈顶元素
STDataType STTop(ST* ps);//有效个数
int STSize(ST* ps);//判断是否为NULL
bool STEmpty(ST* ps);
2.4.2Stack.c
#include Stack.h
//初始化
void STInit(ST* ps)
{assert(ps);ps-pa NULL;ps-top ps-capacity 0;
}//压栈
void STPush(ST* ps,STDataType x)
{assert(ps);//为NULL你插入个屁if (ps-top ps-capacity)//相等说明没空间{int new ps-capacity 0 ? 4 : ps-capacity * 2;STDataType* tmp (STDataType*)realloc(ps-pa,sizeof(STDataType) * new);//假如pa 为NULL则 和malloc一样if (tmp NULL){perror(STPush()::realloc());return;}//不要让ps-pa 直接去接收新空间的地址ps-pa tmp;ps-capacity new;}ps-pa[ps-top] x;ps-top;
}
//删除
void STPop(ST* ps)
{assert(ps);assert(ps-top);//为0 不能删了ps-top--;
}
//取栈顶元素
STDataType STTop(ST* ps)
{assert(ps);assert(ps-top 0);//不大于0你还怎么取栈顶元素return ps-pa[ps-top - 1];//因为是有效元素的后一个
}
//销毁
void STDestroy(ST* ps)
{assert(ps);ps-top ps-capacity 0;free(ps);//删除元素不行销毁因为数组的空间是一次性开辟的ps NULL;
}
//有效个数
int STSize(ST* ps)
{assert(ps);return ps-top;
}
//判空
bool STEmpty(ST* ps)
{assert(ps);return ps-top 0;//表达式为真返回1假返回0
}
2.4.3test.c
#include Stack.h
void STTest()
{ST s;STInit(s);//压栈STPush(s, 1);STPush(s, 2);STPop(s);//边进边出STPush(s, 3);STPush(s, 4);//printf(%d\n, STTop(s));//STPop(s);//printf(%d\n, STTop(s));//STPop(s); //STPop(s);//printf(%d\n, STTop(s));//STPop(s);//STPop(s);while (!STEmpty(s))//返回假(0),返回的结果为假 就运行{printf(%d , STTop(s));STPop(s);}
}
int main()
{STTest();return 0;
}
总结
栈的整体不算难学会理解后要独立完成联系栈也是有应用场景的至于为什么有这些结构体都是前人发明出来的学习知识有延后性意思就是说从小到大不是学习的所有知识都是有用的但是也要学这个时候就体现了笔记和博客的重要性方便后续复习知识多了肯定记不住
