应用
栈的应用
验证括号的正确性
题目很简单就是输入一串字符，判断字符中的括号是否合法。直接上代码：
#include <iostream>
#include <string.h>
using namespace std;
typedef char ElemType;
#define MAXSIZE 100
typedef struct Stack
{
ElemType data[MAXSIZE];
int top;
}Stack;
void InitStack(Stack& S) {
S.top = -1;
}
bool StackEmpty(Stack S) {
if (S.top == -1) {
return true;
}
return false;
}
bool Push(Stack& S, ElemType x) {
if (S.top == MAXSIZE - 1) {
return false;
}
S.top++;
S.data[S.top] = x;
return true;
}
bool Pop(Stack& S, ElemType& x) {
if (S.top == -1) {
return false;
}
x = S.data[S.top];
S.top--;
return true;
}
ElemType GetTop(Stack S) {
return S.data[S.top];
}
int main() {
Stack S;
InitStack(S);
string str;
cin >> str;
//flag标志状态 true为括号匹配，false为不匹配
bool flag = true;
for (int i = 0; i < str.size(); i++) {
//元素若为{，(，[则入栈
if ((str[i] == '{') || (str[i] == '[') || (str[i] == '(')) {
Push(S, str[i]);
}//元素若为}，)，]则出栈 赋值给right
if ((str[i] == '}') || (str[i] == ']') || (str[i] == ')')) {
if ((str[i] == '}' && GetTop(S) == '{')
|| (str[i] == ']' && GetTop(S) == '[')
|| (str[i] == ')' && GetTop(S) == '(')) {
char top = Pop(S, top);
continue;
}
else {
Push(S, str[i]);
}
}
}
if (S.top != -1) { //当栈不为空时
flag = false;
}
if (flag == false) {
cout << "括号不匹配！" << endl;
}
else cout << "括号匹配！" << endl;
system("pause");
return 0;
}实验结果：
表达式求值
要求一个表达式的结果，例如 9 +（3 - 1) * 3 + 1 ，我们可以直接算出来，但是计算机不会，计算机一般将这种表达式转换成后缀表达式，运算符在操作数后面，并且运算也是根据优先级排列好的，没有括号，利于计算机的计算，如上述表达式转换为后缀表示式为：
9 3 1 - 3 * 10 + ，但是我们现在要实现的是中缀表达式的求值。计算思路：
使用两个栈，stack0用于存储操作数，stack1用于存储操作符
从左往右扫描，遇到操作数入栈stack0
遇到操作符时，如果优先级低于或等于栈顶操作符优先级，则从stack0弹出两个元素进行计算，并压入stack0，继续与栈顶操作符的比较优先级
如果遇到操作符高于栈顶操作符优先级，则直接入栈stack1
遇到左括号，直接入栈stack1，遇到右括号，则直接出栈并计算，直到遇到左括号
//算符优先法
#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
const int maxn=110;
char priority[7][7]={
{'>','>','<','<','<','>','>'},
{'>','>','<','<','<','>','>'},
{'>','>','>','>','<','>','>'},
{'>','>','>','>','<','>','>'},
{'<','<','<','<','<','=','0'}, // 此行"("=")"表示左右括号相遇，括号内运算已完成
{'>','>','>','>','0','>','>'},
{'<','<','<','<','<','0','='} // "=" 表示整个表达式求值完毕
}; // "0"表示不可能出现这种情况 ( 语法错误 )
//Precede 用于判断运算符栈栈顶运算符 a1 与读入运算符 a2 之间的优先关系函数
char Procede(char a,char b){ // 建立 pre[][] 到 运算符间的映射关系
int i,j;
switch(a){
case'+':i=0;break;
case'-':i=1;break;
case'*':i=2;break;
case'/':i=3;break;
case'(':i=4;break;
case')':i=5;break;
case'#':i=6;break; // # 是表达式的结束符
}
switch(b){
case'+':j=0;break;
case'-':j=1;break;
case'*':j=2;break;
case'/':j=3;break;
case'(':j=4;break;
case')':j=5;break;
case'#':j=6;break;
}
return priority[i][j];
}
int Operate(int m,int n,char x){
if(x=='+')
return m+n;
if(x=='-')
return n-m;
if(x=='*')
return m*n;
if(x=='/')
return n/m;
}
// EvaluuateExpression-reduced
int main(){
stack <int> OPND; // Operand stack
stack <char> OPTR; // Operator stack
OPTR.push('#');//
char ss[2]="#";//尾部有\0
char s[maxn];
cin>>s;
strcat(s,ss);// 运算式尾部加 "#"--结束运算符
char c=s[0];
int k=1;
while(c!='#'||OPTR.top()!='#'){ //表达式未读完或者运算未完
int y=0;
if(c>='0'&&c<='9'){
while(c>='0'&&c<='9'){ // 读入连续的数字
y=y*10+(c-'0');
c=s[k++];
}
OPND.push(y); // 把读进的数字入数字栈
}
else{
switch(Procede(OPTR.top(),c))
{
case'<': //栈顶元素优先权低
OPTR.push(c);
c=s[k++];
break;
case'=':
OPTR.pop(); // 脱括号
c=s[k++]; // 读入下一个字符
break;
case'>': //退栈并将运算结果入栈
char x=OPTR.top();OPTR.pop();
int m=OPND.top();OPND.pop();
int n=OPND.top();OPND.pop();
OPND.push(Operate(m,n,x));
break;
}
}
}
cout<<OPND.top();
return 0;
}实验结果：
队列的应用
层次遍历
利用队列存储每一层的结点，再存储到数组中，很容易理解。下面是套路：
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> q;
if (root != nullptr) q.push(root);
vector<vector<int>> res;
while (!q.empty()) {
int sz = q.size();
vector<int> temp;
for (int i = 0; i < sz; i++) {
TreeNode* cur = q.front();
q.pop();
temp.push_back(cur->val);
if (cur->left != nullptr)
q.push(cur->left);
if (cur->right != nullptr)
q.push(cur->right);
}
res.push_back(temp);
}
return res;
}队列在计算机系统中的应用
一、解决主机与外部设备之间速度不匹配的问题。
二、解决由多用户引起的资源竞争问题。
Last updated
