搭建一个网站 优帮云/漯河seo公司

1. 逻辑结构

1. 栈（stack）：是仅限定在表尾进行插入和删除操作的线性表。
2. 栈顶：允许插入和删除的一端称为栈顶。
3. 栈底：不允许操作的一端称为栈底。
4. 空栈：不含任何数据元素的栈称为空栈。
5. 栈是一种后进先出的线性表。
6. 栈的插入操作称为进栈，压栈，入栈。
7. 栈的删除操作称为出栈、弹栈。

2. 物理结构

1. 顺序存储

#define Status int
#define ElemType int
#define MaxSize 50
#define OK 1
#define ERROR 0
typedef struct {ElemType data[MaxSize];int top;//top始终指向栈顶元素 栈空时指向-1
}SqStack;

顺序存储结构受限于MaxSize大小，数据过多可能会发生溢出。但是操作、结构相对简单。

2. 链式存储

#define ElemType int
#define MaxSize 50
#define Status int
#define OK 1
#define ERROR 0
typedef struct LNode{ElemType data;struct LNode* next;
}LinkStack;

链式存储的栈通常用没有头结点的单链表，头指针top指向第一个节点，第一个节点就是栈顶，所有操作都在栈顶完成。

3. 共享栈

共享栈：指两个栈共享空间，如下图：

#define ElemType int
#define MaxSize 50
#define Status int
#define OK 1
#define ERROR 0
typedef struct LNode {ElemType data[MaxSize];int top0;//初始指向0int top1;//初试指向MaxSize-1
}SqStack;

关于共享栈的抽象数据类型与顺序栈相差不大，只是要指定0号栈还是1号栈的问题，所以此处不表。

3. 抽象数据类型(操作、算法)

1. 顺序存储的抽象数据类型

1. 初始化栈：就是把栈顶指针置为-1即可

   Status initStack(SqStack &S) {S.top = -1;return OK;
   }
   

2. 判断栈空

   /*
   判断栈是否空，空返回1，非空返回0
   */
   Status StackEmpty(SqStack S) {if (S.top == -1) return OK;else return ERROR;
   }
   

3. 入栈：将元素压入栈中

   /*入栈*/
   Status Push(SqStack &S, ElemType e) {if (S.top == MaxSize - 1)return ERROR;S.top++;	//注意指针先加然后再赋值使指针始终指向栈顶S.data[S.top] = e;return OK;
   }

4. 出栈：将元素弹出

   /*将元素弹出栈，并把值赋给e*/
   Status Pop(SqStack& S, ElemType& e) {if (StackEmpty(S)) return ERROR;e = S.data[S.top];	//先赋值给e再top--保证top指向栈顶S.top--;return OK;
   }
   

5. 读栈顶元素(并不取出)

   /*取栈顶元素，不弹出*/
   Status GetTop(SqStack S, ElemType &e) {if (StackEmpty(S)) return ERROR;e = S.data[S.top];return OK;
   }
   

6. 由于顺序存储的栈结构简单，它的操作算法也十分简单，我们写一个小例来验证一下刚才实现的抽象数据类型(操作算法)

   Status StackPrint(SqStack S) {ElemType e;cout << "打印栈（从栈顶向栈底打印）："<<endl;while (!StackEmpty(S)) {Pop(S, e);cout << e;cout << "\t";}cout << "\t" << endl;return OK;
   }
   int main() {SqStack S ;ElemType e;initStack(S);cout << "压入3，2，1:" << endl;Push(S, 4);Push(S, 3);Push(S, 2);Push(S, 1);StackPrint(S);cout << "栈顶是：" << endl;GetTop(S, e);cout << e << endl;
   }
   

   

2. 链式存储的抽象数据类型

2.1 初始化栈：链栈不需要初始化，LinkStack S=NULL；就行，此时是空栈。

2.2进出栈

Status Push(LinkStack &S, ElemType e) {LNode* s = NULL;s = (LNode*)malloc(sizeof(LNode));if (!s) return ERROR;s->data = e;s->next = S;S = s;return OK;}Status Pop(LinkStack& S, ElemType &e) {if (!S) return ERROR;e = S->data;S = S->next;return OK;
}int main() {LinkStack S = NULL;int e;Push(S, 1);Push(S, 2);Push(S, 3);cout << "pop3次" << endl;Pop(S, e);cout << e << endl;Pop(S, e);cout << e << endl;Pop(S, e);cout << e << endl;}

