「 每日一句 · Daily Quote 」“立志宜思真品格读书须尽苦功夫。”— 阮元文章目录前言一、栈1. 概念与结构2. 栈的实现2.1 定义栈的结构2.2 初始化2.3 销毁2.4 入栈2.5 判断栈是否为空2.6 出栈2.7 取栈顶元素2.8 获取栈中有效元素个数二、队列1. 概念与结构2. 队列的实现2.1 队列结点的创建2.2 队列的初始化2.3 入队2.4 销毁队列2.5 队列判空2.6 出队2.7 队列有效元素2.8 取对头数据2.9 取队尾数据总结前言栈和队列是两种最基础且常用的线性数据结构分别遵循“后进先出”和“先进先出”的原则。本文将从概念入手讲解栈的数组实现与队列的链表实现逐步完成初始化、入栈/入队、出栈/出队、取顶/取尾、判空、销毁等核心接口并分析各操作的代码逻辑与注意事项。掌握它们是理解更复杂数据结构与算法的重要基石。一、栈1. 概念与结构栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFOLast In First Out的原则。压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。出栈栈的删除操作叫做出栈。出数据也在栈顶。栈的实现一般可以使用数组或者链表实现相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。2. 栈的实现2.1 定义栈的结构//定义栈的结构typedefintSTDataType;typedefstructstack{STDataType*arr;//数组指针,指向栈的动态数组inttop;//指向栈顶位置intcapacity;//栈的容量}ST;typedef int STDataType,给栈中数据取了一个别名,方便后续统一处理STDataType* arr数组指针,指向栈的动态数组top指向栈顶位置的数据capacity栈的容量2.2 初始化voidStackInit(ST*ps){ps-arrNULL;ps-topps-capacity0;}将arr置为空,并让top和capacity都为02.3 销毁//销毁voidStackDestroy(ST*ps){if(ps-arr)free(ps-arr);ps-arrNULL;ps-top0;ps-capacity0;}释放arr指向的那块动态申请的内存空间将arr置为空,并让top和capacity都为02.4 入栈//入栈---栈顶voidStackPush(ST*ps,STDataType x){assert(ps);//如果空间不够,扩容if(ps-capacityps-top){intnewcapacityps-capacity0?4:ps-capacity*2;STDataType*tmp(STDataType*)realloc(ps-arr,newcapacity*sizeof(STDataType));if(tmpNULL){perror(relloc fail);exit(1);}ps-arrtmp;ps-capacitynewcapacity;}//入栈操作ps-arr[ps-top]x;ps-top;}先判断ps不为空,才能进行解引用判断空间是否足够,若不够进行扩容操作将数据x放入top指向的位置,并top,让栈顶位置向后移动一位同时表示栈中有效元素数量增加 12.5 判断栈是否为空bool StackEmpty(ST* ps) { assert(ps); return ps-top 0; }先检查ps不为空指针判断ps-top是否为0,并返回布尔值2.6 出栈//出栈——栈顶voidStackPop(ST*ps){//栈不为空assert(!StackEmpty(ps));//出栈操作ps-top--;}先判断栈不为空直接top--,表示有效数据减一2.7 取栈顶元素//取栈顶元素STDataTypeStackTop(ST*ps){//判断栈不为空assert(!StackEmpty(ps));//返回栈顶元素returnps-arr[ps-top-1];}先判断栈不为空返回arr数组中下标为top-1的值,即为栈顶元素的值2.8 获取栈中有效元素个数//获取栈中有效元素个数intStackSize(ST*ps){assert(ps);returnps-top;}检查ps不为空指针返回top的值,即为栈中有效元素个数二、队列1. 概念与结构概念只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出FIFO(First In First Out)入队列进行插入操作的一端称为队尾出队列进行删除操作的⼀端称为队头队列也可以数组和链表的结构实现使用链表的结构实现更优一些因为如果使用数组的结构出队列在数组头上出数据效率会比较低。我们实现队列利用链表来实现.2. 队列的实现2.1 队列结点的创建typedefintQDataType;typedefstructQueueNode{QDataType data;structQueueNode*next;}QueueNode;typedefstructQueue{QueueNode*phead;QueueNode*ptail;//int size;}Queue;typedef int QDataType给已有的数据类型取一个别名,方便之后统一更换数据类型QueueNode作为队列的每个结点,data保存数据,next保存下一个结点的地址Queue作为队列,phead指向头结点,ptail指向尾结点2.2 队列的初始化//初始化voidQueueInit(Queue*pq){assert(pq);pq-pheadpq-ptailNULL;//pq-size 0;}初始化的队列中没有元素, 将队列的头结点和尾结点都置为NULL2.3 入队//入队——队尾voidQueuePush(Queue*pq,QDataType x){assert(pq);//创建新节点QueueNode*newnode(QueueNode*)malloc(sizeof(QueueNode));if(newnodeNULL)//创建失败{perror(malloc fail);exit(1);}//为新结点插入数据newnode-datax;newnode-nextNULL;//判断队列是否为空if(pq-pheadNULL){pq-pheadpq-ptailnewnode;}//队列不为空else{pq-ptail-nextnewnode;pq-ptailnewnode;//尾指针指向新结点}//pq-size;}创建新节点: 用malloc函数创建新节点,并用QueueNode*类型的newnode进行接收将数据x插入newnode的data中,因为此时新插入的结点要成为新的尾结点,所以newnode的next指针为NULL从队尾入队,先判断队列是否为空. 若队列为空,则让phead和ptail都指向newnode.若队列不为空,则让原来ptail的next指针指向newnode,然后再让ptail指向newnode,使newnode变成新的尾结点2.4 销毁队列//销毁队列voidQueueDestroy(Queue*pq){//先判断不是空指针assert(pq);//遍历队列,逐个释放QueueNode*curpq-phead;while(cur){//保存next指针QueueNode*nextcur-next;free(cur);curnext;}//释放完,将队列置为空pq-pheadpq-ptailNULL;//pq-size 0;}创建遍历指针cur,遍历队列先创造一个next指针用于接收并保存cur的next指针释放当前的cur,将先前赋值的next指针赋给cur队列中所以元素释放完,将phead和ptail位置置为NULL2.5 队列判空//队列判空boolQueueEmpty(Queue*pq){//检查不为空指针assert(pq);returnpq-pheadNULL;}检查pq不为空指针,返回pq-phead NULL的布尔值2.6 出队//出队——队头voidQueuePop(Queue*pq){assert(!QueueEmpty(pq));//如果只有一个结点if(pq-pheadpq-ptail){free(pq-phead);pq-pheadpq-ptailNULL;}else{//先保存删除结点QueueNode*delpq-phead;pq-pheadpq-phead-next;free(del);}//pq-size--;}若只有一个结点,则释放当前结点,并将phead和ptail都置为NULL若不止一个结点,则先创建del指针保存要删除的结点,让phead往后移动一位,free(del);2.7 队列有效元素//队列有效元素个数intQueueSize(Queue*pq){assert(pq);//第一种方式遍历链表——适用于不会频繁调用队列有效数据个数的场景intsize0;QueueNode*curpq-phead;while(cur){size;curcur-next;}returnsize;//第二种方式遍历链表——适用于频繁调用队列有效数据个数的场景// return pq-size;}法一:遍历链表—适用于不会频繁调用队列有效数据个数的场景法二:直接返回size,适用于频繁调用队列有效数据个数的场景2.8 取对头数据//取队头数据QDataTypeQueueFront(Queue*pq){assert(!QueueEmpty(pq));returnpq-phead-data;}先检查不为空队列,返回头结点的data2.9 取队尾数据//取队尾数据QDataTypeQueueBack(Queue*pq){assert(!QueueEmpty(pq));returnpq-ptail-data;}先检查不为空队列,返回尾结点的data总结以上就是本篇博客的核心内容。本文介绍了栈LIFO与队列FIFO的概念与结构分别采用动态数组实现栈、单链表实现队列。详细讲解了栈的初始化、入栈、出栈、取栈顶、判空、销毁以及队列的初始化、入队、出队、取队头/队尾、判空、销毁和有效元素统计。通过代码与图解帮助读者掌握两种结构的核心操作与适用场景。