数据结构-stack的基本操作

2025-02-08 技术教程

包括三个文件：stack.h，stack.cpp,main.cpp

stack.h

#include"stdio.h"#include<stdlib.h>#include<malloc.h>#include<string.h>#defineStatusint#defineSElemTypeint#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineOVERFLOW0#defineERROR0#defineOK1//typedefstruct{SElemType*base;//指向栈尾SElemType*top;//指向栈顶intstacksize;//记录栈元素个数}SqStack;//////栈的基本操作////初始化栈StatusInitStack(SqStack&S);//返回1，表示成功；返回0表示不成功//判栈满StatusIsFull(SqStack&S);//判栈空StatusIsEmpty(SqStack&S);//如空，返回1；非空返回0//入栈StatusPush(SqStack&S,SElemTypee);//出栈StatusPop(SqStack&S,SElemType&e);//显示栈元素StatusStackTraverse(SqStack&S);//访问栈顶StatusGetTop(SqStack&S,SElemType&e);//求栈长度intStackLength(SqStack&S);//清空栈StatusClearStack(SqStack&S);//销毁栈StatusDestroyStack(SqStack&S);

stack.cpp

#include"stack.h"#include"stdio.h"#include<stdlib.h>#include<malloc.h>#include<iostream>usingnamespacestd;//栈的基本操作//////初始化栈StatusInitStack(SqStack&S){//构造一个空栈S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)return(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}//判栈满StatusIsFull(SqStack&S){//若满返回1，否则返回0if((S.top-S.base)>=S.stacksize)//若栈满{//cout<<"栈满"<<endl;return1;}elsereturn0;}//判空StatusIsEmpty(SqStack&S){//若栈空返回1，否则返回0if(S.top==S.base){//cout<<"栈空"<<endl;return1;}elsereturn0;}//入栈StatusPush(SqStack&S,SElemTypee){//将e插入栈顶//判满，加空间if(IsFull(S)==1){S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));if(S.base==NULL)return(OVERFLOW);S.top=S.base+S.stacksize;//top指针移动到新位置S.stacksize=S.stacksize+STACKINCREMENT;//栈空间扩容}*S.top=e;//栈顶元素赋值S.top++;//top指针上移//入栈return0;}//出栈StatusPop(SqStack&S,SElemType&e){//弹出栈顶元素，并用e接收//判空if(IsEmpty(S)==1)return(ERROR);//弹出S.top--;e=*S.top;//等价于e=*(--top)returnOK;}//显示栈中元素StatusStackTraverse(SqStack&S){//cout<<"遍历栈元素"<<endl;SElemType*p;p=S.base;while(p!=S.top){cout<<*p<<"";p++;}cout<<endl;cout<<"遍历完毕！"<<endl;return0;}//取栈顶元素StatusGetTop(SqStack&S,SElemType&e){//若栈空返回ERROR,否则返回1if(IsEmpty(S)==1)returnERROR;S.top--;e=*S.top;returnOK;}//求长度intStackLength(SqStack&S){returnS.top-S.base;}//清空栈StatusClearStack(SqStack&S){S.top=S.base;//cout<<"已清空栈"<<endl;returnOK;}//销毁栈StatusDestroyStack(SqStack&S){free(S.base);S.top=NULL;S.base=NULL;S.stacksize=0;cout<<"已销毁栈"<<endl;returnOK;}

main.cpp

