高质量题解|模拟队列操作

题目大意

一共有三种操作:

1. 入队:用数字 $1$ 表示,后面的数字表示入队的数字
2. 出队:用数字 $2$ 表示,将队首出队
3. 访问队首:用数字 $3$ 表示,访问队首

考纲知识点

输入输出、分支结构、循环结构、队列、基础数据类型、变量的定义以及使用

数据范围

$n < 100$

解题思路

一共有 $n$ 次操作
判断操作方法

1. 入队($s==1$):输入元素 $a$
2. 出队($s==2$):先判断队列是否为空(队列为空则无法输出)
   2.1 队列不为空:删除队首元素
   2.2 队列为空:操作不合法,输出"impossible!"
3. 访问队首($s==3$):先判断队列是否为空(队列为空则无法访问)
   3.1 队列不为空:访问队首元素
   3.2 队列为空:操作不合法,输出"impossible!"

参考程序

#include <bits/stdc++.h>
using namespace std;
queue<int>q;
int main(){
	int n;
	cin >> n;
	for(int i = 1;i <= n;i++){
		int s;
		cin >> s;
		if(s == 1){
			int a;
			cin >> a;
			q.push(a);
		}else if(s == 2){
			if(!q.empty()){
				q.pop();
			}else{
                cout << "impossible!" << endl;
            }
		}else if(s == 3){
            if(!q.empty()){
                cout << q.front() << endl;
            }else{
                cout << "impossible!" << endl;
            }
        }
	}
	return 0;
} 

时间复杂度

$O(n)$(线性时间复杂度)
单层循环 $n$ 次,队列操作为 $O(1)$,整体为线性时间复杂度 $O(n)$

空间复杂度

$O(n)$(线性空间复杂度)
队列最多存储 $n$ 个元素,空间随输入规模线性增长

---

$\color{red}题解仅供学习参考使用$

抄袭、复制题解,以达到刷 AC 率/AC 数量或其他目的的行为,在ACGO是严格禁止的