数据结构基础 | 栈和队列练习

叁歲伎倆 2023-07-08 10:27 57阅读 0赞

数据结构和算法这基础鸭，在上研究生之前还是要好好巩固好的。那么！从今天开始就坚持每日一小节趴！害，我这无处安放的勤奋学习的心啊~~ 刚把得！

--------------------

**例题6-2 铁轨**

> 某城市有一个火车站，有n截车厢从A方向驶入，按进站顺序编号1-n。判断能否按照特定的顺序进入B方向的铁轨驶出车站

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTQ1OTI2_size_16_color_FFFFFF_t_70][]

**解法：栈的简单运用**  
**代码：**

//判断出栈顺序是否可能
    #include<cstdio>
    #include<stack>
    using namespace std;
    const int MAXN=1000+10;
    int n, target[MAXN];
    int main(){ 
    	while(scanf("%d",&n)==1){ 
    		stack<int> s;
    		int A=1,B=1;
    		for(int i=1;i<=n;i++)
    			scanf("%d",&target[i]);
    		int ok=1;
    		while(B<=n)
    		{ 
    			if(A==target[B]){ A++;B++;}
    			else if(!s.empty() && s.top()==target[B]){ s.pop();B++;}
    			else if(A<=n)s.push(A++);
    			else { ok=0; break;}
    		}
    		printf("%s\n",ok?"yes":"no");
    	}
    	return 0;
    }

--------------------

**例题6-3 矩阵链乘**

> 输入n个矩阵的维度和一些矩阵链乘表达式，输出乘法的次数。如果无法相乘输出error。假定A是mxn矩阵，B是nxp矩阵，乘法次数位mxnxp。  
> 例如，A是50x10的，B是10*20的，C是20*5的，则（A(BC)）的乘法次数为10x20x5(BC的乘法次数)+50x10x5(A(BC))的乘法次数）=3500

**解法：** 分析表达式，用栈解决，碰到字母时进展，碰到右括号出栈计算，将结果存栈。

**代码：**

#include <cstdio>
    #include <stack>
    #include<iostream>
    #include <string>
    using namespace std;
    
    struct Matrix{ 
    	int a, b;
    	Matrix(int a=0,int b=0):a(a),b(b){ }
    }m[26];
    
    stack<Matrix> s;
    int main()
    { 
    	int n;
    	cin>>n;
    	for(int i=0;i<n;i++)
    	{ 
    		string name;
    		cin>>name;
    		int k=name[0]-'A';
    		cin>>m[k].a>>m[k].b;
    	}
    	string expr;
    	while(cin>>expr){ 
    		int len=expr.length();
    		bool error=false;
    		int ans=0;
    		for(int i=0;i<len;i++)
    		{ 
    			if(isalpha(expr[i])) s.push(m[expr[i]-'A']);
    			else if(expr[i]==')'){ 
    				Matrix m2=s.top();s.pop();
    				Matrix m1=s.top();s.pop();
    				if(m1.b !=m2.a){  error=true;break;}
    				ans+=m1.a*m1.b*m2.b;
    				s.push(Matrix(m1.a,m2.b));
    			}
    		}
    		if(error) printf("error\n");
    		else printf("%d\n",ans);
    	}
    	return 0;
    }

--------------------

**描述**

> 实现一个栈，完成以下功能：入栈、出栈、询问栈中位置Y是谁
> 
> 一开始栈为空。栈中的位置从1开始（即栈底位置为1）。

**输入**

> 第一行一个整数n，表示操作个数。  
> 接下来n行，每行第一个数字表示操作（见描述）：  
> 若为数字1，则接下来有一串字符串X，表示将X压入栈中。  
> 若为数字2，表示弹出栈顶（保证栈非空），并输出出栈的这个人。  
> 若为数字3，则接下来有一个整数Y，表示询问栈中位置Y是谁（保证位置Y合法），并输出名字

**输出**

> 将所有操作2和操作3输出，一行一个。

**代码：**

#include <iostream>
    using namespace std;
    const int N=100005;
    	//Stack:栈
    	//top：栈顶位置
    	string Stack[N];
    	int n,top=1;
    
    	//压入栈顶
    	//name:被压入的人的姓名
    	void push(string name)
    	{ 
    		Stack[top]=name;top++;
    	}
    
    	//弹出栈顶
    	//返回值：被弹出来的人的name
    	string pop(){ 
    	return Stack[(top--)-1];//--top 和top--的区别
    	}
    	//询问栈中某个位置上的人的姓名（栈底位置为1，向栈顶方向的位置依次递增）
    	//pos：询问位置
    	//返回值：pos上的name
    	string query(int pos){ 
    		return Stack[pos];
    	}
    int main()
    { 
    	cin>>n;
    	char name[20];
    	for( ;n--;)
    	{ 
    		int m; cin>>m;
    		switch(m)
    		{ 
    			case 1:
    				cin>>name;push(name);break;
    			case 2:
    				cout<<pop().c_str()<<endl;//c_str是Borland封装的String类中的一个函数，它返回当前字符串的首字符地址。
    				break;
    			case 3:
    				int pos;cin>>pos;
    				cout<<query(pos).c_str()<<endl;
    				break;
    		}
    	}
    	return 0;
    }

--------------------

**题目与上面相同 改成队列形式**

#include <iostream>
    using namespace std;
    const int N=100005;
    	//Queue:队列
    	//first：队顶位置
    	string Queue[N];
    	int n,first=1,rear=1;
    
    	//压入队列
    	//name:被压入的人的姓名
    	void inqueue(string name)
    	{ 
    		Queue[rear]=name;rear++;
    	}
    
    	//输出队列
    	//返回值：被弹出来的人的name
    	string dequeue(){ 
    	return Queue[first++]; 
    	}
    	//询问队列中某个位置上的人的姓名
    	//pos：询问位置
    	//返回值：pos上的name
    	string query(int pos){ 
    		return Queue[pos+first-1];//ahhhhhhh 我真是个天才，，，虽然底子差 但是自己想出来的感觉真爽！
    	}
    int main()
    { 
    	cin>>n;
    	char name[20];
    	for( ;n--;)
    	{ 
    		int m;
    		cin>>m;
    		switch(m)
    		{ 
    		case 1:
    			cin>>name;inqueue(name);
    			break;
    		case 2:
    			cout<<dequeue().c_str()<<endl;//c_str是Borland封装的String类中的一个函数，它返回当前字符串的首字符地址。
    			break;
    		case 3:
    			int pos;
    			cin>>pos;
    			cout<<query(pos).c_str()<<endl;
    			break;
    		}
    	}
    	return 0;
    }

--------------------

**参考博客：**

*  [C++中stack用法][C_stack]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTQ1OTI2_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200226113140846.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTQ1OTI2,size_16,color_FFFFFF,t_70
[C_stack]: https://blog.csdn.net/qq_36134437/article/details/103372345?ops_request_misc=%7B%22request_id%22:%22158303820119724848316235%22,%22scm%22:%2220140713.130056874..%22%7D&request_id=158303820119724848316235&biz_id=0&utm_source=distribute.pc_search_result.none-task