约瑟夫环 C++ 栈与队列

以下是使用队列求解约瑟夫环问题的C++代码，具体实现方法是将所有人的编号放入队列中，然后按照约瑟夫环的规则依次出队，直到队列中只剩下一个人为止：

#include <iostream>
#include <queue>
using namespace std;

void josephus(int n, int k, int m) {
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        q.push(i);
    }
    int count = 0;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        count++;
        if (count == k) {
            cout << x << " ";
            count = 0;
        } else {
            q.push(x);
        }
    }
}

int main() {
    int n = 9, k = 1, m = 5;
    josephus(n, k, m);
    return 0;
}

以下是使用栈求解约瑟夫环问题的C++代码，具体实现方法是将所有人的编号放入栈中，然后按照约瑟夫环的规则依次出栈，直到栈中只剩下一个人为止：

#include <iostream>
#include <stack>
using namespace std;

void josephus(int n, int k, int m) {
    stack<int> s1, s2;
    for (int i = 1; i <= n; i++) {
        s1.push(i);
    }
    int count = 0;
    while (!s1.empty() || !s2.empty()) {
        while (!s1.empty()) {
            int x = s1.top();
            s1.pop();
            count++;
            if (count == k) {
                cout << x << " ";
                count = 0;
            } else {
                s2.push(x);
            }
        }
        while (!s2.empty()) {
            int x = s2.top();
            s2.pop();
            count++;
            if (count == m) {
                cout << x << " ";
                count = 0;
            } else {
                s1.push(x);
            }
        }
    }
}

int main() {
    int n = 9, k = 1, m = 5;
    josephus(n, k, m);
    return 0;
}