[C++知识库]栈和队列的应用【ACboy needs your help again、C++】

题目描述

ACboy was kidnapped!!
he miss his mother very much and is very scare now.You can’t image how dark the room he was put into is, so poor
As a smart ACMer, you want to get ACboy out of the monster’s labyrinth.But when you arrive at the gate of the maze, the monste say :" I have heard that you are very clever, but if can’t solve my problems, you will die with ACboy."
The problems of the monster is shown on the wall:
Each problem’s first line is a integer N(the number of commands), and a word “FIFO” or “FILO”.(you are very happy because you know “FIFO” stands for “First In First Out”, and “FILO” means “First In Last Out”).
and the following N lines, each line is “IN M” or “OUT”, (M represent a integer).
and the answer of a problem is a passowrd of a door, so if you want to rescue ACboy, answer the problem carefully!

input

The input contains multiple test cases.
The first line has one integer,represent the number oftest cases.
And the input of each subproblem are described above.

output

For each command “OUT”, you should output a integer depend on the word is “FIFO” or “FILO”, or a word “None” if you don’t have any integer.

sample

4
4 FIFO
IN 1
IN 2
OUT
OUT
4 FILO
IN 1
IN 2
OUT
OUT
5 FIFO
IN 1
IN 2
OUT
OUT
OUT
5 FILO
IN 1
IN 2
OUT
IN 3

1
2
2
1
1
2
None
2
3

题目的大概意思就是给一组数组，有FIFO和FILO的数据，当命令为in的时候，输入值，当为out时输出值

题目中很明确的告诉了我们会用到先进先出和先进后出，这两者分别对应数据结构队列和栈，因此该题为栈和队列的基本应用

AC代码

#include <iostream>
#include<algorithm>
#include<queue>
#include<stack>

using namespace std;

void deal_ans(int queue_or_stack , int num){
    queue<string> queue_data;
    stack<string> stack_data;

    string cmd , data;
    for(int i = 1 ; i <= num ; i ++){
        cin >> cmd;

        if(queue_or_stack == 1){
            // 队列（输入/输出）
            if(cmd == "IN"){
                cin >> data;
                queue_data.push(data);
            }
            else if(cmd == "OUT"){
                if(queue_data.size() == 0){
                    cout << "None" << endl;
                    continue;
                }
                cout << queue_data.front() << endl;
                queue_data.pop();
            }
        }
        else if (queue_or_stack == 2){
            // 队列（输入/输出）
            if(cmd == "IN"){
                cin >> data;

                stack_data.push(data);
            }
            else if(cmd == "OUT"){
                if(stack_data.empty()){
                    cout << "None" << endl;
                    continue;
                }
                cout << stack_data.top() << endl;
                stack_data.pop();
            }
        }

    }
}

int main()
{
    int t , x ;
    string cmd_type;

    //ios::sync_with_stdio(0);

    cin >> t;

    while(t --){
        cin >> x >> cmd_type;

        if(cmd_type[2] == 'F'){
            // 先进先出（队列）
            deal_ans(1,x);
        }
        else {
            // 先进后出（栈）
            deal_ans(2,x);
        }

    }

    return 0;
}

代码解释

首先输入有几组测试样例（T），对T进行循环

判断需要调用的是队列还是栈，因为FILO和FIFO差别只在第三位，所以我这里只判断了第三位的值，将判断的命令调用函数deal_ans去得到真正的答案

编写为函数，使整体逻辑更加明了，清晰。

在函数内定义队列和栈，<string>为队列和栈存储的数据类型
（这里都给的是string）

根据传入的数据结构类型进行不同的判断

• 1——对于队列
• 2——对应栈

只有当输入的命令为IN的时候才需要输入数据，所以将输入数据的操作放在了判断in操作的内部

如果队列或者栈的长度为0了，但是依旧要out，则输出None

这里需要注意的是，在OUT操作时，我们是需要输出值

• 栈——输出top值
• 队列 ——输出front值
  并不是直接pop()，因为pop获取不到值，仅仅只是删除了末尾或者队头的元素