博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
数据结构 顺序栈
阅读量:5863 次
发布时间:2019-06-19

本文共 3790 字,大约阅读时间需要 12 分钟。

做一个豁达而努力的自己。

栈的定义:只能在表的一端(栈顶)进行插入和删除的线性表。

逻辑结构:与线性表相同,仍为一一对应的关系。

存储结构:用顺序栈和链栈存储均可,但以顺序栈更为常见。

运算规则:只能在栈顶(top)进行运算,且访问节点时只能先进后出(FILO),或后进先出(LIFO)的原则。

实现方式:关键是在写压栈和弹栈的函数具体的实现依顺序栈和链栈的不同而不同,基本的操作有压栈,弹栈,读取栈顶元素,建栈,判断栈满,判断栈空等等。

顺序栈的存储结构:

#define MAXSIZE 100typedef struct {    SElemType *base;    //栈底    SElemType *top;     //栈顶    int stacksize;  //顺序栈的存储容量}SqStack;

顺序栈的初始化:

顺序栈初始化即为构造一个空栈,第一步为顺序栈分配存储空间,第二部判断是否分配成功,若分配失败错误,成功则继续,第三部栈顶等于栈底表示为空栈,第四部设置顺序栈的存储空间,初始化成功。

Status InitStack(SqStack &S){    S.base = new SElemType[MAXSIZE];    if(!S.base)        return OVERFLOW;    S.top = S.base;    S.stacksize = MAXSIZE;    return OK;}

判断顺序栈是否为空:

bool StackEmpty(SqStack S){    if(S.base == S.top)        return true;    return false;}

求顺序栈的长度:

int StackLength(SqStack S){    return S.top - S.base;}

清空顺序栈:

Status ClearStack(SqStack &S){    if(S.base != S.top)        S.base = S.top;    return OK;}

销毁顺序栈:

Status DestroyStack(SqStack &S){    if(S.base)    {        delete S.base;        S.stacksize = 0;        S.top = S.base = NULL;    }    return OK;}
顺序栈压栈:

第一步判断顺序栈是否已满,满则返回失败,不满继续,第二步元素e压入栈中,第三部栈顶加一。

Status Push(SqStack &S, SElemType e){    if(S.top - S.base == MAXSIZE)        return ERROR;    *S.top++ = e;   //*S.top = e, S.top++, 先给值,再加一    return OK;}

顺序栈弹栈:

第一步判断顺序栈是否为空,空则返回失败,不空继续,第二步栈顶元素减一,再将位于栈顶位置的元素暂时保存到e中。

Status Pop(SqStack &S, SElemType &e){    if(S.base == S.top)        return ERROR;    e = *--S.top;   //--S.top, e = *S.top, 栈顶先减一, 再把值保存到e中    return OK;}

获取顺序栈栈顶元素:

第一步判断顺序栈是否空,空则返回失败,不空继续,第二步现取栈顶前一个地址的元素给e。

Status GetStack(SqStack S, SElemType &e){    if(S.base == S.top)        return ERROR;    e = *(S.top - 1);    return OK;}

代码:

#include 
#include
using namespace std;#define MAXSIZE 100//顺序栈的存储结构typedef struct{ int *base; //栈底 int *top; //栈顶 int stacksize;}SqStack;//顺序栈的初始化void InitStack(SqStack &S){ S.base = new int[MAXSIZE]; if(!S.base) exit(1); S.top = S.base; S.stacksize = MAXSIZE;}//压栈bool Push(SqStack &S, int e){ if(S.top - S.base == MAXSIZE) return false; *S.top++ = e; return true;}//弹栈bool Pop(SqStack &S, int &e){ if(S.base == S.top) return false; e = *--S.top; return true;}//判断顺序栈是否为空bool StackEmpty(SqStack S){ if(S.base == S.top) return true; return false;}//求顺序栈的长度int StackLength(SqStack S){ return S.top - S.base;}//清空顺序栈void ClearStack(SqStack &S){ if(S.base) S.top = S.base;}//销毁顺序栈void DestroyStack(SqStack &S){ if(S.base) { delete S.base; S.stacksize = 0; S.base = S.top = NULL; }}//获取栈顶元素bool GetStack(SqStack S, int &e){ if(S.base == S.top) return false; e = *(S.top - 1); return true;}//输出顺序栈void PrintStack(SqStack S){ while(S.base != S.top) cout << *S.base++ << '\t'; cout << endl;}int main(){ SqStack S; InitStack(S); if(StackEmpty(S)) cout << "顺序栈为空" << endl; else cout << "顺序栈不为空" << endl; int n; cout << "输入元素的个数:"; cin >> n; int e; while(n--) { cin >> e; if(Push(S, e)) ; else cout << "压栈失败" << endl; } PrintStack(S); cout << "弹出一个数据" << endl; if(Pop(S, e)) ; else cout << "弹栈失败" << endl; cout << "长度为:"; cout << StackLength(S) << endl; if(GetStack(S, e)) cout << "栈顶元素为:" << e << endl; else cout << "获取栈顶元素失败" << endl; if(StackEmpty(S)) cout << "栈为空" << endl; else cout << "栈不为空" << endl; cout << "清空栈" << endl; ClearStack(S); if(StackEmpty(S)) cout << "栈为空" << endl; else cout << "栈不为空" << endl; cout << "栈长为:"; cout << StackLength(S) << endl; cout << "销毁栈" << endl; DestroyStack(S); return 0;}

转载于:https://www.cnblogs.com/KogetsuChida/p/10410005.html

你可能感兴趣的文章
代码互审
查看>>
铅酸蓄电池正确使用与充电管理
查看>>
jmeter ssh+jdbc用法
查看>>
微信小程序将view动态填满全屏
查看>>
Android 系统设置中显示设置之亮度调节篇
查看>>
Android 内嵌 webview测试
查看>>
IOS-WebViewJavascriptBridge使用说明
查看>>
python 如何在一个for循环中遍历两个列表
查看>>
(转)Android环境变量的设置
查看>>
java开发中使用枚举表述数据字典
查看>>
三维扫描 FZU 1063
查看>>
window onload || jquery $()
查看>>
排查私有API
查看>>
[git] BabyBluetooth
查看>>
使用IDEA工具创建本地项目并且上传到码云
查看>>
UVA 512 Spreadsheet Tracking
查看>>
关于DropDownList
查看>>
【ocp-12c】最新Oracle OCP-071考试题库(47题)
查看>>
用eclipse编写Hadoop程序
查看>>
WP7->界面->ListBox动态加载,滚动到底部时触发事件
查看>>