【算法通关指南：数据结构和算法篇】队列相关算法题：1. 【模板】队列，2. 机器翻译

小龙报

发布于 2025-12-15 14:57:21

1980

文章被收录于专栏：C\C++C\C++

🔥小龙报：个人主页 🎬作者简介：C++研发，嵌入式，机器人方向学习者 ❄️个人专栏：《算法通关指南》 ✨ 永远相信美好的事情即将发生

前言

本专栏聚焦算法题实战，系统讲解算法模块：以《c++编程》，《数据结构和算法》《基础算法》《算法实战》等几个板块以题带点，讲解思路与代码实现，帮助大家快速提升代码能力***ps:本章节题目分两部分，比较基础笔者只附上代码供大家参考，其他的笔者会附上自己的思考和讲解，希望和大家一起努力见证自己的算法成长***

一、【模板】队列

1.1题目

链接：【模板】队列

1.2算法原理

模拟⼀个队列提供两种解法

1.3代码

1.3.1 STL版本

#include <iostream>
#include <queue>
using namespace std;
queue<int> q;
int n;

int main()
{
	cin >> n;

	while (n--)
	{
		int op;
		cin >> op;

		if (op == 1)
		{
			int x;
			cin >> x;
			q.push(x);
		}
		else if (op == 2)
		{
			if (q.empty())
				cout << "ERR_CANNOT_POP" << endl;
			else
				q.pop();
		}
		else if (op == 3)
		{
			if (q.empty())
				cout << "ERR_CANNOT_QUERY" << endl;
			else
				cout << q.front() << endl;
		}
		else if (op == 4)
			cout << q.size() << endl;
	}
	return 0;
}

1.3.2 模拟版本

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int q[N];
int  h, t;
int n;

int main()
{
	cin >> n;

	while (n--)
	{
		int op;
		cin >> op;

		if (op == 1)
		{
			int x;
			cin >> x;
			q[++t] = x;
		}
		else if (op == 2)
		{
			if (h == t)
				cout << "ERR_CANNOT_POP" << endl;
			else
				h++;
		}
		else if (op == 3)
		{
			if (h == t)
				cout << "ERR_CANNOT_QUERY" << endl;
			else
				cout << q[h + 1] << endl;
		}
		else if (op == 4)
			cout << t - h << endl;
	}
	return 0;
}

二、机器翻译

2.1题目

链接：机器翻译

2.2算法原理

（1）创建一个队列，模拟整个流程（2）同时创建⼀个bool或int类型的数组，快速判断元素是否在队列中维持队列元素个数在m个即可。

2.3代码

#include <iostream>
#include <queue>
using namespace std;
const int N = 1e3 + 10;
queue<int> q;
int m, n;
int st[N];

int main()
{
	cin >> m >> n;

	int ret = 0; //查找次数
	for (int i = 1; i <= n; i++)
	{
		int x;
		cin >> x;

		if (st[x] != 0) //内存中有此单词
			continue;
		else
		{
			ret++;
			q.push(x);
			//内存满了
			if (q.size() > m)
			{
				st[q.front()] = 0; //原内存中最早的单词弹出
				q.pop();
			}
			st[q.back()] = 1; //把刚加进来的元素置为1即词典有该单词
		
		}

	}

	cout << ret << endl;
	return 0;
}