因为栈底位置是固定不变的,所以可以将栈底位置设置在数组的两端的任何一个端点;栈顶位置是随着进栈和退栈操作而变化的,故需要一个变量top来指示当前栈顶的位置,通常称top为栈顶指针。 算法思想: 算法思想 算法思想 1、链式存储方式表示的栈称链栈 算法思想: 算法思想: 算法思想:
【数据结构——栈篇】
目录
一、栈的顺序存储——顺序栈
1、顺序栈的表示和实现
2、顺序栈的定义
#define MAXSIZE 100 typedef struct { SElemType* base;//栈底指针 SElemType* top;//栈顶指针 int stacksize;//可使用的最大容量 }SqStack; SqStack S;//定义顺序栈 S.stacksize = s;//栈的大小 S.base == S.top;//空栈 S.top - S.base == stacksize;//满栈
2、顺序栈初始化
1、分配空间并检查空间是否分配成功,否则返回错误
2、栈顶指针top初始化为栈底指针base
3、stacksize = 栈的最大容量Status IniStack(SqStack& S) { S.base = new SElemType[MAXSIZE];//分配空间 if (!S.base) exit(OVERFLOW);//分配失败,返回错误 S.top = S.base;//栈顶指针初始化为栈底指针 S.stacksize = MAXSIZE;//初始化栈的最大容量 return OK; }
3、顺序栈入栈
1、判断是否栈满,若满则出错
2、新元素e压入栈顶
3、栈顶指针+1Status Push(SqStack& S, SElemType e) { if (S.top - S.base == S.stacksize) return ERROR;//栈满 *S.top = e;//新元素e压入栈顶 S.top++;//栈顶指针+1 return OK; }
4、顺序栈出栈
1、判断是否栈空,若空则出错
2、栈顶指针-1
3、获取栈顶元素eStatus Pop(SqStack& S, SElemType& e) { if (S.top == S.base) return ERROR;//栈空报错 --S.top;//栈顶指针-1 e = *S.top;//获取栈顶元素e return OK; }
5、取顺序栈栈顶元素
SElemType GetTop(SqStack S) { if (S.top != S.base)//栈非空 return *(S.top - 1);//返回栈顶元素的值 //栈顶指针不变 }
6、输出栈内容
void OutPut_SqS(SqStack S) { SElemType* p; if (S.top == S.base) printf("空栈!n"); else for (p = S.top - 1;p >= S.base;p--) printf("%dn", *p); }
二、栈的链式存储——链栈
2、运算受限的单链表
3、链表的头指针就是栈顶
4、不需要头结点
5、插入与删除仅在栈顶执行1、链栈的存储结构
typedef struct StackNode { SElemType data; struct StackNode* next; }StackNode,*LinkStack; LinkStack S;
2、栈链的初始化
1、不需要头结点
2、链栈的头指针就是栈顶
3、栈链无栈满问题,空间可扩充
4、空栈相当于头指针指向NULLStatus IniStack(LinkStack& S) {//构造一个空栈,栈顶指针置空 S = NULL; return OK; }
3、链栈的入栈
1、为入栈元素e分配空间,用指针p指向
2、将新结点指针域置为e
3、将新结点插入栈顶
4、修改栈顶指针为pStatus Push(LinkStack& S, SElemType e) { p = new StackNode;//生成新结点 p->data = e;//将新结点数据域置为e p->next = S;//将新结点插入栈顶 S = p;//修改栈顶指针为p return OK; }
4、链栈的出栈
1、判断是否是空栈,若是空栈,返回错误
2、将栈顶元素赋值给e
3、临时保存栈顶元素的空间,以备释放
4、修改栈顶指针,指向新的栈顶元素
5、释放原栈顶元素的空间Status Pop(LinkStack& S, SElemType& e) { if (S == NULL) return ERROR;//栈空 e = S->data;//将栈顶元素存储到e中 p = S;//用p临时保存栈顶元素的空间,以备释放 S = S->next;//修改栈顶指针 delete p;//释放原栈顶元素的空间 return OK; }
5、取链栈栈顶元素
SElemType GetTop(LinkStack S) { if (S != NULL) return S->data; }
6、输出链栈的内容
void OutPut(LinkStack S) { p = S; if (!p) printf("空栈!"); else while (p) { printf("%d", p->data); p = p->next; } }
本网页所有视频内容由 imoviebox边看边下-网页视频下载, iurlBox网页地址收藏管理器 下载并得到。
ImovieBox网页视频下载器 下载地址: ImovieBox网页视频下载器-最新版本下载
本文章由: imapbox邮箱云存储,邮箱网盘,ImageBox 图片批量下载器,网页图片批量下载专家,网页图片批量下载器,获取到文章图片,imoviebox网页视频批量下载器,下载视频内容,为您提供.
阅读和此文章类似的: 全球云计算