网站描述 修改,淘宝优惠券网站开发,一流的锦州网站建设,wordpress自定义的注册页面本文来介绍一下数据结构中的栈#xff0c;以及如何用C语言去实现。 1. 栈的概念及结构 栈#xff1a;一种特殊的线性表#xff0c;它只允许在固定的一端进行插入和删除元素的操作。 进行数据插入和删除操作的一端称为栈顶#xff0c;另一端称为栈底。 栈中元素遵循后进先出…
本文来介绍一下数据结构中的栈以及如何用C语言去实现。 1. 栈的概念及结构 栈一种特殊的线性表它只允许在固定的一端进行插入和删除元素的操作。 进行数据插入和删除操作的一端称为栈顶另一端称为栈底。 栈中元素遵循后进先出LIFOLast In First Out的原则 压栈栈的插入操作叫做进栈/入栈/压栈入数据在栈顶。 出栈栈的删除操作叫做出栈出数据也在栈顶。 2. 实现栈的底层方法选择
没有规定栈的哪端是栈顶只说了数据插入和删除的一端是栈顶所以我们栈的底层实现可以用链表或者数组 。 虽然数组和单链表都可以实现栈但是单链表能很好入数据不好删除数据这里单链表要删除数据就是尾删尾删需要找到前一个结点不是很方便。
非要用链表的话有两个解决方法1.可以用双向链表 2.我们把单链表的头节点当作栈顶也就是把左边当栈顶右边当栈底对单链表进行头插和头删的操作。 现在有3种方法实现栈数组单链表双链表我们应该如何选
首先排除双链表用双链表不如用单链表双链表因为一个节点存两个指针比单链表的一个节点多了4个字节或者8个字节。数组实现栈和单链表实现栈有什么区别?基本没区别都可以非要说选一个我们还是更倾向于数组因为数组的唯一缺点就是内存不足时需要扩容扩容的影响也不是特别大最重要的是数组的缓存效率更高。所以我们就用数组实现栈。 3. 栈的实现
提前说明如果本篇看不太懂可以先看看【数据结构】顺序表-CSDN博客我们栈的实现和顺序表的实现差不多。
还是一样新建一个头文件和两个源文件 点开Stack.h文件在这个文件里面我们要定义栈的结构以及给类型和栈的结构取别名。
typedef int STDateType;
typedef struct Stack
{STDateType* a;//动态申请空间 调大小int top; //用栈顶记录元素个数int capacity; //数组实现要扩容记录空间大小
}ST; 栈一共要实现下面这7个接口我们将一个一个来看.
void STInit(ST* pst);//栈初始化
void STDistroy(ST* pst);//栈的销毁
void STPush(ST* pst, STDateType x);//压栈
void STPop(ST* pst);//出栈
STDateType STTopDate(ST* pst);//获取栈顶元素
bool STEmpty(ST* pst);//判断栈是否为空
int STSize(ST* pst);//获取栈元素个数 这里是会用到的头文件且标注了是什么会用到被包含的头文件全放在Stack.h中
#include stdio.h
#include stdlib.h //空间申请
#include stdbool.h //布尔类型
#include assert.h //断言
在Stack.c中只需要包含Stack.h
#include Stack.h准别工作做好后我们开始实现栈。 3.1 栈的初始化和销毁
在Stack.h中进行函数的声明。这里的参数需要传指针。
void STInit(ST* pst);//栈初始化
void STDistroy(ST* pst);//栈的销毁
在SeqList.c中进行函数的实现
void STInit(ST* pst)//栈初始化
{assert(pst); //判断pst是否为空pst-capacity 0;pst-top 0;pst-a NULL;
}
void STDistroy(ST* pst)//栈的销毁
{assert(pst);free(pst-a);pst-a NULL;pst-capacity pst-top 0;
} 这里和顺序表差不多很简单就不多说了。 3.2 压栈和出栈
在Stack.h中进行函数的声明。
void STPush(ST* pst, STDateType x);//压栈
void STPop(ST* pst);//出栈
这里的参数需要传指针压栈的函数参数还有要插入的数据。因为栈插入数据就是从栈顶插入这里就没有什么头插尾插的概念直接就是Push删除数据也是直接栈顶删除Pop。
在SeqList.c中进行函数的实现
先说压栈
先分析空间足够的情况初始化我们把top置为0放进一个元素top就是1但是这个元素在数组中的下标为0所以栈顶元素数组下标是top-1而top指向的是栈顶元素的下一个位置而不是栈顶元素。
所以我们放数据就是直接放下标为top的位置。 void STPush(ST* pst, STDateType x)//压栈
{assert(pst);pst-a[pst-top] x; //先放数据pst-top; //然后top}
然后考虑扩容。capacity是数组大小分析一下数组满了的情况 应该是top和capacity相等此时就要扩容。
void STPush(ST* pst, STDateType x)//压栈
{assert(pst);if (pst-top pst-capacity){int newcapacity pst-capacity * 2;//原来空间2倍的扩容//扩容STDateType* tmp (STDateType*)realloc(pst-a, newcapacity * sizeof(STDateType));if (tmp NULL) //扩容失败{perror(realloc fail);return;}//扩容成功pst-a tmp;pst-capacity newcapacity;}pst-a[pst-top] x;pst-top;
}
但是我们要注意这句代码 int newcapacity pst-capacity * 2; 我们一开始capacity初始化为00乘任何数都是0所以这句换我们要改一下用一个三目操作符就能解决。
int newcapacity pst-capacity 0 ? 4 : pst-capacity * 2; 再说出栈
出栈和顺序表是一样的直接top--就行了不理解的可以看看顺序表中数据的尾删
void STPop(ST* pst)//出栈
{assert(pst);assert(pst-top 0);pst-top--;
} 在test.c中测试一下栈的初始化压栈出栈栈的销毁。
#include Stack.h
int main()
{ST s;STInit(s); //初始化STPush(s, 1);//压栈STPush(s, 2);STPush(s, 3);STPush(s, 4);for (int i 0; i s.top; i){printf(%d , s.a[i]);}printf(\n);STPop(s);//出栈for (int i 0; i s.top; i){printf(%d , s.a[i] );}printf(\n);STPop(s);//出栈for (int i 0; i s.top; i){printf(%d , s.a[i]);}STDistroy(s);//销毁return 0;
} 遵循后进先出 3.3 获取栈顶元素
在Stack.h中进行函数的声明。
STDateType STTopDate(ST* pst);//获取栈顶元素
在SeqList.c中进行函数的实现
STDateType STTopDate(ST* pst)//获取栈顶元素
{assert(pst);assert(pst-top 0);return pst-a[pst-top - 1];
}
在test.c中测试一下
#include Stack.h
int main()
{ST s;STInit(s); //初始化STPush(s, 1);//压栈STPush(s, 2);STPush(s, 3);STPush(s, 4);for (int i 0; i s.top; i){printf(%d , s.a[i]);}printf(\n);printf(栈顶元素%d\n, STTopDate(s));STPop(s);//出栈STPop(s);for (int i 0; i s.top; i){printf(%d , s.a[i] );}printf(\n);printf(栈顶元素%d\n, STTopDate(s));STDistroy(s);//销毁return 0;
} 3.4 判断栈是否为空
在Stack.h中进行函数的声明。
bool STEmpty(ST* pst);//判断栈是否为空这里用了bool类型需要包含头文件stdbool.h
在SeqList.c中进行函数的实现
bool STEmpty(ST* pst)//判断栈是否为空
{assert(pst);if (pst-top 0) //为空返回真return true;else //不为空返回假return false;
}
还有一个更简单的写法如下 bool STEmpty(ST* pst)//判断栈是否为空
{assert(pst);return pst-top 0;
} 为空返回真不为空返回假。
在test.c中测试一下用栈的后进先出的特点访问
#include Stack.h
int main()
{ST s;STInit(s); //初始化STPush(s, 1);//压栈STPush(s, 2);STPush(s, 3);STPush(s, 4);//栈标准的后进先出访问方式while (!STEmpty(s)){printf(%d , STTopDate(s));//先访问栈顶元素STPop(s); //然后把栈顶元素删除}STDistroy(s);//销毁return 0;
} 3.5 获取栈元素个数
在Stack.h中进行函数的声明。
int STSize(ST* pst);//获取栈元素个数在SeqList.c中进行函数的实现
因为我们前面的top初始化为0所以top就是栈的元素个数直接返回top就行了。
int STSize(ST* pst)//获取栈元素个数
{assert(pst);return pst-top;
}
在test.c中自己测试一下这里就不测试了 到这里这个栈就实现好了本篇也就结束啦拜拜~
