Question

IN JAVA!!!

This is called the Josephus problem. Josephus.mp4Play media comment.

Use words.txt as input.

Use the Node class and the Circular Queue class you created in L5b.

In your main program input the words from words.txt into a Queue (a circular queue) - do this by using enqueue .

Then input an integer (n). Then starting at the head of the queue delete every nth node until only one node remains. Output the String in that last node.

Make NO changes to the Node class. In the Queue class you will need a method to delete every nth node.

You will need to print your queue, so make a print method in your Queue class. This should print the ENTIRE queue, not just the head. It is true that at the end only the head should remain, but by printing the entire queue and finding there is only one node printed you are verifying to me (and to yourself) that only the head remains.

When I ran my program these are the answers I got:

n=5 : hostelry

n=29: cliquish

n=7: alienist

SUGGESTION: Try this on a smaller input file first. This one contains just the numbers 1-20    Ex.txt

You can try this by hand, and then verify that your program is correct. For n=5, the answer is "20"

NODE CLASS

class Node<T> {
//Node makes item, next, and prev all private
//and therefore has to provide accessors
//and mutators (gets and sets)
private T item;
private Node next;
private Node prev;

Node(T newItem) {
item = newItem;
next = null;
prev = null;
}

Node(T newItem, Node nextNode, Node prevNode) {
item = newItem;
next = nextNode;
prev = prevNode;
}

/**
* @return the item
*/
public T getItem() {
return item;
}

/**
* @param item the item to set
*/
public void setItem(T item) {
this.item = item;
}

/**
* @return the next
*/
public Node getNext() {
return next;
}

/**
* @param next the next to set
*/
public void setNext(Node next) {
this.next = next;
}

/**
* @return the prev
*/
public Node getPrev() {
return prev;
}

/**
* @param prev the prev to set
*/
public void setPrev(Node prev) {
this.prev = prev;
}

}

QUEUE CLASS

class Queue<T> {

private Node head, tail = null;
int size = 0;
public Queue() {
head = tail = null;
size = 0;
}
//enqueue
public void enqueue(T item) {
Node temp = new Node(item);
if (head == null) {
head = temp;
tail = temp;
} else {
temp.next = head;
tail.next = temp;
tail = temp;
}
size++;
}

//dequeue
public T dequeue(T item) {
Node temp = head;
head = head.next;
tail.next = head;
size--;
return (T) temp.item;
}
//size
public int size() {
if (size == 0) {
}
return size;
}
//peek
public T peek() {
return (T) head.item;
//return item
}
//isEmpty
public boolean isEmpty() {
return (size == 0);
}
//print in queue class
public void print() {
if(head != null) {
Node curr = head;
System.out.println(curr.item);
curr = curr.next;
while (curr != head) {
System.out.println(curr.item);
curr = curr.next;
}
}
}

//Deletes every nth node until only one node remains
public void delete(int num, Queue q) {
Node head = q.head;
Node tail = q.tail;
int count;
Node temp = tail;
int length = q.size;
while((head != tail) && length > 1){
count = 1;
while(count != num){
temp = temp.next;
count++;
}
System.out.println("Deleting " + temp.next.item);
temp.next = temp.next.next;
length--;
}
q.head = temp;
q.tail = temp;
q.size = length;
}
}

Answer 1

file-name:   Node.java
----------------------------
class Node<T> {
    //Node makes item, next, and prev all private
//and therefore has to provide accessors
//and mutators (gets and sets)
    private T item;
    private Node next;
    private Node prev;

    Node(T newItem) {
        item = newItem;
        next = null;
        prev = null;
    }
    Node(T newItem, Node nextNode, Node prevNode) {
        item = newItem;
        next = nextNode;
        prev = prevNode;
    }

    /**
     * @return the item
     */
    public T getItem() {
        return item;
    }
    /**
     * @param item the item to set
     */
    public void setItem(T item) {
        this.item = item;
    }

    /**
     * @return the next
     */
    public Node getNext() {
        return next;
    }

    /**
     * @param next the next to set
     */
    public void setNext(Node next) {
        this.next = next;
    }

    /**
     * @return the prev
     */
    public Node getPrev() {
        return prev;
    }

    /**
     * @param prev the prev to set
     */
    public void setPrev(Node prev) {
        this.prev = prev;
    }
} // END of class Node

=============================================

file-name:     Queue.java
------------------------------
class Queue<T> {

    private Node head, tail = null;
    int size = 0;
    public Queue() {
        head = tail = null;
        size = 0;
    }
    //enqueue
    public void enqueue(T item) {
        Node temp = new Node(item);
        if (head == null) {
            head = temp;
            tail = temp;
        } else {
            temp.setNext(head);
            tail.setNext(temp);
            tail = temp;
        }
        size++;
    }

    //dequeue
    public T dequeue(T item) {
        Node temp = head;
        head = head.getNext();
        tail.setNext(head);
        size--;
        return (T) temp.getItem();
    }
    //size
    public int size() {
        if (size == 0) {
        }
        return size;
    }
    //peek
    public T peek() {
        return (T) head.getItem();
//return item
    }
    //isEmpty
    public boolean isEmpty() {
        return (size == 0);
    }
    //print in queue class
    public void print() {
        if(head != null) {
            Node curr = head;
            System.out.println(curr.getItem());
            curr = curr.getNext();
            while (curr != head) {
                System.out.println(curr.getItem());
                curr = curr.getNext();
            }
        }
    }

    //Deletes every nth node until only one node remains
    public void delete(int num, Queue q) {
        Node head = q.head;
        Node tail = q.tail;
        int count;
        Node temp = tail;
        int length = q.size;
        while((head != tail) && length > 1){
            count = 1;
            while(count != num){
                temp = temp.getNext();
                count++;
            }
            System.out.println("Deleting " + temp.getNext().getItem());
            temp.setNext(temp.getNext().getNext());
            length--;
        }
        q.head = temp;
        q.tail = temp;
        q.size = length;
    } // END of delete
} // END of class Queue

================================================

file-name:  Main.java
-----------------------------

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) {

        // creating Queue object
        Queue<String> q = new Queue<>();

        BufferedReader br;
        try {
            FileReader file = new FileReader("/home/rahul/Pictures/words.txt");
            br = new BufferedReader(file);
            String line = br.readLine();
            while(line != null) {
                q.enqueue(line);
                line = br.readLine();
            }
        } // END of try
        catch (FileNotFoundException e) {
            System.out.println("No file with this name");
        } catch (IOException e) {
            e.printStackTrace();
        } // END of catch

        // printing all the names in the queue.
        q.print();
        System.out.println("\n===============================\n");
        // deleting every 5th member in the queue.
        q.delete(5,q);
        // printing the members in the queue after deleting
        System.out.println("\n================================\n");
        q.print();
    } // main( ) method ended
}// END of Main class

-----------------------------------------------------------------------------------------------

OUTPUT:

THANK YOU !! If you have any doubts please ask in comment section. I will modify the answer accordingly. Please UPVOTE if you like my effort and answer.