Josephus Problem using Queue

//Josephus.java
//Out of  n members, every m'th person will be eliminated
import java.io.*;

//Stack---------------
class Node<T> {
    T value;
    Node<T> link;
}

class Stack<T> {
    Node<T> top;
    public Stack() {
        top = null;
    }
    public void push(T item) {
        Node<T> n = new Node<T>();
        n.value = item;
        n.link = top;
        top = n;
    }
    public T pop() {
        T item;
        item = top.value;
        Node<T> n = top;
        n = null;
        top = top.link;
        return item;
    }
    public void display() {
        Node<T> n = top;
        System.out.print("(top)");
        while (n != null) {
            System.out.print(" ->" + n.value);
            n = n.link;
        }
        System.out.println();
    }
}

// Queue---------------------------
class Queue<T> {
    Node<T> front, rear;
    Stack<T> s1 = new Stack<T>();
    Stack<T> s2 = new Stack<T>();
    public Queue() {
    }
    public void add(T item) {
        while (s2.top != null)
            s1.push(s2.pop());
        s1.push(item);
        rear = s1.top;
        while (s1.top != null)
            s2.push(s1.pop());
        front = s2.top;
    }
    public T remove() {
        T item = s2.pop();
        front = s2.top;
        return item;
    }
    public void display() {
        Node<T> n = s2.top;
        System.out.print("(front)");
        while (n != null) {
            System.out.print(" <-" + n.value);
            n = n.link;
        }
        System.out.println(" <-(rear)");
    }
}

// Josephus Problem-------------------
public class Josephus {
    public static void main(String[] args) throws IOException {
        Queue<Integer> q = new Queue<Integer>();
        Queue<Integer> q1 = new Queue<Integer>();
        int n, m, i;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        System.out.println("Enter no. of members (n) : ");
        n = Integer.parseInt(br.readLine());
        System.out.println("Enter the elimination number (m) : ");
        m = Integer.parseInt(br.readLine());
        for (i = 1; i <= n; i++)
            q.add(i);
        Node<Integer> node = q.front;
        int l, k = 0;
        while (k != n - 1) {
            for (i = 1; i < m; i++)
                q.add(q.remove());
            l = q.remove();
            q1.add(l);
            k++;
        }
        System.out.println("Order of elimination is : ");
        while (q1.front != null)
            System.out.print(q1.remove() + ",");
        System.out.println("nWinner is : " + q.remove());
    }
}

0 comments:

Post a Comment

Popular Labels

Featured Post (TOP)

Flickr Images

Follow Me on Facebook.com

Follow on Google+

Recent Posts

AD (728x60)

Pages

Powered by Blogger.

Labels

Followers

Popular Posts

Popular Posts

Subscribe Via Email

Sign up for our newsletter, and well send you news and tutorials on web design, coding, business, and more! You'll also receive these great gifts: