cms网站开发价格,莱西市城乡建设局网站,php图片怎么导入wordpress,做效果图的兼职网站目录
前言
一、顺序栈的定义
二、顺序栈的c语言结构描述表示
三、顺序栈中基本操作的实现
3.1顺序栈的初始化
3.2判断顺序栈是否为空
3.3求顺序栈的长度
3.4清空顺序栈
3.5销毁顺序栈
3.6顺序栈的入栈
3.7顺序栈的出栈
3.8求栈顶元素
3.9遍历顺序栈 四、顺序栈的…目录
前言
一、顺序栈的定义
二、顺序栈的c语言结构描述表示
三、顺序栈中基本操作的实现
3.1顺序栈的初始化
3.2判断顺序栈是否为空
3.3求顺序栈的长度
3.4清空顺序栈
3.5销毁顺序栈
3.6顺序栈的入栈
3.7顺序栈的出栈
3.8求栈顶元素
3.9遍历顺序栈 四、顺序栈的代码实现
五、测试结果
五、总结 前言
本文参考王卓老师的数据结构视频和严蔚敏老师的《数据结构》 一、顺序栈的定义
栈操作受限的线性表限定仅在表尾进行插入和删除操作的线性表即后进先出。这一端被称为栈顶相对地把另一端称为栈底。
顺序栈用顺序结构存储的栈
例子类似子弹压入弹夹后放入的子弹可以先从弹夹弹出来。
特点简单方便但是容易溢出上溢或者下溢
二、顺序栈的c语言结构描述表示
代码如下示例 typedef struct sqstack{ int *top;//栈顶指针 int *base;//栈底指针 int stackSize;//栈的最大容量 }stack; 三、顺序栈中基本操作的实现
3.1顺序栈的初始化 数组用c的new来动态开辟 当内存不够的时候也即是s.base为空则直接结束 不为空的时候则栈的栈顶指针与栈底指针都指向同一位置 代码如下示例
void initStack(stack s)
{s.basenew int[MaxSize];if(!s.base) exit(0);//内存分配失败结束s.tops.base;//初始的时候栈的top与base相等 s.stackSizeMaxSize;//栈的最大容量
}
3.2判断顺序栈是否为空 栈顶指针与栈底指针都指向同一位置即s.bases.top的时候则栈为空返回1 否则不为空返回0 代码如下示例
int isEmpty(stack s)
{if(s.bases.top)return 1;//表示为空无元素return 0;//不为空
}
3.3求顺序栈的长度 长度即为有多少个元素可以用s.top-s.base 代码如下示例
int stackLength(stack s)
{return s.top-s.base;
}
3.4清空顺序栈 当s.base不为空的时候让s.top(栈顶指针)直接指向s.base栈底,则把所有的元素逻辑上清空了 而当s.base为空的时候则栈已经被销毁了无需清空 代码如下示例
void CleanStack(stack s)
{if(s.base){s.tops.base;cout成功清空endl;}elsecout栈已经被销毁无需清空endl;
}
3.5销毁顺序栈 从物理层次销毁 也即是用delete将整个s.base从内存中删除 代码如下示例
void DestoryStack(stack s)
{if(s.base){delete s.base;s.stackSize0;s.baseNULL;s.topNULL;cout成功销毁endl;}elsecout栈已经被销毁无需销毁endl;
}
3.6顺序栈的入栈
首先判断栈是否已经满了如果满了则无法入栈否则可以入栈 代码如下示例
void push(stack s,int e)
{if((s.top-s.base)s.stackSize)cout栈满了无法添加新元素endl;else{*(s.top)e;s.top; cout添加成功endl;}
}
3.7顺序栈的出栈 首先判断栈是否为空如果为空则无法出栈否则可以出栈 代码如下示例
void pop(stack s,int e)
{if(isEmpty(s)){cout栈为空无法弹出endl;} else{s.top--;e*(s.top);cout成功弹出endl; }
}
3.8求栈顶元素 先判断栈是否为空为空则无法求栈顶元素否则可以求栈顶元素 代码如下示例
int top(stack s)
{if(isEmpty(s)){cout栈为空没有栈顶元素endl;return -1;}else{s.top--;return *(s.top);}
}
3.9遍历顺序栈 从栈底开始遍历 代码如下示例
void traverse(stack s)
{int lengthstackLength(s);if(length0){cout顺序栈的元素为:(从栈底开始遍历)endl;for(int i0;ilength;i)couts.base[i] ;} elsecout顺序栈为空endl;
} 四、顺序栈的代码实现
#include iostream
using namespace std;
const int MaxSize100;
typedef struct sqstack{int *top;//栈顶指针int *base;//栈底指针int stackSize;//栈的最大容量
}stack;
void initStack(stack s)
{s.basenew int[MaxSize];if(!s.base) exit(0);//内存分配失败结束s.tops.base;//初始的时候栈的top与base相等 s.stackSizeMaxSize;//栈的最大容量
}
int isEmpty(stack s)
{if(s.bases.top)return 1;//表示为空无元素return 0;//不为空
}
int stackLength(stack s)
{return s.top-s.base;
}
void CleanStack(stack s)
{if(s.base){s.tops.base;cout成功清空endl;}elsecout栈已经被销毁无需清空endl;
}
void DestoryStack(stack s)
{if(s.base){delete s.base;s.stackSize0;s.baseNULL;s.topNULL;cout成功销毁endl;}elsecout栈已经被销毁无需销毁endl;
}
//入栈
void push(stack s,int e)
{if((s.top-s.base)s.stackSize)cout栈满了无法添加新元素endl;else{*(s.top)e;s.top; cout添加成功endl;}
}
//出栈
void pop(stack s,int e)
{if(isEmpty(s)){cout栈为空无法弹出endl;} else{s.top--;e*(s.top);cout成功弹出endl; }
}
int top(stack s)
{if(isEmpty(s)){cout栈为空没有栈顶元素endl;return -1;}else{s.top--;return *(s.top);}
}
void traverse(stack s)
{int lengthstackLength(s);if(length0){cout顺序栈的元素为:(从栈底开始遍历)endl;for(int i0;ilength;i)couts.base[i] ;} elsecout顺序栈为空endl;
}
void menu()
{cout**********************************endl;cout1.初始化endl;cout2.判断栈是否为空endl;cout3.求栈的长度endl;cout4.清空栈endl;cout5.销毁栈endl;cout6.入栈endl;cout7.出栈endl;cout8.求栈顶元素endl;cout9.遍历顺序栈endl;cout10.退出endl;cout**********************************endl;
}
int main()
{int choice;stack s;int e1,e2;while(1){menu();cinchoice;switch(choice){case 1:initStack(s);cout初始化成功endl;break;case 2:if(isEmpty(s))cout栈为空endl;elsecout栈不为空endl; break;case 3:cout栈的长度为stackLength(s)endl;break;case 4:CleanStack(s);break;case 5:DestoryStack(s);break; case 6:cout请输入想要入栈的元素值endl;cine1;push(s,e1);break;case 7:pop(s,e2);cout弹出的元素为e2endl;break;case 8:if(top(s)!-1)cout栈顶元素为top(s)endl;break;case 9:traverse(s);coutendl;break;case 10:cout成功退出endl;exit(0);default:cout输入有误请重新输入endl;break; } }
}
五、测试结果 图一 图二 图三 图四 图五 图六 图七 图八 图九 图十 图十一
六、总结 栈是一种操作受限的线性表虽然操作受限但是与线性表有点类似只不过栈的插入和删除都在表尾而已。而我在本文中实现的顺序栈有点类似顺序表。我们也需要注意到顺序栈虽然实现简单但是其容易发生溢出在栈满的时候还要入栈则会上溢而在栈空的时候还要出栈则会下溢针对这个问题我将在下一篇文章的链栈解决这个问题。