其他操作也很简单，链式栈一般没有顺序栈重要。

4.栈的应用

4.1括号匹配

栈的特性十分适用于括号匹配，什么是括号匹配呢？{},[],()由这六个符号构成的一串字符串，我们判定它是不是有效字符串，有效字符串的意思是：同样类型的左阔号与右括号相邻就可以消除，最后若字符串全部被消除，则是有效字符串。如([{}{}])是有效字符串。([{]})是无效字符串。

算法思想：

1.初始化一个空栈，遇到左阔号压入栈中。

2.遇到右阔号与栈顶符号相匹配则栈顶符号出栈，否则右阔号进栈。

3.算法结束时栈空则是有效字符串，否则是无效字符串。

代码：

首先我们需要一个物理结构，把顺序栈的ElemType改为char

#define ElemType char
#define MaxSize 50
#define OK 1
#define ERROR 0
#define Status int
typedef struct {ElemType data[MaxSize];int top;
}SqStack;

由于之前实现的抽象数据类型ElemType是int，我们需要把ElemType改为char，就可以直接用了。实现算法如下

Status PMatch(SqStack S) {Status StackEmpty(SqStack S);Status Push(SqStack & S, ElemType e);Status Pop(SqStack & S, ElemType & e);Status GetTop(SqStack S, ElemType & e);ElemType e;ElemType s= NULL;cout << "请输入阔号字符串：" << endl;cin >> e;while (e != '#') {if (e == '[' || e == '{' || e == '(') {Push(S, e);}else if (e == ']') {if (!GetTop(S, s)) return ERROR;if (s == '[') Pop(S, s);else Push(S, e);}else if (e == '}') {if (!GetTop(S, s)) return ERROR;if (s == '{') Pop(S, s);else Push(S, e);}else if (e == ')') {if (!GetTop(S, s)) return ERROR;if (s == '(') Pop(S, s);else Push(S, e);}else cout << "请输入正确字符：" << endl;cin >> e;}if (StackEmpty(S)) return OK;else return ERROR;
}int main() {Status initStack(SqStack & S);SqStack S;initStack(S);if (PMatch(S) == OK) cout << "有效字符串" << endl;else cout << "无效字符串" << endl;}

4.2表达式求值

问题描述：通过算法实现加减乘除四则运算，其中还有括号的匹配，例如输入3 + 2 * 5+(5 - 2)*2求出值。

4.2.1 前缀、中缀、后缀表达式的原理直接去看表达式求值视频讲解，文字的表达能力有限，我们这里直接实现算法。

4.2.2 中缀转后缀

算法：

遍历字符串：

遇到操作数：直接加入后缀表达式。

遇到界限符：左括号压入栈，右括号弹出相应左括号之前的运算符加到后缀表达式后面，弹出左括号。

遇到运算符：弹出栈中优先级高于或等于该运算符的运算符加入后缀表达式。遇到左括号或栈空为止。接下来把该运算符压入栈中。

遍历所有字符后，将栈依次弹出加入后缀表达式。

（因为输入的原因操作数只能支持0~9，大家稍微改变输入可以扩充到实数）

代码相对要复杂一点，不很理解原理很好写出代码，比较判断多了一点，代码中有大量注释，完全可以看懂。

