🎯目的：
1、掌握栈的顺序表示和实现。
2、掌握栈的链式表示和实现。
🎯内容：
1、栈的顺序表示和实现。
2、栈的链式表示和实现。
🎯环境：
TC或VC++。
🎯顺序栈步骤：
🎐1.栈的顺序表示和实现
编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：
- 1初始化顺序栈
- 3删除栈顶元素
- 4取栈顶元素
🎆注意要点：
顺序栈，入栈时需判断栈是否为满，栈满时不能入栈，否则出现空间溢出；出栈时需判断栈是否为空，为空时不能操作，否则产生错误；取栈顶元素与遍历之前也要判断栈是否为空。
typedef struct { SElemType *base;//栈底指针 SElemType *top;//栈顶指针 int stacksize;//栈可用的最大容量 } SqStack;
🎯顺序栈完整代码：
//顺序栈 #include "iostream" using namespace std; #define MAXSIZE 100 #define OK 1 #define ERROR 0; #define OVERFLOW -1 typedef int Status; typedef char SElemType ; typedef struct{//定义顺序栈 SElemType *base; SElemType *top; int stacksize; }SqStack; Status InitStack(SqStack &S){//顺序栈的初始化 S.base=new SElemType [MAXSIZE]; if(!S.base) exit(OVERFLOW); S.top=S.base; S.stacksize=MAXSIZE; return OK; } Status Push(SqStack &S,SElemType e){//顺序栈的入栈 if(S.top-S.base==S.stacksize) return ERROR; *S.top++=e; return OK; } Status Pop(SqStack &S,SElemType &e){//顺序表的出栈 if(S.top==S.base) return OK; e=*--S.top; return OK; } SElemType GetTop(SqStack S){//取栈顶元素 if(S.base!=S.top) return *(S.top-1); } void StackTraverse(SqStack S){//遍历顺序栈 SElemType *p; p=S.top; cout<<"顺序栈的元素为:"; while(p!=S.base){ p--; printf("%2c ",*p); } cout<<endl; } void CleanStack(SqStack &S){//置空栈 if(S.base) { S.top=S.base; cout<<"恭喜您，栈已清空"<<endl; } else cout<<"栈不存在"<<endl; } bool isValid(char op[]){ SqStack T; InitStack(T);//初始化 int i=0; while(op[i]!='\0'){ if(op[i]=='I') Push(T,op[i]); else if(op[i]=='O'){ char c; if(Pop(T,c)!=OK||c!='I') return false; } i++; } if(T.top==T.base) return true; else return false; } int main(){ SqStack s; int choose=-1; SElemType e,n; cout<<"1.初始化顺序栈\n2.插入元素\n3.删除栈顶元素\n4.取栈顶元素\n5.遍历栈\n6.置空栈\n7.检验IO操作是否合法\n0.退出"<<endl; cout<<"提示:入栈时只能输入单个字符"<<endl; cout<<"-----------------------------"<<endl; while(choose!=0){ cout<<"请输入您的选择:"; cin>>choose; switch(choose){ case 1: if(InitStack(s)==1){ cout<<"恭喜您初始化成功"<<endl; } else cout<<"很遗憾初始化失败"<<endl; break; case 2: cout<<"请输入您要插入的元素："; cin>>e; if(Push(s,e)==1) cout<<"恭喜您插入成功"<<endl; else cout<<"很遗憾插入失败"<<endl; break; case 3: if(Pop(s,e)==1){ cout<<"恭喜您删除栈顶元素成功"<<endl; cout<<"删除的栈顶元素为:"<<e<<endl; } else cout<<"很遗憾删除栈顶元素失败"<<endl; break; case 4: if(s.base==s.top) cout<<"您的栈已空"<<endl; else{ n=GetTop(s); cout<<"栈顶元素为:"<<n<<endl; } break; case 5: if(s.base==s.top) cout<<"您的栈已空"<<endl; else{ StackTraverse(s); } break; case 6: CleanStack(s); break; case 7: char op[MAXSIZE]; cout<<"请输入要检验的序列"; cin>>op; if(isValid(op)) cout<<"输入的序列合法"<<endl; else cout<<"输入的序列不合法"<<endl; break; case 0: cout<<"恭喜您已退出"<<endl; break; default: cout<<"输入错误，请您重新输入"<<endl; } } return 0; }
🎯链栈步骤：
🎐2.栈的链式表示和实现
链栈的存储结构定义：
typedef struct StackNode { SElemType data; struct StackNode *next; } StackNode, *LinkStack;
- 1链栈的初始化
🎆注意要点：
链栈，出栈时需判断栈是否为空，为空时不能操作，否则产生错误；取栈顶元素与遍历之前也要判断栈是否为空。
🎯链栈完整代码：
//链栈 #include "iostream" using namespace std; #define OK 1 #define OVERFLOW -1 #define ERROR 0 #define MAXSIZE 100 typedef int Status; typedef char SElemType; typedef struct StackNode{//定义栈 SElemType data; struct StackNode *next; }StackNode,*LinkStack; Status InitStack(LinkStack &S){//链栈的初始化 S=NULL; return OK; } Status Push(LinkStack &S,SElemType e){//入栈 LinkStack p; p=new StackNode; p->data=e; p->next=S; S=p; return OK; } Status Pop(LinkStack &S,SElemType &e){//出栈 if(S==NULL) return ERROR; LinkStack p; e=S->data; p=S; S=S->next; delete p; return OK; } SElemType GetTop(LinkStack S){//取栈顶元素 if(S!=NULL) return S->data; } void TraverseList(LinkStack S){//遍历链栈 LinkStack p; p=S; if(p){ cout<<p->data<<endl; TraverseList(p->next); } } Status ClearStack(LinkStack &S){//置空链栈 LinkStack p; if(S=NULL) return ERROR; while(S!=NULL){ p=S; S=S->next; delete p; } return OK; } bool isValid(char op[]){ LinkStack T; InitStack(T);//初始化 int i=0; while(op[i]!='\0'){ if(op[i]=='I') Push(T,op[i]); else if(op[i]=='O'){ char c; if(Pop(T,c)!=OK||c!='I') return false; } i++; } if(T==NULL) return true; else return false; } int main(){ LinkStack s; SElemType e; int choose=-1; SElemType n; cout<<"1.链栈的初始化\n2.入栈\n3.出栈\n4.取栈顶元素\n5.遍历栈\n6.置空栈\n7.检验IO操作是否合法\n0.退出\n"; cout<<"特别注意：入栈时只可以是单个字符！！！"<<endl; cout<<"----------------------------"<<endl; while(choose!=0){ cout<<"请输入您的选择:"; cin>>choose; switch(choose){ case 1: if(InitStack(s)==1) cout<<"恭喜您初始化成功"<<endl; else cout<<"很遗憾初始化失败"<<endl; break; case 2: cout<<"请输入您要入栈的元素:"; cin>>e; if(Push(s,e)==1) cout<<"恭喜您入栈成功"<<endl; else cout<<"很遗憾入栈失败"<<endl; break; case 3: if(Pop(s,e)==1){ cout<<"恭喜您出栈成功"<<endl; cout<<"出栈元素为:"<<e<<endl; } else cout<<"很遗憾出栈失败"<<endl; break; case 4: if(s==NULL) cout<<"您的栈已空"<<endl; else{ n=GetTop(s); cout<<"栈顶元素为:"<<n<<endl; } break; case 5: if(s==NULL) cout<<"您的栈已空"<<endl; else{ cout<<"链栈中的元素为:"<<endl; TraverseList(s); } break; case 6: if(ClearStack(s)==1) cout<<"恭喜您栈已置空"<<endl; else cout<<"很遗憾栈不存在"<<endl; break; case 7: char op[MAXSIZE]; cout<<"请输入要检验的序列"; cin>>op; if(isValid(op)) cout<<"输入的序列合法"<<endl; else cout<<"输入的序列不合法"<<endl; break; case 0: cout<<"恭喜您已退出"<<endl; break; default: cout<<"输入错误，请重新输入"<<endl; } } }
[附加题]
1、假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序、列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。
下面所示的序列中哪些是合法的？
A. IOIIOIOO
B. IOOIOIIO
C. IIIOIOIO
D. IIIOOIOO
通过对以上序列的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false (假定被判定的操作序列巳存入一维字符数组中）。
1. 顺序栈实现检验：
2.链栈实现检验：
