3-2栈和队列-应用

一.栈的应用
（一）栈的应用
1.括号匹配

#define MaxSize 50
typedef struct {
	ElemType data[MaxSize];
	int top;
}SqStack;

void InitStack(SqStack &S){
	S.top = -1;
}

bool Push(SqStack &S,ElemType x){
	if (S.top = MaxSize)
		return false;
	S.data[++S.top] = x;
	return true;
}

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

bool Pop(SqStack &S,ElemType &x){
	if (S.top == -1)
		return false;
	x = S.data[S.top--];
	return true;
}

bool bracketCheck(char str[], int length) {
	SqStack S;
	InitStack(S);
	for (int i = 0; i < length; i++) {
		if (str[i] == '(' || str[i] == '[' || str[i] == '{') {
			Push(S, str[i]);
		}
		else {
			if (StackEmpty(S))
				return false;
			char topElem;
			Pop(S, topElem);
			if (str[i] == ')' && topElem != '(')
				return false;
			if (str[i] == ']' && topElem != '[')
				return false;
			if (str[i] = '}' && topElem != '{')
				return false;
		}
	}
	return StackEmpty(S);
}

2.表达式求值

（1）中缀转后缀
①按优先级（有括号的先算括号），结合左优先原则，给运算符标注次序

②后缀，运算符写后面
对于1，写为ab+
对于2，写为cd*
对于3，原来在左边的数还在左边，写为ab+cd*-

练习1

答案：15 7 1 1 + - ÷ 3 × 2 1 1 + + -

练习2

答案：AB+ CD*E/ -F+

（2）后缀转中缀
按从左到右，划线法，原来在左边的还在左边

中缀：(a+b) - (c*d)
即a+b-c*d

练习1

答案：A+B-C*D/E+F

练习2

答案：(15÷(7-(1+1)))×3 - (2+(1+1))

（3）中缀转前缀
按优先级（有括号的先算括号），结合右优先原则，给运算符标注次序，然后依次处理。前缀，运算符写前面

对于1，cd
对于2，-bcd
对于3，原来在前面的还在前面，+a-b*cd

练习1

答案：+A-*B-CD/EF

练习2

答案：- × ÷ 15 - 7 + 1 1 3 + 2 + 1 1

（4）前缀转中缀
从右往左，划线法，依次处理

答案：(a+b) - (cd)
即a+b-cd

练习1

答案：A+B*(C-D)-E/F

练习2

答案：(15÷(7-(1+1)))×3 - (2+(1+1))

总结

（5）前缀表达式的计算（操作数栈）
后缀是从左往右，前缀都是从右往左
例：

从右往左
1入栈，1入栈，遇到+号，栈顶两个1弹出，计算1+1=2*，压入栈
2入栈，两个元素弹出，2+2*=4，压入栈
1入栈，1入栈，遇到+，弹出计算=2入栈
7入栈，弹出7-2=5入栈
15入栈，弹出15÷5=3入栈
3入栈，弹出3×3=9入栈
遇到-号，9-4=5，完成

后缀同理，从左往右

（6）用栈实现中缀转后缀（运算符栈）
从左往右，仅运算符入栈，操作数直接加入后缀表达式，依次弹出栈中优先级≥当前运算符的所有运算符，并加入后缀表达式。遇到(直接入栈，遇到)依次弹出栈内运算符加入后缀表达式，碰到(或栈空停止。（不加入后缀表达式。总结：大（≥）的往里放，大（≥）的往外出。
例
中缀：A+B-C*D/E+F
A，后缀表达式：A
+入栈，栈内：+
B，表达式：AB
-（≤+的优先级，+弹出），表达式：AB+
-入栈，栈内：-
C，表达式AB+C
*（＞-的优先级，入栈），栈内：-*（从底到顶）
D，表达式AB+CD
/（≤*的优先级，*弹出），栈内：-，表达式AB+CD*
/入栈，栈内：-/（从底到顶）
E，表达式AB+CD*E
+（≤/的优先级，/弹出），栈内：-，表达式：AB+CD*E/
+（≤-的优先级，-弹出），栈内：空，表达式AB+CD*E/-
+入栈
F，表达式：AB+CD*E/-F
+弹出，表达式：AB+CD*E/-F+

（7）用栈实现中缀表达式的计算
=中缀转后缀（运算符栈）+后缀求值（操作数栈）
后缀：从左到右
例：
A+B-C*D/E+F
运算符栈：+
操作数栈：AB
遇到-，+出栈，-入栈
+出栈后需要两个操作数运算，AB出栈，结果记为t1，压入操作数栈
运算符栈：- *
操作数栈：t1 C D
遇到/，*出栈，C*D记为t2，压入操作数栈，/入栈
运算符栈：- /
操作数栈：t1 t2 E
遇到+，/出栈，t2/E记为t3，压入操作数栈。-出栈，t1-t3记为t4，压入操作数栈。+入栈
运算符栈：+
操作数栈：t4 F
+出栈，t4+F为运算结果

总结
用栈实现前缀表达式的计算（操作数栈）
用栈实现中缀转后缀（运算符栈）
用栈实现中缀表达式的计算=中缀转后缀（运算符栈）+后缀求值（操作数栈）[中缀不能直接计算]

3.递归

（二）队列的应用
1.树的层次遍历
2.图的广度优先遍历
3.计算机系统中的应用
（1）解决主机与外部设备直接速度不匹配的问题
（2）解决由多用户引起的资源竞争问题