#include<iostream>
#include"SqStack.h"
using namespace std;
#define ExpressionLength 30/*判断字符种类*/
Status whichkind(char e) {if (e == '('  || e == '{'  || e == '[' ) {return 1;}else if (e == '+' || e == '-' || e == '/' || e == '*') {return 2;}else if (e <= 57 && e >= 48) return 3;else if (e == ')' || e == '}' || e == ']') {return 4;}else {cout << "输入错误！" << endl;exit(1);}
}
/*比较运算符,若b等级大于等于a则返回1否则返回0*/
Status level(char a, char b) {if (a == '+' || a == '-') {//return OK;}else if (a == '*' || a == '/') {if (b == '*' || b == '/') {return OK;}}else {cout << "输入错误！" << endl;exit(1);}return ERROR;}/*中缀转后缀表达式*/
string ReversePoland(string s) {Status StackEmpty(SqStack S);Status Push(SqStack & S, ElemType e);Status Pop(SqStack & S, ElemType & e);Status GetTop(SqStack S, ElemType & e);Status initStack(SqStack & S);char a[ExpressionLength] = { '\0' };//后缀表达式数组int a_count = 0;SqStack S;initStack(S);char e;for (int i = 0; i < s.size(); i++) {if (whichkind(s[i]) == 1) {//左括号Push(S, s[i]);}else if (whichkind(s[i]) == 2) {//运算符while (GetTop(S, e)!=0 && whichkind(e)!=1) {//栈不为空且栈顶不是左括号if (level(s[i], e) == OK) {//等级高于s[i]Pop(S, e);		//出栈a[a_count++] = e;//加入后缀表达式}else {//栈顶运算符等级低于该运算符break;//循环结束}}//whilePush(S, s[i]);//当前运算符压入栈}else if (whichkind(s[i]) == 3) {//操作数a[a_count++] = s[i];}else if (whichkind(s[i]) == 4) {//右括号while (GetTop(S, e) != 0 && whichkind(e) != 1) {//栈不为空且栈顶不是左括号 一定是匹配的括号否则表达式不合法Pop(S, e);a[a_count++] = e;}Pop(S, e); //取出左括号}else {cout << "程序错误！"<<endl;exit(1);}}//forwhile (StackEmpty(S) != OK) {Pop(S, e);a[a_count++] = e;}string rs = a;return rs;
}int main() {string s;cout << "请输入表达式：" << endl;cin >> s;while (s.compare("#") != 0) {cout << ReversePoland(s) << endl;cout << "请输入表达式：(输入#退出程序)" << endl;cin >> s;}}

打印结果：

4.2.3 表达式求值

算法：

遍历后缀表达式每个字符：

若遇到操作数：直接压入栈中

若遇到运算符：假设操作符为#，依次弹出两个操作数b,a。计算a#b的值压入栈中。

遍历完成后，栈顶值即为表达式的值。

注意以上栈的ElemType都是char，这个部分的栈的ElemType是float,因为涉及除法运算。为此我们需要再写个float栈。并且写几个抽象数据类型(改原来的函数名和参数类型即可)如下：注意不要用相同的函数名,我在前面都加了个float

typedef struct {//用于表达式求值float data[MaxSize];int top;
}FloatSqStack;
Status FloatinitStack(FloatSqStack& S) {S.top = -1;return OK;
}
/*
判断栈是否空，空返回1，非空返回0
*/
Status FloatStackEmpty(FloatSqStack S) {if (S.top == -1) return OK;else return ERROR;
}
/*入栈*/
Status FloatPush(FloatSqStack& S, float e) {if (S.top == MaxSize - 1)return ERROR;S.top++;S.data[S.top] = e;return OK;
}
/*将元素弹出栈，并把值赋给e*/
Status FloatPop(FloatSqStack& S, float& e) {if (FloatStackEmpty(S)) return ERROR;e = S.data[S.top];S.top--;return OK;
}
/*取栈顶元素，不弹出*/
Status FloatGetTop(FloatSqStack S, float& e) {if (FloatStackEmpty(S)) return ERROR;e = S.data[S.top];return OK;
}

然后是求值算法(比求后缀表达式简单)：

/*求a e b的值 e是运算符*/
float compute(float a, float b, char e) {if (e == '+') return a + b;else if (e == '-') return a - b;else if (e == '*') return a * b;else {return a / b;}
}float ExpressionEvaluation(string s) {string rs = ReversePoland(s);FloatSqStack S;FloatinitStack(S);float a,b;for (int i = 0; i < rs.size(); i++) {if (whichkind(rs[i])==3) {//操作数float x = float(int(rs[i]) - 48);//字符转为浮点数FloatPush(S, x);}else if (whichkind(rs[i]) == 2) {//运算符FloatPop(S, b);//先弹出bFloatPop(S, a);//后弹出aFloatPush(S, compute(a, b, rs[i]));}else {cout << "程序错误！" << endl;exit(1);}}//forreturn S.data[S.top];
}int main() {string s;cout << "请输入表达式：" << endl;cin >> s;while (s.compare("#") != 0) {cout << "表达式值为：" << endl;cout << ExpressionEvaluation(s) << endl;cout << "请输入表达式：(输入#退出程序)" << endl;cin >> s;}}

打印结果：

最后把4.1所有代码贴一起：

#include<iostream>
#include"SqStack.h"using namespace std;
#define ExpressionLength 30/*判断字符种类*/
Status whichkind(char e) {if (e == '('  || e == '{'  || e == '[' ) {return 1;}else if (e == '+' || e == '-' || e == '/' || e == '*') {return 2;}else if (e <= 57 && e >= 48) return 3;else if (e == ')' || e == '}' || e == ']') {return 4;}else {cout << "输入错误！" << endl;exit(1);}
}
/*比较运算符,若b等级大于等于a则返回1否则返回0*/
Status level(char a, char b) {if (a == '+' || a == '-') {//return OK;}else if (a == '*' || a == '/') {if (b == '*' || b == '/') {return OK;}}else {cout << "输入错误！" << endl;exit(1);}return ERROR;
}/*中缀转后缀表达式*/
string ReversePoland(string s) {Status StackEmpty(SqStack S);Status Push(SqStack & S, ElemType e);Status Pop(SqStack & S, ElemType & e);Status GetTop(SqStack S, ElemType & e);Status initStack(SqStack & S);char a[ExpressionLength] = { '\0' };//后缀表达式数组int a_count = 0;SqStack S;initStack(S);char e;for (int i = 0; i < s.size(); i++) {if (whichkind(s[i]) == 1) {//左括号Push(S, s[i]);}else if (whichkind(s[i]) == 2) {//运算符while (GetTop(S, e)!=0 && whichkind(e)!=1) {//栈不为空且栈顶不是左括号if (level(s[i], e) == OK) {//等级高于s[i]Pop(S, e);		//出栈a[a_count++] = e;//加入后缀表达式}else {//栈顶运算符等级低于该运算符break;//循环结束}}//whilePush(S, s[i]);//当前运算符压入栈}else if (whichkind(s[i]) == 3) {//操作数a[a_count++] = s[i];}else if (whichkind(s[i]) == 4) {//右括号while (GetTop(S, e) != 0 && whichkind(e) != 1) {//栈不为空且栈顶不是左括号 一定是匹配的括号否则表达式不合法Pop(S, e);a[a_count++] = e;}Pop(S, e); //取出左括号}else {cout << "程序错误！"<<endl;exit(1);}}//forwhile (StackEmpty(S) != OK) {Pop(S, e);a[a_count++] = e;}string rs = a;return rs;
}typedef struct {//用于表达式求值float data[MaxSize];int top;
}FloatSqStack;
Status FloatinitStack(FloatSqStack& S) {S.top = -1;return OK;
}
/*
判断栈是否空，空返回1，非空返回0
*/
Status FloatStackEmpty(FloatSqStack S) {if (S.top == -1) return OK;else return ERROR;
}
/*入栈*/
Status FloatPush(FloatSqStack& S, float e) {if (S.top == MaxSize - 1)return ERROR;S.top++;S.data[S.top] = e;return OK;
}
/*将元素弹出栈，并把值赋给e*/
Status FloatPop(FloatSqStack& S, float& e) {if (FloatStackEmpty(S)) return ERROR;e = S.data[S.top];S.top--;return OK;
}
/*取栈顶元素，不弹出*/
Status FloatGetTop(FloatSqStack S, float& e) {if (FloatStackEmpty(S)) return ERROR;e = S.data[S.top];return OK;
}/*求a e b的值 e是运算符*/
float compute(float a, float b, char e) {if (e == '+') return a + b;else if (e == '-') return a - b;else if (e == '*') return a * b;else {return a / b;}
}float ExpressionEvaluation(string s) {string rs = ReversePoland(s);FloatSqStack S;FloatinitStack(S);float a,b;for (int i = 0; i < rs.size(); i++) {if (whichkind(rs[i])==3) {//操作数float x = float(int(rs[i]) - 48);//字符转为浮点数FloatPush(S, x);}else if (whichkind(rs[i]) == 2) {//运算符FloatPop(S, b);//先弹出bFloatPop(S, a);//后弹出aFloatPush(S, compute(a, b, rs[i]));}else {cout << "程序错误！" << endl;exit(1);}}//forreturn S.data[S.top];
}int main() {string s;cout << "请输入表达式：" << endl;cin >> s;while (s.compare("#") != 0) {cout << "表达式值为：" << endl;cout << ExpressionEvaluation(s) << endl;cout << "请输入表达式：(输入#退出程序)" << endl;cin >> s;}}

4.3 递归

关于递归，默认大家已经非常熟悉了，如果不熟悉就看看语法多练习，这里要说的是递归是用栈来实现的，栈的特性非常适合实现递归。

5. 总结与分析

栈是数据结构中非常基础且重要的一个结构，在许多实际问题中都有其应用，这一章我们主要熟悉顺序栈以及它的各种抽象数据类型就好了。如果能自己手写出表达式求值的代码，那你对栈的理解就已经足够了。