什么是链栈及其基本操作

文章目录什么是链栈代码实现结构定义与初始化入栈出栈查找取栈顶销毁(了解)带头结点的链栈什么是链栈链栈是栈的链式存储结构本质上是操作受限的单链表。遵循栈后进先出 LIFO规则只在链表头部栈顶做插入、删除。因为所有的操作都集中在链表头部为了代码最简且效率最高链栈通常采用不带头结点的单链表实现头指针就是栈顶指针。栈顶Top就是单链表的头指针 S它始终指向链表的第一个结点。入栈Push相当于单链表的“头插法”在头部插入新结点。出栈Pop相当于删除单链表的头结点。图示初始S NULL空栈 Push(10) S - [10] - NULL Push(20) S - [20] - [10] - NULL Pop() S - [10] - NULL20 被 free 释放代码实现结构定义与初始化#includestdio.h#includestdlib.h#includestdbool.h// 链栈结点定义与单链表完全一样typedefstructLNode{intdata;// 数据域structLNode*next;// 指针域}LNode,*LinkStack;// LinkStack 就是栈顶指针指向第一个结点// 初始化 创建空栈voidInitStack(LinkStackS){SNULL;// 头指针置空表示没有任何结点}// 判空boolStackEmpty(LinkStack S){returnSNULL;}// 【判满】链栈几乎不存在 “满 ”的概念// 唯一的 “满 ”是堆内存耗尽malloc 失败。通常不写判满函数// 而是在 Push 时检测 malloc 返回值是否为 NULL。boolStackFull(LinkStack S){// 链栈无需判满因为可以动态扩展。// 如果硬要写永远返回 false只要内存够用。returnfalse;}入栈即头插法头插法新结点作为新栈顶。步骤新建结点 → 新结点指向原来的(旧)栈顶 → 更新栈顶指针// 入栈 在栈顶链表头部插入元素 eboolPush(LinkStackS,inte){// 1. 申请新结点空间LNode*s(LNode*)malloc(sizeof(LNode));if(sNULL){// 内存分配失败相当于 “栈满 ”returnfalse;}// 2. 头插法核心三步s-datae;s-nextS;// 新结点指向旧的栈顶结点Ss;// 栈顶指针指向新结点returntrue;}出栈出栈删除头结点栈顶结点步骤判空 → 暂存栈顶结点 → 取出数据 → 栈顶后移 → 释放原栈顶// 出栈删除栈顶元素并通过 e 带回其值boolPop(LinkStackS,inte){// 1. 先判空if(SNULL){returnfalse;}// 2. 保存被删结点LNode*qS;// q 指向栈顶结点eq-data;// 取出数据// 3. 头指针后移跨过被删结点Sq-next;// 新的栈顶变为原(旧)栈顶的下一个结点// 4. 释放被删结点内存防止内存泄漏free(q);returntrue;}查找取栈顶// 取栈顶只读操作不删除结点boolGetTop(LinkStack S,inte){if(SNULL)returnfalse;// 空栈eS-data;// 直接读取头结点的数据域returntrue;}销毁循环释放每一个结点最后栈顶置 NULLvoidDestroyStack(LinkStackS){while(S!NULL){LNode*qS;SS-next;free(q);}}(了解)带头结点的链栈头结点固定存在data闲置next指向真正的栈顶结点。栈顶指针S永远指向这个头结点不移动。#includestdio.h#includestdlib.h#includestdbool.htypedefstructLNode{intdata;structLNode*next;}LNode,*LinkStack;// LinkStack 指向头结点// 初始化: 创建头结点让头结点的 next 置空boolInitStack(LinkStackS){S(LNode*)malloc(sizeof(LNode));if(SNULL)returnfalse;S-nextNULL;// 头结点后面没有结点表示空栈returntrue;}// 判空: 判断头结点的 next 是否为 NULLboolStackEmpty(LinkStack S){returnS-nextNULL;}对比维度不带头结点标准带头结点初始状态S NULL空指针S指向头结点S-next NULL判空条件S NULLS-next NULL入栈核心代码s-next S; S s;直接改头指针s-next S-next; S-next s;改头结点的指针域出栈核心代码S q-next;头指针后移S-next q-next;头结点指针域跳过取栈顶元素e S-data;e S-next-data;多一层间接访问