• 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;
}