队列queue的特征:先进先出

可以简单将队列看成一个通道,从通道的一头进从另外一头出。

头文件: #include<queue>

C++队列queue类成员函数如下:

back()返回最后一个元素

empty()如果队列空则返回真

front()返回第一个元素

pop()删除第一个元素

push()在末尾加入一个元素

size()返回队列中元素的个数

下面看个简单的例题

约瑟夫环

Description

题目:n个数字(1,2,3…,n)形成一个圆圈,从数字1开始,每次从这个圆圈中删除第m个数字(第一个为当前数字本身,第二个为当前数字的下一个数字)。 当一个数字删除后,从被删除数字的下一个继续删除第m个数字。 求出在这个圆圈中剩下的最后一个数字。

Input

n=9 m=5

Output

The last one is 8

Sample Input

9 5

Sample Output

8

思路:把所有数字存入队列,把队列中的第一个数据存入队列并删除第一个数据,第m个数据不存入队列就OK了 AC代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <cstdio>
#include <stack>
#include <queue>
#include <algorithm>

using namespace std;

int main()
{
queue<int>p; //开辟队列
int n,m,x=0,i;
while(!p.empty()) //清空队列
p.pop();
scanf("%d%d",&n,&m);
for(i=1; i<=n; i++)
{
p.push(i); //把数据存入队列
}
i=0;
while(1)
{
x++;
if(x!=5) //如果不是你要删掉的那个数据 就存到队列最后
p.push(p.front());
else
x=0; //删除一个数据后要重新计数
p.pop(); //删除队列中第一个数据
if(p.size()==1)
{ //如果还剩一个数据 输出该数据
printf("%d\n",p.front());
break;
}
}
return 0;
}

评论




博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

载入天数...载入时分秒... 本站使用 Volantis 作为主题 鲁ICP备-20012065号