王道机试C++第 5 章 数据结构二：队列queue和21年蓝桥杯省赛选择题Day32

#include <bits/stdc++.h>
using namespace std;
 
int main() {  
    queue<int> myQueue; // 定义并初始化一个整型队列  
  
    // 输出队列初始大小  
    printf("the size of myQueue: %zu\n", myQueue.size());  
  
    for (int i = 0; i < 10; ++i) {  
        myQueue.push(i); // 将元素推入队列  
    }  
  
    // 输出队列的前端和后端元素  
    printf("the front of myQueue: %d\n", myQueue.front());  
    printf("the back of myQueue: %d\n", myQueue.back());  
  
    // 输出队列当前大小  
    printf("the size of myQueue: %zu\n", myQueue.size());  
  
    int sum = 0;  
    while (!myQueue.empty()) {  
        sum += myQueue.front(); // 累加队列前端元素  
        myQueue.pop(); // 弹出队列前端元素  
    }  
  
    // 输出累加和  
    printf("sum: %d\n", sum);  
  
    //再次检查是否为空  
     if (myQueue.empty()) {  
         printf("myQueue is empty\n");  
    }  
  
    // 输出队列最终大小（应该是0）  
    printf("the size of myQueue: %zu\n", myQueue.size());  
  
    return 0;  
}

2. 队列的应用

例:约瑟夫问题 No. 2

题目描述：

#include <bits/stdc++.h>
using namespace std;
 
int main() {  
    int n,p,m;
    while(true){
    	scanf("%d%d%d",&n,&p,&m);
    	if(n==0&&p==0&&m==0){
    		break;
		}
		
//1、排队 
		//队列中的元素是孩子的编号 
		queue<int>children;
//把第一轮要喊编号的孩子排好队 
//i遍历孩子的编号，j记录已经遍历的孩子数量 
		for(int i=p,j=0;j<n;++j){
			children.push(i);
			++i;//p ->p+1 ->p+2 ->..n ->1 ->...->p-1
			if(i>n){
				i=1;
			}
		}
	}
	
//2、喊号过程 
	int num=1;//将要喊的号
	while(true){
	    int cur=children.front();//cur是队首孩子的编号
		children.pop();
		if(num==m){//检查刚才喊得号是不是1 
			num=1;//下一个就是1
			//喊号的同学不需要归队
			if(children.empty()){
				printf("%d\n",cur);
				break;
			}else{
				//还有同学在喊号
				printf("%d",cur);
			}
		}	
	} else{
		//喊得号码不是m,归队
		num=num+1; 
		children.push(cur); 
	}
    return 0;  
}

代码表示：

#include <bits/stdc++.h>
using namespace std;
 
// 定义动物结构体  
struct animal {  
    int num; // 动物编号  
    int seq;  // 次序标志  
    animal(int n, int o) : number(n), order(o) {} // 构造函数  
};  
  
int main() {  
    queue<animal> catque; // 猫的队列  
    queue<animal> dogque; // 狗的队列  
    int n;  
    int seq = 0;  
    scanf("%d",&n); // 输入动物数量  
    for (int i = 0; i < n; ++i) {  
        int method, pare;  
        scanf("%d%d",&method,&pare)// 输入操作方法和动物类型  
        if (method == 1) {  
            // 入队操作  
            if (pare > 0) 
			{ 
			//操作狗
			animal dog;
			dog.num=para;
			dog.seq=seq; 
			++seq;
            dogque.push(dog);
            } else 
			{ 
			animal cat;
			cat.num=para;
			cat.seq=seq; 
			++seq;
            catque.push(dog); 
            }  
        } 
		else 
		{  
            // 出队操作  
            if (pare == 0 && !dogque.empty() && !catque.empty()) {  
                // 猫和狗都不为空，比较次序出队  
                if (dogque.front().pare < catque.front().pare) {  
                    cout << dogque.front().number << " ";  
                    dogque.pop();  
                } else {  
                    cout << catque.front().number << " ";  
                    catque.pop();  
                }  
            } else if (pare == 0 && dogque.empty() && !catque.empty()) {  
                // 狗为空，只有猫，出队猫  
                cout << catque.front().num << " ";  
                cats.pop();  
            } else if (pare== 0 && !dogque.empty() && catque.empty()) {  
                // 猫为空，只有狗，出队狗  
                cout << dogque.front().num << " ";  
                dogs.pop();  
            } else if (pare == 1 && !dogque.empty()) {  
                // 只出队狗  
                cout << dogque.front().num<< " ";  
                dogs.pop();  
            } else if (pare== -1 && !catque.empty()) {  
                // 只出队猫  
                cout << catque.front().num<< " ";  
                catque.pop();  
            }  
        }  
    }  
    cout << endl; // 输出换行符  
    return 0;  
}