3.3栈&队列
2021/12/11 23:20:01
本文主要是介绍3.3栈&队列,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
目录- 3.3栈&队列
- 1. 栈
- 2. 队列
- 3. 题目:字符匹配问题
- 4. 题目:周末舞会
3.3栈&队列
1. 栈
概念:栈(stack)又名堆栈,它是一种限定仅在表尾进行插入和删除操作的线性表。
栈顶&栈底:线性表可以操作的一端称为栈顶,另一端称为栈底。
入栈:向一个栈插入新元素又称作进栈或入栈,它是把新元素放到栈顶元素的上面,成为新的栈顶元素。
出栈:从一个栈删除元素称作出栈,它是把栈顶元素删除,使其下面的元素成为新的栈顶元素。
特性:后进先出(LIFO-last in first out),最后插入的元素最先出来或者说先进后出。
#include<iostream> #include<stack> //头文件 using namespace std; stack<int> sta; //栈的声明 int main(){ for(int i=0; i<=3; i++) sta.push(i);//入栈 while(!sta.empty()){ //栈空返回 1 cout<<sta.top()<<" "; //返回栈顶元素 sta.pop(); //出栈 } cout<<"栈内元素个数:"<<sta.size(); return 0; }
数组模拟栈:STL中的栈容易炸开,所以手动模拟
手动模拟栈的时候需要注意入栈时是否发生溢出,本文中并未考虑溢出的情况。
#include<iostream> #include<stack> using namespace std; const int N=1e4; //栈的大小 int sta[N], top=0; //模拟栈,栈顶 int main(){ for(int i=0; i<=3; i++) sta[++top]=i;//入栈 sta[1]~sta[top] while(top){ //栈不空则执行 cout<<sta[top]<<" "; //返回栈顶元素 --top; //出栈 } cout<<"栈内元素个数:"<<top; return 0; }
栈经常用来解决递归问题和表达式计算问题,尤其是前后缀问题
中缀表达式:a + b 3 * (5-2) + 7 前缀表达式:+ a b + * 3 - 5 2 7 后缀表达式:a b + 3 5 2 - * 7 +
2. 队列
概念:队列是一种限定在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作的线性表。
队头&队尾:进行插入操作的端称为队尾,进行删除操作的端称为队头。
入队:向一个队列插入新元素又称作进队或入队,它是把新元素放到队尾元素后面,成为新的队尾元素。
出队:从一个队列弹出元素称作出队,它是把队头元素弹出,使其后面一个元素成为新的队头元素。
特性:先进先出(FIFO-first in first out),最先插入的元素最先出来。
#include<iostream> #include<queue> //头文件 using namespace std; queue<int> que; //队列的声明 int main(){ for(int i=0; i<=3; i++) que.push(i);//入队 cout<<"队头:"<<que.front()<<"\t队尾:"<<que.back()<<endl; while(!que.empty()){ //队空返回 1 cout<<que.front()<<" "; //队头 que.pop(); //出队 } cout<<"队列中元素个数:"<<que.size(); return 0; }
顺序数组模拟队列
#include<iostream> #include<queue> using namespace std; const int N=1e4; //队列大小 int que[N], front=1, rear=0;//模拟队列,队头,队尾 int main(){ for(int i=1; i<=3; i++) que[++rear]=i;//入队que[1]~que[rear] cout<<"队头:"<<que[front]<<"\t队尾:"<<que[rear]<<endl; while(front<=rear){ //队列不为空,继续执行 cout<<que[front]<<" ";//队头 ++front; //出队 } --front; //队列溢出处理 cout<<"队列中元素个数:"<<rear-front; }
3. 题目:字符匹配问题
现在有一行括号序列,请你检查这行括号是否配对。
输入:第一行输入一个数N(0<N<=100),表示有N组测试数据。
后面的N行输入多组输入数据,每组输入数据都是一个字符串S ( S的长度小于10000,且S不是空串),数据保证S中只含有"[", “]”, “(”, “)” 四种字符。
输出:每组输入数据的输出占一行,如果该字符串中所含的括号是配对的,则输出Yes,如果不配对则输出No。
输入样例: 3 [][][] [()]()[ [(])[]() 输出样例: Yes No No
#include<iostream> #include<stack> using namespace std; int main() { int n; cin>>n; for(int i=1; i<=n; i++){ stack<char> sta; string s; cin>>s; for(int j=0; j<s.length(); j++){ if(s[j]=='[') sta.push('['); else if(s[j]=='(') sta.push('('); else if(s[j]==']' && sta.top()=='[') sta.pop(); else if(s[j]==')' && sta.top()=='(') sta.pop(); else{ break; } } if(sta.empty()) cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; }
#include<bits/stdc++.h> using namespace std; const int N=1e4+1; char a[N]; int main() { int n; cin>>n; for(int i=1; i<=n; i++) { int cnt=0; string s; cin>>s; for(int j=0; j<s.length(); j++) { if(s[j]=='[') a[++cnt]='['; else if(s[j]=='(') a[++cnt]='('; else if(s[j]==']' && a[cnt]=='[') --cnt; else if(s[j]==')' && a[cnt]=='(') --cnt; else { cnt=-1; break; } } if(cnt==0) cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; }
4. 题目:周末舞会
假设在周末舞会上,男士们和女士们进入舞厅时,各自排成一队。跳舞开始时,依次从男队和女队的队头上各出一人配成舞伴。规定每个舞曲能有一对跳舞者。若两队初始人数不相同,则较长的那一队中未配对者等待下一轮舞曲。现要求写一个程序,模拟上述舞伴配对问题。
输入两队的人数a,b,舞曲的数目n,输出配对情况。
输入样例:4 6 7
输出样例:(1,1)(2,2)(3,3)(4,4)(1,5)(2,6)(3,1)
#include<iostream> #include<queue> using namespace std; int main(){ int a,b,n; cin>>a>>b>>n; queue<int> que1,que2; for(int i=1; i<=a; i++) que1.push(i); for(int i=1; i<=b; i++) que2.push(i); for(int i=1; i<=n-1; i++){ int t1=que1.front(), t2=que2.front(); que1.pop(); que1.push(t1); que2.pop(); que2.push(t2); cout<<"("<<t1<<","<<t2<<")"; } cout<<"("<<que1.front()<<","<<que2.front()<<")"; return 0; }
#include<iostream> using namespace std; const int N=1e4; int que1[N], que2[N]; int main() { int a,b,n; cin>>a>>b>>n; for(int i=0; i<a; i++) que1[i]=i+1; for(int i=0; i<b; i++) que2[i]=i+1; for(int i=0; i<n; i++){ int t1=que1[i%a], t2=que2[i%b]; cout<<"("<<t1<<","<<t2<<")"; } return 0; }
这篇关于3.3栈&队列的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-02Java微服务系统项目实战入门教程
- 2024-11-02Java微服务项目实战:新手入门指南
- 2024-11-02Java项目实战:新手入门教程
- 2024-11-02Java小程序项目实战:从入门到简单应用
- 2024-11-02Java支付系统项目实战入门教程
- 2024-11-02SpringCloud Alibaba项目实战:新手入门教程
- 2024-11-02Swagger项目实战:新手入门教程
- 2024-11-02UNI-APP项目实战:新手入门与初级教程
- 2024-11-02编译部署资料入门教程:一步步学会编译和部署
- 2024-11-02地图服务资料入门指南