2013年NOIP提高组复赛第1题—机器翻译

1

问题描述

2

问题分析

这道题是2013年noip提高组复赛第1题，主要考察了队列的先进先出的思想，以及循环队列入队和出队的方式，我们可以采用数组模拟的方式，这个时候队尾指针的变化通过(rear+1)%maxn来实现就可以了。我们也可以采用STL模板库中queue相关的函数来实现。

---

知识扩展：

（1）队列：

 队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

 

点：先进先出

（2）循环队列：

像上述图示情况，顺序队列因进行多次入队和出队操作后出现有存储空间但不能进行入队操作的溢出我们称为假溢出。

为解决上述情况，我们可以把顺序队列所使用的存储空间构成一个逻辑上首尾相连的循环队列来处理。

 

 

 但是，在循环队列这种情况下，队空的条件是front = rear, 队满时的条件也是front = rear;

这种情况，我们通常采用以下方法解决：

 方法：人为损失一个单元，这样队空条件是：front = rear,队满的条件是：(rear+1)%maxn=front。

 

C++中的STL模板queue的基本用法  :

首先要包含头文件：#include<queue>

（1）定义

queue<int>q；

（2）基本操作

q.push(x)；=> x入队。

q.pop()；=> 出队（弹出队列第一个元素，不返回）。

q.front()；=> 访问队首元素。

q.back()；=> 访问队尾元素。

q.empty()；=> 判断队列是否为空（空时返回true，否则返回false）。

q.size()；=> 返回队列中元素的个数。

3

参考代码如下

第一种数组模拟队列：

第二种STL队列：

转自公众号：
信息学少儿编程