3.3栈&队列

3.3栈&队列
- 1. 栈
- 2. 队列
- 3. 题目：字符匹配问题
- 4. 题目：周末舞会

1. 栈

概念：栈(stack)又名堆栈，它是一种限定仅在表尾进行插入和删除操作的线性表。
栈顶&栈底：线性表可以操作的一端称为栈顶，另一端称为栈底。
入栈：向一个栈插入新元素又称作进栈或入栈，它是把新元素放到栈顶元素的上面，成为新的栈顶元素。
出栈：从一个栈删除元素称作出栈，它是把栈顶元素删除，使其下面的元素成为新的栈顶元素。
特性：后进先出(LIFO-last in first out)，最后插入的元素最先出来或者说先进后出。

#include
#include  //头文件
using namespace std;
stack sta;   //栈的声明
int main(){
    for(int i=0; i<=3; i++) sta.push(i);//入栈
    while(!sta.empty()){          //栈空返回 1 
        cout<


数组模拟栈：STL中的栈容易炸开，所以手动模拟

手动模拟栈的时候需要注意入栈时是否发生溢出，本文中并未考虑溢出的情况。
#include
#include
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<

栈经常用来解决递归问题和表达式计算问题，尤其是前后缀问题
中缀表达式：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
#include //头文件
using namespace std;
queue que; //队列的声明
int main(){
for(int i=0; i<=3; i++) que.push(i);//入队
cout<<"队头："<

顺序数组模拟队列
#include
#include
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<<"队头："<

3. 题目：字符匹配问题
现在有一行括号序列，请你检查这行括号是否配对。

输入：第一行输入一个数N(0
后面的N行输入多组输入数据，每组输入数据都是一个字符串S ( S的长度小于10000，且S不是空串)，数据保证S中只含有"[", “]”, “(”, “)” 四种字符。

输出：每组输入数据的输出占一行，如果该字符串中所含的括号是配对的，则输出Yes，如果不配对则输出No。
输入样例：
3
[][][]
[()]()[
[(])[]()

输出样例：
Yes
No
No

#include
#include
using namespace std;
int main() {
    int n; cin>>n;
    for(int i=1; i<=n; i++){
        stack sta;    string s; cin>>s;   
        for(int j=0; j

#include
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

4. 题目：周末舞会
假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。规定每个舞曲能有一对跳舞者。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一个程序，模拟上述舞伴配对问题。

输入两队的人数a,b，舞曲的数目n，输出配对情况。

输入样例：4 6 7

输出样例：(1,1)(2,2)(3,3)(4,4)(1,5)(2,6)(3,1)
#include
#include
using namespace std;
int main(){
    int a,b,n; cin>>a>>b>>n;  queue 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<<"("<

#include
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

3.3栈&队列

3.3栈&队列

1. 栈

2. 队列

3. 题目：字符匹配问题

4. 题目：周末舞会

相关

标签