华为网站建站,青岛seo关键词,哪里做网站比较快,网站建设最新外文翻译前言#xff1a; 小编已经在前面讲完了链表和顺序表的内容#xff0c;下面我们继续乘胜追击#xff0c;开始另一个数据结构#xff1a;栈的详解#xff0c;下面跟上小编的脚步#xff0c;开启今天的学习之路#xff01; 目录 1.栈的概念和结构 1.1.栈的概念 1.2.栈的结构…前言 小编已经在前面讲完了链表和顺序表的内容下面我们继续乘胜追击开始另一个数据结构栈的详解下面跟上小编的脚步开启今天的学习之路 目录 1.栈的概念和结构 1.1.栈的概念 1.2.栈的结构 2.栈的实现 此实现是基于顺序表实现的 2.1.栈的初始化 2.2.栈的销毁 2.3.入栈 2.4.出栈 2.5.取出栈顶的元素 2.6.判断栈中有效的数据个数 2.7.栈元素的打印 3.代码展示 3.1.Stack.h 3.2.Stack.c 总结 正文 1.栈的概念和结构 1.1.栈的概念 栈是一种特殊的线性表它只允许一端进一端出只允许在固定的一端去删除数据和插入数据对于进行插入和删除操作的地方叫做栈顶另一端叫做栈底栈中的数据元素遵从后进先出LIFO的原则简单来说就是最后一个进的最先出来这和它的结构有关下面我们来看一下栈的结构 1.2.栈的结构 上图就是栈的结构图小编在概念也说过栈是有栈顶和栈底的栈顶就是一个出入口所以我们可以把栈看做成一个罐子数据只可以从栈顶进行进入和出去以上就是关于栈的概念和结构了光知道栈的结构是概念是不够的下面小编讲带领大家去实现一个栈 2.栈的实现 此实现是基于顺序表实现的 在讲一些栈的功能之前由于栈是一种线性表所以我们实现栈的可以有顺序表链表两种方式来实现由于时间复杂度等的原因小编在这里选择用顺序表实现但这并不代表着我们不可以用链表实现小编曾经做过题那个题就让我们用链表来实现栈可千万不要以为栈只能用顺序表实现这是重点下面小编先给各位栈结构体的内容
typedef int STDataType;
typedef struct stack {STDataType* arr; //数组类型可能不是一定的所以用typedef替换一下int capacity; //总空间大小int top; //栈顶表示
}ST;2.1.栈的初始化 我们在每次写一个线性表之前初始化是必备的操作因为栈是基于顺序表实现的所以初始化也顺序表类似首先我们需要把数组指针先设置为空对于总空间大小和栈元素个数栈顶都得设置为0由于难度不大小编就不给各位图演示了直接上代码
void STInit(ST* ps)
{ps-arr NULL;ps-capacity ps-top 0; //总空间个数和有用空间个数都初始化为0
}2.2.栈的销毁 有了初始化操作自然而然就有着销毁操作毕竟“有始有终” 栈的销毁同样也是不难的我们对于arr需要判断它是否开辟了空间如果开辟了就free掉没有开辟就直接把栈的空间大小和栈顶都置为空就好下面直接上代码图
void STDestroy(ST* ps)
{if (ps - arr) //先判断是否进行动态内存开辟了{free(ps - arr);}ps-capacity ps-top 0;
}2.3.入栈 在进行完初始化操作以后就要进行一些正式操作了看着入栈这个名字很高大尚以小编的话来说这其实就是栈的尾插栈也只能尾插因为只能从栈顶插入就类似下图 上面这个图就展示了入栈操作其实就是我们在顺序表阶段写的尾插操作首先我们需要先设置一个函数来判断一下栈的总空间大小和栈顶是否是相等如果相等了那就扩容这个和顺序表的扩容是一样的详情可以看小编之前写的那一篇由于栈的插入只有入栈这一种所以扩容操作直接写到函数内部就好我们在进行完插入以后直接往栈顶插入数据然后让栈顶在想后走一步就好了下面直接展示代码
void STPush(ST* ps, STDataType x) //类似顺序表的尾插
{if (ps-capacity ps-top){int newcaopacity ps-capacity 0 ? 4 : 2 * ps - capacity;STDataType* arr1 (STDataType*)realloc(ps-arr, newcaopacity * sizeof(STDataType));assert(arr1);ps-arr arr1;ps-capacity newcaopacity;} //扩容完成ps-arr[ps-top] x;
}2.4.出栈 有入栈肯定就会有出栈对于栈的出栈其实就是顺序表的尾删操作因为栈的元素只能从栈顶出栈底是不可以出元素的可以类比下图进行记忆 通过上图我们就可以知道出栈到底是什么东西对于出栈我们首先需要判断栈是不是空的不然拿什么来出栈所以此时我们得写一个布尔类型函数来判断一下此时的栈是否是空的如果是空的返回true不是真的返回false此时我们进需要判断栈顶是否为0就好下面小编直接给代码图
bool panduan(ST * ps)
{assert(ps);return ps - top 0; //这个是来判断栈是不是空了
}对于上面的代码小编其实写的很简略其实如果写麻烦一点我们需要使用选择语句来判断一下是否为空这里小编直接使用一句话来跳过选择语句了这个代码的含义就是如果右边是对的那么直接返回true如果栈顶不为0直接返回false。当我们判断完以后可以直接进行尾删操作很简单我们只需呀让栈顶减一就好了此时我们就实现了出栈操作下面给出代码图
void STPop(ST* ps)
{assert(ps);assert(!panduan(ps));ps-top--;
}2.5.取出栈顶的元素 这个也是很轻松的对于取出栈顶的元素其实就是取顺序表或者可以直接理解为数组最后一个有效数据此时我们还是需要判断栈顶是否还有元素如果有的话我们直接取出来就好了可是如果那我们就取出了个寂寞所以这一步是必须的之后我们就直接返回栈的最后一个有效数据就好了下面是代码展示
STDataType STTop(ST* ps)
{return ps-arr[ps-top - 1];
}2.6.判断栈中有效的数据个数 这个其实说白了就是返回栈顶的元素就好了此时我们也不需要在判断栈是否有数据了如果没有数据那就直接返回0就好下面小编就直接展示代码了
int STSize(ST* ps)
{return ps-top;
} 2.7.栈元素的打印 对于栈中元素的打印其实也是有点要求的可能有些读者朋友会说我们直接从头打印不就好了那当然是不行的这样就违背了我们栈的结构我们只能从栈顶进入和出去所以我们打印数据其实就是从栈顶开始进行打印的我们每进行完一次打印后就让栈顶元素出栈直到栈中的元素为空就好了如下图所示 正如上图所示打印操作也是这么实现下面进入代码展示
void print(ST * ps)
{while (ps.top){printf(%d , STTop(ps));STPop(ps);}
} 以上就是栈结构的实现其实这么看去栈是一种比较简单实现的数据结构了前提学完了顺序表可能有一些读者朋友想要知道完整的代码不要着急下面进入代码展示环节 3.代码展示 对于栈的实现小编也是分成了两个文件来进行书写一个用来声明函数一个用来实现函数 3.1.Stack.h
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h //存放布尔类型的头文件//下面来复习一下栈的创建
//它的底层代码是数组也可以理解为顺序表
typedef int STDataType;
typedef struct stack {STDataType* arr; //数组类型可能不是一定的所以用typedef替换一下int capacity; //总空间大小int top; //栈顶表示
}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); 3.2.Stack.c
#includeStack.h
void STInit(ST* ps)
{ps-arr NULL;ps-capacity ps-top 0; //总空间个数和有用空间个数都初始化为0
}void STDestroy(ST* ps)
{if (ps - arr) //先判断是否进行动态内存开辟了{free(ps - arr);}ps-capacity ps-top 0;
}void STPush(ST* ps, STDataType x) //类似顺序表的尾插
{if (ps-capacity ps-top){int newcaopacity ps-capacity 0 ? 4 : 2 * ps - capacity;STDataType* arr1 (STDataType*)realloc(ps-arr, newcaopacity * sizeof(STDataType));assert(arr1);ps-arr arr1;ps-capacity newcaopacity;} //扩容完成ps-arr[ps-top] x;
}bool panduan(ST * ps)
{assert(ps);return ps - top 0; //这个是来判断栈是不是空了
}void STPop(ST* ps)
{assert(ps);assert(!panduan(ps));ps-top--;
}STDataType STTop(ST* ps)
{return ps-arr[ps-top - 1];
}int STSize(ST* ps)
{return ps-top;
}
总结 小编也是完成了对于栈的讲解总体来说栈这个数据结构小编自己认为是不算太难的关于栈的习题不算本篇文章算是小编最近写的最短的一篇了希望读者朋友可以去好好的了解如果文章有什么错误的地方请在评论区指出小编一定及时更正那么我们下篇文章见啦
