什么是顺序栈
文章目录顺序栈结构定义 初始化进栈出栈查找 取栈顶销毁另一种方式 top含义共享栈总结栈Stack是一种只允许在表的一端栈顶进行插入和删除操作的线性表具有后进先出LIFO的特性。其逻辑结构与普通线性表相同。栈顶允许插入和删除的一端栈顶元素栈底不允许插入和删除的一端栈底元素n 个不同元素进栈出栈元素不同排列的个数为1 n 1 C 2 n n \frac{1}{n1} C_{2n}^{n}n11C2nn顺序栈顺序栈是利用一组地址连续的存储单元存放栈元素基于静态数组实现的栈属于顺序存储。栈底固定在数组下标0位置用整型变量top作为栈顶指针标记当前栈顶元素下标(数组下标)遵循后进先出 LIFO仅能在栈顶完成插入、删除。所有基本操作时间复杂度都为O(n)结构定义 初始化top的含义指向栈顶元素所在位置#includestdio.h#includestdbool.h// 为了使用 bool 类型#defineMaxSize10// 定义最大容量typedefstruct{intdata[MaxSize];// 静态数组存放数据inttop;// 栈顶指针指向栈顶元素指向此时栈顶元素即数组下标}SqStack;// 初始化 创建空栈 top-1指向栈顶元素所在位置voidInitStack(SqStackS){S.top-1;// 关键点初始时栈中无元素指针指向 -1// 注意data 数组里的旧垃圾值不需要清零因为 top -1 屏蔽了它们}// 判空boolStackEmpty(SqStack S){returnS.top-1;// 栈顶指针指向 -1 即为空 返回 true}// 判满boolStackFull(SqStack S){returnS.topMaxSize-1;// 数组下标 最大MaxSize -1}进栈// 进栈 在栈顶插入元素 eboolPush(SqStackS,inte){// 1. 先判断是否已满if(S.topMaxSize-1)returnfalse;// 2. top 先加 1指向新的空位再把元素放进去S.topS.top1;// 即 S.top;S.data[S.top]e;// 或者合并为一行S.data[S.top] e;returntrue;}出栈出栈数据还残留在内存当中只是逻辑上被删除了被top屏蔽了。// 出栈删除栈顶元素并带回其值boolPop(SqStackS,inte){// 1. 先判断是否为空if(S.top-1)returnfalse;// 2. 先取出当前栈顶元素再让 top 减 1eS.data[S.top];S.topS.top-1;// 即 S.top--;// 或者合并为一行e S.data[S.top--];returntrue;}// 物理上还在但逻辑上被 top 指针屏蔽了。下次入栈新元素时会直接覆盖这个位置。查找 取栈顶// 取栈顶只读操作不删除元素所以不使用 SboolGetTop(SqStack S,inte){if(S.top-1)returnfalse;eS.data[S.top];// top 不动returntrue;}取栈顶对比出栈操作销毁顺序栈的清空S.top -1;即可。因为数组空间是静态分配的逻辑上清空指针即可物理内存不需要free除非用了动态malloc。回收函数运行结束后系统自动回收内存(因为是静态数组)。另一种方式 top含义top的含义指向栈顶元素的下一个位置即待插入位置#defineMaxSize10// 定义最大容量typedefstruct{intdata[MaxSize];inttop;}SqStack;// 初始化创建空栈voidInitStack(SqStackS){S.top0;// 初始指向 0指向下一个可插入元素的位置}// 判空boolStackEmpty(SqStack S){returnS.top0;// 栈顶指针指向 0 即为空栈 返回 true}// 判满 顺序栈的缺点站的大小不可变boolStackFull(SqStack S){returnS.topMaxSize;}// 进栈S.data[S.top]e;S.topS.top1;// S.top;// 上面两行等价于 S.data[S.top] x;// 出栈S.topS.top-1;// S.top--;eS.data[S.top];// 上面两行等价于 x S.data[--S.top];共享栈两个栈共享同一段数组空间data[0 ... MaxSize-1]两个栈从两边往中间增长极大提高内存利用率。#defineMaxSize10// 定义最大容量typedefstruct{intdata[MaxSize];inttop0;// 0 号栈 栈顶指针inttop1;// 1 号栈 栈顶指针}SqStack;voidInitStack(ShStackS){S.top0-1;// 初始化栈顶指针S.top1MaxSize;}// 栈满条件top0 1 top1;// 两个栈顶指针相邻代表数组被完全占满无空位图示[ 栈0元素 | 栈0元素 | 空闲 | 栈1元素 | 栈1元素 ] ↑ top0 ↑ top1总结维度top-1 推荐top0top 的含义指向栈顶元素所在位置指向栈顶元素的下一个位置即待插入位置初始值top -1top 0栈空条件top -1top 0栈满条件top MaxSize - 1top MaxSize入栈动作Pushdata[top] e;先移指针再放元素data[top] e;先放元素再移指针出栈动作Pope data[top- -];先取元素再移指针e data[- - top];先移指针再取元素记忆口诀“顶指元素先移后放”“顶指空位先放后移”
