Josephus

/* From https://algs4.cs.princeton.edu/13stacks/Josephus.java.html
* Josephus problem. In the Josephus problem from antiquity, N people are in dire straits and agree to the
* following strategy to reduce the population. They arrange themselves in a circle (at positions numbered
* from 0 to N-1) and proceed around the circle, eliminating every Mth person until only one person is left.
* Legend has it that Josephus figured out where to sit to avoid being eliminated. Write a Queue client
* Josephus.java that takes M and N from the command line and prints out the order in which people are
* eliminated (and thus would show Josephus where to sit in the circle).*/

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

public class Josephus {
    public static void main(String[] args) {
        int m = StdIn.readInt();
        int n = StdIn.readInt();

        // initialize the queue
        LinkedQueueOfIntegers queue = new LinkedQueueOfIntegers();
        for (int i = 0; i < n; i++)
            queue.enqueue(i);

        while (!queue.isEmpty()) {
            for (int i = 0; i < m - 1; i++)
             // we send back at the beginning of the queue the first mth positions using dequeue with
             // and print the position that goes away.
                queue.enqueue(queue.dequeue());
                StdOut.print(queue.dequeue()+ " ");
        }
        StdOut.println();
    }
}

---------------with this implementation of a Queue of Integers using Linked-list for example -------------

public class LinkedQueueOfIntegers {

    private Node first, last; // we maintain 2 pointers in a linked list for queues

    private class Node {  // a nested inner class to get the recursion feature
        Integer item;
        Node next;
    }

    public boolean isEmpty() {return first == null;}


    public void enqueue(Integer item ){
        Node oldLast = last;    // we save a copy of the current last item
        last = new Node(); // initialize it with a new node
        last.item = item; // and populate it
        last.next = null;
        if(isEmpty()) first = last; // case of empty list
        else oldLast.next = last; // and we reconnect the oldLast to point to the new last of the queue
    }

    public Integer dequeue() {
        Integer item = first.item; // we save the value of the current first item
        first = first.next; // and reset the value of first to the next item
        if(isEmpty()) last = null;
        return item;
    }
}