Josephus Problem Using Queue

Queue simulation solves Josephus neatly: keep people in a queue, move first k-1 people to rear, eliminate the kth, and repeat until one survivor remains.

On this page

Queue-based elimination idea
C implementation
Step trace and survivor

1) Algorithm

Step	Action
1	Enqueue persons `1..n`.
2	Repeat while size > 1: rotate `k-1` times (front to rear).
3	Dequeue next person (eliminated).
4	Remaining front is survivor.

2) Example in C

#include <stdio.h>

#define MAX 200
int q[MAX], f = 0, r = -1, sz = 0;
void enq(int x){ q[++r] = x; sz++; }
int deq(void){ sz--; return q[f++]; }

int josephus(int n, int k){
    f = 0; r = -1; sz = 0;
    for(int i=1;i<=n;i++) enq(i);
    while(sz > 1){
        for(int i=1;i<k;i++) enq(deq());
        printf("Eliminated: %d\n", deq());
    }
    return deq();
}

int main(void){
    int n = 7, k = 3;
    int ans = josephus(n, k);
    printf("Survivor: %d\n", ans);
    return 0;
}

Execution summary (n=7, k=3)

Round	Eliminated	Queue State (conceptual)
1	3	[4,5,6,7,1,2]
2	6	[7,1,2,4,5]
3	2	[4,5,7,1]
4	7	[1,4,5]
5	5	[1,4]
6	1	[4]

3) Complexity

Time: O(nk) for direct simulation.
Space: O(n) for queue.

Key takeaway

Josephus is a strong queue-rotation pattern problem: repeated front-to-rear moves + periodic dequeue.