#include<iostream>#include"stack.h"usingnamespacestd;intmain(){/*SqStacksta;InitStack(sta);cout<<IsEmpty(sta)<<endl;Push(sta,'a');Push(sta,'b');Push(sta,'c');Push(sta,'d');cout<<"栈长度为:"<<StackLength(sta)<<endl;StackTraverse(sta);cout<<IsEmpty(sta)<<endl;SElemTypee;Pop(sta,e);cout<<"栈长度为:"<<StackLength(sta)<<endl;cout<<"e="<<e<<endl;StackTraverse(sta);GetTop(sta,e);cout<<"e="<<e<<endl;cout<<"栈长度为:"<<StackLength(sta)<<endl;ClearStack(sta);cout<<"栈长度为:"<<StackLength(sta)<<endl;Push(sta,'a');Push(sta,'b');Push(sta,'c');Push(sta,'d');StackTraverse(sta);cout<<"栈长度为:"<<StackLength(sta)<<endl;DestroyStack(sta);//cout<<"栈长度为:"<<StackLength(sta)<<endl;*//*//需求：将一个十进制转换为二进制voidconversion();conversion();//cout<<"栈长度为:"<<StackLength(sta)<<endl;*///需求：行编程程序/*voidLineEdit();LineEdit();*///需求：后缀表达式求值34+5*7/charstr[100];fgets(str,100,stdin);//从标准输入获取字符串intres=0;intReverseCal(char*);//函数声明res=ReverseCal(str);//函数调用cout<<"res="<<res<<endl;system("pause");return(0);}intPrecede(char*c1,char*c2){//大于返回1,小于返回-1，等于返回0if(*c1=='*'){if(*c2=='+')return1;if(*c2=='-')return1;if(*c2=='*')return0;if(*c2=='/')return0;}if(*c1=='/'){if(*c2=='+')return1;if(*c2=='-')return1;if(*c2=='*')return0;if(*c2=='/')return0;}if(*c1=='+'){if(*c2=='+')return0;if(*c2=='-')return0;if(*c2=='*')return-1;if(*c2=='/')return-1;}if(*c1=='-'){if(*c2=='+')return0;if(*c2=='-')return0;if(*c2=='*')return-1;if(*c2=='/')return-1;}}char*InffixToSuffix(char*s){//将中缀表达式转换为后缀表达式SqStackOPTR;//操作符栈SqStackOPND;//操作数栈InitStack(OPTR);InitStack(OPND);Push(OPTR,'#');char*p=s;while(*p!='\0'){switch(*p){//如果不是运算符（是数字），入栈//如果是运算符，比较符合栈的操作符，再做}p++;}returns;}intReverseCal(char*s){//逆波兰式计算器SqStacksta;InitStack(sta);//初始化话一个栈结构intres;inta,b;char*p=s;p=strtok(s,"");//分解字符串Push(sta,atoi(p));//atoi()函数将字符串转换为intwhile((p=strtok(NULL,""))!='\0'){switch(*p){case'+':Pop(sta,b);Pop(sta,a);res=a+b;Push(sta,res);//将结果入栈break;case'-':Pop(sta,b);Pop(sta,a);res=a-b;Push(sta,res);break;case'*':Pop(sta,b);Pop(sta,a);res=a*b;Push(sta,res);break;case'/':Pop(sta,b);Pop(sta,a);res=a/b;Push(sta,res);break;default:Push(sta,atoi(p));//如果获取数字直接入栈}}returnres;}/*voidLineEdit(){//行编辑函数cout<<"请输入字符:"<<endl;SqStacksta;InitStack(sta);//初始化话一个栈结构charch,e;ch=getchar();//cout<<ch;while(ch!=EOF&&ch!='\n'){switch(ch){case'#':Pop(sta,e);//若输入#,回退一格break;case'@':ClearStack(sta);//若输入@,回退一行break;default:Push(sta,ch);break;}ch=getchar();}StackTraverse(sta);//遍历栈元素DestroyStack(sta);//销毁栈}//行编辑函数*/voidconversion(){//进制转换程序intN;cout<<"请输入一个正整数:"<<endl;cin>>N;SqStacksta;InitStack(sta);while(N!=0){Push(sta,N%2);//求余N=N/2;//整除}//StackTraverse(sta);cout<<"对应的二进制为:"<<endl;while(IsEmpty(sta)!=1){SElemTypee;Pop(sta,e);cout<<e<<"";}cout<<endl;}