栈（考研复习）

一、采用顺序存储结构实现栈即顺序栈总结Stack.h#pragmaonce#includestdio.h#includestdbool.h#defineMaxSize10typedefintElemType;// 采用顺序结构实现栈// 定义栈的结构typedefstructSqStack{ElemType arr[MaxSize];// 栈中最多可以存储MaxSize个ElemType类型的数据inttop;// top是栈顶指针指向栈顶元素}SqStack;// 栈的初始化voidInit(SqStackS);// 判断栈是否为空。为空返回true否则返回false。boolEmpty(SqStack S);// 新元素x入栈boolPush(SqStackS,ElemType x);// 删除栈顶元素(出栈操作),并将栈顶元素的值赋给变量eboolPop(SqStackS,ElemTypee);// 获取栈顶元素并将栈顶元素的值赋给变量eboolGetTop(SqStack S,ElemTypee);Stack.cpp#define_CRT_SECURE_NO_WARNINGS1#includeStack.h// 栈的初始化voidInit(SqStackS){S.top-1;}// 判断栈是否为空。为空返回true否则返回falseboolEmpty(SqStack S){if(S.top-1)returntrue;// 栈为空elsereturnfalse;// 栈不为空}// 新元素x入栈boolPush(SqStackS,ElemType x){if(S.topMaxSize-1)// 此时表示栈中已经存满了元素无法执行入栈操作returnfalse;S.top;S.arr[S.top]x;// 将新元素x放到栈顶的位置returntrue;}// 删除栈顶元素(出栈操作),并将栈顶元素的值赋给变量eboolPop(SqStackS,ElemTypee){if(S.top-1)// 表示此时栈为空无法执行出栈操作returnfalse;eS.arr[S.top];// 将栈顶元素赋给eS.top--;returntrue;}// 获取栈顶元素并将栈顶元素的值赋给变量eboolGetTop(SqStack S,ElemTypee){if(S.top-1)returnfalse;// 表示栈为空无法指向获取栈顶元素的操作eS.arr[S.top];returntrue;}二、共享栈共享栈就是两个栈共享同一片空间// 定义共享栈的结构(两个栈共享同一块内存这两个栈分别命名为0号栈与1号栈)#defineMaxSize10typedefintElmeType;typedefstructShStack{ElmeType data[MaxSize];inttop0;// 0号栈的栈顶指针inttop1;// 1号栈的栈顶指针}ShStack;// 共享栈的初始化voidInitStack(ShStackS){S.top0-1;S.top1MaxSize;}// 共享栈满了的条件S.top01 S.top1三、掌握算法思想即可不用写代码2025年02考了算法题栈在括号匹配中的应用#define_CRT_SECURE_NO_WARNINGS1#defineMaxSize10typedefcharElemType;// 采用顺序结构实现栈// 定义栈的结构typedefstructSqStack{ElemType arr[MaxSize];// 栈中最多可以存储MaxSize个ElemType类型的数据inttop;// top是栈顶指针指向栈顶元素}SqStack;// 栈的初始化voidInit(SqStackS){S.top-1;}// 判断栈是否为空。为空返回true否则返回falseboolEmpty(SqStack S){if(S.top-1)returntrue;// 栈为空elsereturnfalse;// 栈不为空}// 新元素x入栈boolPush(SqStackS,ElemType x){if(S.topMaxSize-1)// 此时表示栈中已经存满了元素无法执行入栈操作returnfalse;S.top;S.arr[S.top]x;// 将新元素x放到栈顶的位置returntrue;}// 删除栈顶元素(出栈操作),并将栈顶元素的值赋给变量eboolPop(SqStackS,ElemTypee){if(S.top-1)// 表示此时栈为空无法执行出栈操作returnfalse;eS.arr[S.top];// 将栈顶元素赋给eS.top--;returntrue;}// 字符数组str存储length个括号字符若这些括号字符是匹配的,就返回true,否则返回falseboolbracketCheck(charstr[],intlength){// 创建一个栈SqStack s;// 对栈进行初始化Init(s);for(inti0;ilength;i){// 当遍历到左括号就让左括号入栈if(str[i]{||str[i][||str[i](){Push(s,str[i]);}else// 当遍历到右括号时就让栈顶的左括号出栈看看是否与右括号匹配{if(Empty(s))// 栈顶的左括号出栈前要判断栈此时是否为空如果为空直接返回falsereturnfalse;chartemp;Pop(s,temp);;// 让栈顶元素出栈并将栈顶元素的值赋给tempif(temp(str[i]!))returnfalse;if(temp[str[i]!])returnfalse;if(temp{str[i]!})returnfalse;}}// 当所有的括号遍历完之后如果此时栈为空表示括号匹配成功否则匹配失败returnEmpty(s);}