队列：循环队列基本操作

一、简介

1.循环队列的用处

采用求余方式实现元素的循环存储，避免假溢出现象

2.基本操作

• 若rear+1，则对其与N（队列最大容量数）求余，即rear=(rear+1)%N
• 若front+1，则对其与N（队列最大容量数）求余，即front=(front+1)%N
• 若rear-1，则对其与N（队列最大容量数）求余，防止出现负数，即front=(front-1+N)%N

3.注意

1. rear尾指针和栈的top指针一样，总是在队列尾元素的下一个位置
2. 循环队列一定要注意指针的求余，防止假溢出现象
3. 队列空条件：头尾指针相等 q.rear==q.front
4. 队列满条件：尾指针和头指针之间差一个空位 ** (q,rear+1)%N==q.front**

二、代码实现

1. 队列创建

typedef struct{
    int data[N];
    int f;
    int r;
}Queue;

2. 队列初始化

条件：队头和队尾相等且为0

void initialQ(Queue &q){
    q.f=q.r=0;
}

3.判空

条件：若队头指针和队尾指针重合，则为空

int ifEmpty(Queue &q){
    if(q.r==q.f) return 1;
    else return 0;
}

4. 压入队列

先判断队列是否满，若不满则压入队列

队列满：还差一个空位时则为满

(rear+1)%N==front时即为满

void push(Queue &q,int x){
    if((q.r+1)%N==q.f) return;
    q.data[q.r] = x;
    q.r=(q.r+1)%N;
}

5.出队列

判断队列是否为空，非空则出队列

出队列：头指针+1（要对N求余）

void pop(Queue &q){
    if(ifEmpty(q)) return;
    else {
        q.f=(q.f+1)%N;
    }
}

6.取队头元素

先判断队列非空

int getF(Queue &q){
    if(!ifEmpty(q)) return q.data[q.f];
}

7.取队尾元素

先判断队列非空

int getR(Queue &q){
    if(!ifEmpty(q)) return q.data[(q.r-1+N)%N];
}

三、例题：约瑟夫问题（猴子选大王）

1. 题目

Description

n个人想玩残酷的死亡游戏，游戏规则如下：

n个人进行编号，分别从1到n，排成一个圈，顺时针从1开始数到m，数到m的人被杀，剩下的人继续游戏，活到最后的一个人是胜利者。

请输出最后一个人的编号。

Input

输入n和m值。

Output

输出胜利者的编号。

Sample

Input

5 3

Output

4

Hint

第一轮：3被杀第二轮：1被杀第三轮：5被杀第四轮：2被杀

2.代码（AC）

#include <iostream>
#include <cstdio>
#include<cstdlib>
#include<string>
using namespace std;
const int N=1e5;
typedef struct{
    int data[N];
    int f;int r;
}Queue;
void init(Queue &q){
    q.f=q.r=0;
}
int ifEmpty(Queue &q){
    if(q.r==q.f) return 1;
    else return 0;
}
void push(Queue &q,int x){
    if((q.r+1)%N!=q.f){
        q.data[q.r]=x;
        q.r=(q.r+1)%N;
    }
    else return;
}
void pop(Queue &q){
    if(!ifEmpty(q))
        q.f=(q.f+1)%N;
    else return;
}
int getF(Queue &q){
    return q.data[q.f];
}

int main(){

    int m,n,i,c=0;
    cin>>n>>m;
    Queue q;
    init(q);
    for(i=1;i<=n;i++)
        push(q,i);
    while(n!=1){
        if(c==m){
            for(i=1;i<m;i++){
                push(q,getF(q));pop(q);
            }
            pop(q);n--;c=0;
        }
        else c++;
    }
    cout<<q.data[q.f]<<endl;
    return 0;
}