企业网站网络推广怎么做,微信上打开连接的网站怎么做的,北京东站,网页设计公司理念前言#xff1a;
还是举一个生活中的例子#xff0c;大家都玩过积木#xff0c;当我们把积木叠起来的时候#xff0c;如果要拿到最底部的积木#xff0c;我们必须从顶端一个一个打出#xff0c;最后才能拿到底部的积木#xff0c;也就是后进先出#xff08;先进后出
还是举一个生活中的例子大家都玩过积木当我们把积木叠起来的时候如果要拿到最底部的积木我们必须从顶端一个一个打出最后才能拿到底部的积木也就是后进先出先进后出的道理今天分享栈的实现的本质也就是后进先出先进后出。
目录
前言
栈的概念及结构
栈的实现
栈的结构定义
初始化栈
压栈数据的添加
出栈数据的删除
获取栈顶元素
获取栈中有效元素个数
判断栈是否为空
栈实现的总代码vs2022
头文件Stack.h
函数文件Stack.c
测试Text.c 栈的概念及结构
要去实现栈我们要知道什么是 栈栈的结构是什么该从什么方向去实现。 栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除 操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出 LIFO Last In First Out 的原则。 压栈栈的插入操作叫做进栈/ 压栈 / 入栈入数据在栈顶。 出栈栈的删除操作叫做出栈。出数据也在栈顶。 如图我们会发现数据进栈出栈后的顺序倒置了其实栈不只是可以将顺序导致我们也可以先把AB放进去拿出来之后再将CD放进去全部拿出来可以得到CDAB所以栈最后导致的结果是多种多样的这取决你如何运用栈了。
栈的实现 栈的实现一般可以使用数组或者链表实现相对而言数组的结构实现更优一些。因为数组在尾上 插入数据的代价比较小。 我们在这里使用数组进行实现如图所示我们把数组的尾部作为栈顶这样可以轻松的进行压栈操作增加数据如果使用链表的话我们找到尾节点需要进行遍历找尾利用循环去找为节点这样就增多了时间的消耗这里使用数组来实现栈可以提高算法效率。 栈的结构定义
typedef int STDataType;typedef struct Stack
{ STDataType* a;int top; //栈顶int capacity;//栈容量
}Stack;
栈只需要对栈顶进行操作所以我们有一个变量top表示栈顶。后面需要判断栈是否为空我们需要一个变量capacity表示栈容量。
初始化栈
void StackInit(Stack* ps)
{assert(ps);ps-a (STDataType*)malloc(sizeof(STDataType) * 4);ps-top 0;ps-capacity 4;
}
这里我们创造了4个整型变量的空间所以capacity给4。
压栈数据的添加
void StackPush(Stack* ps,STDataType x)
{assert(ps);if (ps-top ps-capacity)//考虑到空间大小不够使用realloc进行增容操作{STDataType* tmp (STDataType*)realloc(ps-a, ps-capacity * 2 * sizeof(STDataType));if (tmp NULL)//要注意tmp可能为空的情况。{printf(realloc fail!!!);exit(-1);}ps-a tmp;//别忘了把指针a指向新开辟的空间ps-capacity * 2;}ps-a[ps-top] x;ps-top;//注意个数的增加
}
在压栈的时候要注意几点
1.压栈时要考虑空间的大小是否足够不够时要进行增容操作。
2.增容操作后的原指针要指向新指针保证数据不会丢失。
3.压栈过后要对将top往后移动一位因为top的指向是数组最后元素的下一个位置。
出栈数据的删除
void StackPop(Stack* ps)
{assert(ps);assert(ps-top 0);//top不能小于或等于0因为top是指向栈顶元素的下一个位置ps-top--;
}
因为是用数组进行栈的实现我们只需要把栈顶往前移动一位就表示删除了数据。
获取栈顶元素
STDataType StackTop(Stack* ps)
{assert(ps);assert(ps-top 0);return ps-a[ps-top - 1];//因为top是指向栈顶元素的下一个位置所以要-1}
一定注意对ps-top0进行断言保证栈的元素不为空。
获取栈中有效元素个数
int StackSize(Stack* ps)
{assert(ps);return ps-top;}
top指向的数组尾部元素后一位刚好是数组中有效元素的个数。
判断栈是否为空
bool StackEmpty(Stack* ps)//bool也可以使用 表示真假
{assert(ps);return ps-top 0;
}
检查栈是否为空如果不为空则返回0如果为空则返回非零结果。
栈实现的总代码vs2022
头文件Stack.h
#pragma once#includestdio.h
#includestdbool.h
#includestdlib.h
#includeassert.h
typedef int STDataType;typedef struct Stack
{ STDataType* a;int top; //栈顶int capacity;//栈容量
}Stack;
//初始化栈
void StackInit(Stack* ps);
//栈的销毁
void StackDestory(Stack* ps);
//压栈
void StackPush(Stack* ps,STDataType x);
//出栈
void StackPop(Stack* ps);
//获取栈顶元素
STDataType StackTop(Stack* ps);
//获取栈中有效元素的个数
int StackSize(Stack* ps);
//检查栈是否为空如果不为空则返回0如果为空则返回非零结果
bool StackEmpty(Stack* ps);//bool也可以使用 表示真假函数文件Stack.c
#includeStack.hvoid StackInit(Stack* ps)
{assert(ps);ps-a (STDataType*)malloc(sizeof(STDataType) * 4);ps-top 0;ps-capacity 4;
}
void StackDestory(Stack* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-top ps-capacity 0;}
//入栈
void StackPush(Stack* ps,STDataType x)
{assert(ps);if (ps-top ps-capacity)//考虑到空间大小不够使用realloc进行增容操作{STDataType* tmp (STDataType*)realloc(ps-a, ps-capacity * 2 * sizeof(STDataType));if (tmp NULL)//要注意tmp可能为空的情况。{printf(realloc fail!!!);exit(-1);}ps-a tmp;//别忘了把指针a指向新开辟的空间ps-capacity * 2;}ps-a[ps-top] x;ps-top;//注意个数的增加
}
void StackPop(Stack* ps)
{assert(ps);assert(ps-top 0);//top不能小于或等于0因为top是指向栈顶元素的下一个位置ps-top--;
}
STDataType StackTop(Stack* ps)
{assert(ps);assert(ps-top 0);return ps-a[ps-top - 1];//因为top是指向栈顶元素的下一个位置所以要-1}
int StackSize(Stack* ps)
{assert(ps);return ps-top;}
bool StackEmpty(Stack* ps)//bool也可以使用 表示真假
{assert(ps);return ps-top 0;
}
测试Text.c
#includeStack.hvoid StackText()
{Stack st;StackInit(st);StackPush(st, 1);StackPush(st, 2);StackPush(st, 3);StackPush(st, 4);StackPush(st, 5);while (!StackEmpty(st)){printf(%d , StackTop(st));StackPop(st);}StackDestory(st);
}int main()
{StackText();return 0;
}
好啦这就是今天学习的分享啦看到希望大家的三连呀
如果有不当之处欢迎大佬指正
