php网站建设是什么意思,做地铁系统集成的公司网站,公众号怎么赚钱,如何获取热搜关键词文章目录#x1f63a;前言栈初始化栈顶入栈栈顶出栈栈体判空栈的数据个数获取栈顶元素栈的销毁整体代码#x1f63c;写在最后#x1f63a;前言 #x1f47b;前面我们学习了链表#xff0c;总算是跨过一个台阶了#xff0c;本章带大家轻松一波#xff0c;领悟一下栈的魅力…
文章目录前言栈初始化栈顶入栈栈顶出栈栈体判空栈的数据个数获取栈顶元素栈的销毁整体代码写在最后前言 前面我们学习了链表总算是跨过一个台阶了本章带大家轻松一波领悟一下栈的魅力。栈是一种较为简单的数据结构它的主要性质就是数据后进先出(LIFO)我们可以利用这一性质在做某些算法题时以此为切入点。因此栈还是挺不错的。 栈初始化
栈的性质是后进先出(不能任意插入删除)并且只能访问栈顶元素因此对数据的入栈和出栈是特别方便的。 根据栈的这样一个后进先出的性质我们该如何选择它的底层结构呢是顺序表的数组还是链表呢由此我们分析一下。 如果是数组很容易想到完全符合对栈的性质的操作如果是入栈直接在数组最后一个位置插入即可空间不够扩容就好如果是出栈直接将统计栈顶的变量减一即可想要获取栈顶的数据那不也很简单嘛。由此看来数组还真是不错呢。 如果是链表入栈只要将数据头插即可出栈就是头删获取栈顶数据就是头节点的数据这样看来链表也挺不错呢。那么到底是选数组还是链表呢
我们来看一下数据对比
可以看到对于栈的性质该表的前面五个特点都没有明显的优与劣但是最后一个缓存利用率却能分出高下很明显实现一个栈使用数组会更好。对于什么是缓存利用率这里就不讲解了大家自行查找资料噢 选取了实现栈的底层结构接下来就是对栈的初始化操作了。 首先需要三个文件与前面的单链表一样哈哈哈stack.hstack.ctest.cstack.h用来存放一些所需头文件函数声明以及栈的结构体。stack.c用来实现函数接口test.c用来测试。 所需头文件
#include stdio.h
// assert断言
#include assert.h
// 判空需用到
#include stdbool.h
// 动态空间需用
#include stdlib.h接下来就对控制栈的结构体进行创建
typedef int STDataType;
typedef struct stack
{// 底层数组STDataType* a;// 容量int capacity;// 标识栈顶int top;
}stack;接下来是函数声明
// 初始化
void STInit(stack* pt);
// 入栈
void STPush(stack* pt, STDataType x);
// 出栈
void STPop(stack* pt);
// 判空
bool STEmpty(stack* pt);
// 取栈顶元素
STDataType STTop(stack* pt);
// 栈的元素个数
int STSize(stack* pt);
// 销毁栈
void STDestroy(stack* pt);怎么样是不是看了函数接口就很简单呢只有这些接口噢。
栈的初始化
对于栈的初始化我们可以直接将top和capacity置为0指向存放数据的数组的指针置为NULL。如下
void STInit(stack* pt)
{// 这里断言一下pt是为了防止传递一个NULL指针正确的应该传递一个结构体的地址assert(pt);pt-a NULL;pt-capacity 0;pt-top 0;
}关于top实际上还可以初始化为-1。但-1与0实际差别不大只是获取栈顶元素判空和数据入栈这些代码会有所不同。如果top初始化为-1那么top就是栈顶元素如果top初始化为0top就是栈顶元素的下一个位置。所以我们在实现的时候要注意这个top。 而本章采用的top为0也就是top是栈顶元素的下一个位置。 top 0 实际上也间接体现了此时栈的数据个数。 栈顶入栈 栈顶入栈就是在数组的最后一个位置添加一个数据即可操作简单不过这里要考虑一个扩容的问题。 如果此时空间容量不够(判断条件top capacity)就需要扩容这里使用realloc扩容如果开始没有空间该函数的功能就跟malloc一样。 插入只要在top位置插入即可最后top要加加一下噢。
下面是相关函数接口的代码实现
void STPush(stack* pt, STDataType x)
{// 防止传递一个NULLassert(pt);// 检查容量看是否已满满了就需要扩容if (pt-top pt-capacity){int newcapacity pt-capacity 0 ? 4 : pt-capacity * 2;STDataType* tmp realloc(pt-a, sizeof(STDataType) * newcapacity);if (tmp NULL){perror(realloc fail);exit(-1);}pt-a tmp;pt-capacity newcapacity;}// 在top位置放新的的数据同时top要加一pt-a[pt-top] x;
}栈顶出栈 栈顶出栈就是抹去数组最后一个数据只要top自减一即可。 注意当栈为空的时候就不能出栈了如何判断是否为空在下面呢别急哈哈哈。
下面是相关函数接口的代码实现
void STPop(stack* pt)
{// 如果为空就不能删了。判空在后面写到。assert(pt !STEmpty(pt));// top减一即可pt-top--;
}栈体判空
栈体判空只需要判断一下top是否为0即可。如果是0说明此时栈为空返回true如果不等于0说明此时栈不为空返回false。
下面是相关函数接口的代码实现
bool STEmpty(stack* pt)
{assert(pt);return pt-top 0;
}栈的数据个数
前面说了top就相当于是数据的个数所以这里直接返回top的值即可。
下面是相关函数接口的代码实现
int STSize(stack* pt)
{assert(pt);return pt-top;
}获取栈顶元素
由于top是最后一个元素的下一个位置因此获取栈顶元素时它的位置为top - 1。
下面是相关函数接口的代码实现
STDataType STTop(stack* pt)
{assert(pt !STEmpty(pt));return pt-a[pt-top - 1];
}栈的销毁 有空间的开辟那就要有空间的释放这里称为销毁。 销毁也很简单只需要将指向栈空间的那个指针free即可。 当然最后可以将top置为0capacity也置为0。
下面是相关函数接口的代码实现
void STDestroy(stack* pt)
{assert(pt);free(pt-a);pt-capacity 0;pt-top 0;
}整体代码
stack.h
#include stdio.h
#include assert.h
#include stdbool.h
#include stdlib.htypedef int STDataType;
typedef struct stack
{STDataType* a;int capacity;int top;
}stack;// 初始化
void STInit(stack* pt);
// 入栈
void STPush(stack* pt, STDataType x);
// 出栈
void STPop(stack* pt);
// 判空
bool STEmpty(stack* pt);
// 取栈顶元素
STDataType STTop(stack* pt);
// 栈的元素个数
int STSize(stack* pt);
// 销毁栈
void STDestroy(stack* pt);stack.c
#include stack.hvoid STInit(stack* pt)
{assert(pt);pt-a NULL;pt-capacity 0;pt-top 0;
}void STPush(stack* pt, STDataType x)
{assert(pt);if (pt-top pt-capacity){int newcapacity pt-capacity 0 ? 4 : pt-capacity * 2;STDataType* tmp realloc(pt-a, sizeof(STDataType) * newcapacity);if (tmp NULL){perror(realloc fail);exit(-1);}pt-a tmp;pt-capacity newcapacity;}pt-a[pt-top] x;
}
void STPop(stack* pt)
{assert(pt !STEmpty(pt));pt-top--;
}bool STEmpty(stack* pt)
{assert(pt);return pt-top 0;
}
STDataType STTop(stack* pt)
{assert(pt !STEmpty(pt));return pt-a[pt-top - 1];
}int STSize(stack* pt)
{assert(pt);return pt-top;
}void STDestroy(stack* pt)
{assert(pt);free(pt-a);pt-capacity 0;pt-top 0;
}test.c
#include stack.hvoid test()
{stack st;STInit(st);STPush(st, 1);STPush(st, 2);STPush(st, 3);STPush(st, 4);STPush(st, 5);while (!STEmpty(st)){printf(%d , STTop(st));STPop(st);}printf(\n);STPush(st, 5);STPush(st, 55);STPush(st, 555);STPush(st, 5555);STPush(st, 55555);STPush(st, 555555);printf(%d\n, STTop(st));while (!STEmpty(st)){printf(%d , STTop(st));STPop(st);}printf(\n);STDestroy(st);
}int main()
{test();return 0;
}写在最后 到这里一个简简单单的栈就完成了是不是很简单呢不过也别得意哈后面难的数据结构还没来呢栈就是让你处于一个平静期为后来的难度做准备呢哈哈哈哈哈。 ❤️后续将会持续输出有关数据结构的文章你们的支持就是我写作的最大动力 感谢阅读本小白的博客错误的地方请严厉指出噢~
