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栈&队列的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程