Java - Rail Road Car Rearrangement Using List (FIFO)
Here the source code in Java for rearranging rail road car using Queue - LinkedList (First In First Out)
The other related links are,
Turbo C++ - Applying Queue Technique for Rail Road Car Rearrangement
Visual C++ - Applying Queue Technique for Rail Road Car Rearrangement
Algorithm:
- Construct three queues (FIFO) Namely Track 1, Track 2, Track 3
- Input the all the cars into Track 1.
- Move the first car from Track 1 and Track 3.
- Compare the cars from Track 1 and Track 3. If there are no cars in Track 1, then go to step 7.
- If track 3 holds the least value, then move the car from Track 1 to Track 2. Here Track 3 holds the least value again. Go to Step 4.
- If track 3 holds the higher value, then move the car from Track 3 to Track 2 and Move the car from Track 1 to Track 3. Now Track3 holds the least value. Go to Step 4.
- Now if it first pass, there will be one car which is least among the queue would be in Track 3 and the Track 1 would be empty and the track 2 would have other cars. If it is second pass, there will be two cars which are least among the queue would be in Track 3 and Track 1 would be empty and the track 2 would have other cars. And so on.
- Move all the cars one by one from Track 2 Queue to Track 1 Queue - This step can be avoided but the algorithm needs to be changed so that Track 1 behaves like Track 2 and Track 2 behaves like Track 1 on Step 4, 5, 6.
- Go to Step 4 until Track 1 is empty.
- You will notice all the cars are moved on to Track 3 in the correct order.
Source Code
import java.io.*;
import java.util.*;
import java.lang.*;
class RailRoadCar {
public static LinkedList Rearrange(LinkedList list)
{
System.out.println("Rearranging Cars...");
LinkedList track1 = new LinkedList();
LinkedList track2 = new LinkedList();
LinkedList track3 = new LinkedList();
LinkedList Output = new LinkedList();
track1 = list;
while (true)
{
int len1 = track1.size();
if (len1 == 0)
break;
for (int i = 0; i < len1; i++)
{
if (i == 0)
{
track3.add(track1.element());
track1.remove();
}
else
{
int lvalue = Integer.parseInt(track3.element().toString());
int rvalue = Integer.parseInt(track1.element().toString());
if (lvalue < rvalue)
{
track2.add(track3.element());
track3.remove();
track3.add(track1.element());
track1.remove();
}
else
{
track2.add(track1.element());
track1.remove();
}
}
}
int len2 = track2.size();
for (int j = 0; j < len2; j++)
{
track1.add(track2.element());
track2.remove();
}
Output.add(track3.element());
track3.remove();
System.out.print(track1.toString());
System.out.print(" , ");
System.out.print(track2.toString());
System.out.print(" , ");
System.out.print(track3.toString());
System.out.print(" , ");
System.out.println(Output.toString());
}
return Output;
}
public static void main(String[] args) {
String inpstring = "";
InputStreamReader input = new InputStreamReader(System.in);
BufferedReader reader = new BufferedReader(input);
LinkedList q = new LinkedList();
try
{
System.out.println("Input: ");
inpstring = reader.readLine();
int i = 0;
for (i = 0; i < inpstring.length(); i++)
{
Object o = inpstring.charAt(i);
boolean bRet = q.add(o);
}
}
catch (Exception e)
{
e.printStackTrace();
}
LinkedList result = Rearrange(q);
System.out.println(result.toString());
}
}
Output
Input: 8273645190
Rearranging Cars...
[2, 7, 3, 6, 4, 5, 1, 8, 0] , [] , [] , [9]
[2, 3, 6, 4, 5, 1, 7, 0] , [] , [] , [9, 8]
[2, 3, 4, 5, 1, 6, 0] , [] , [] , [9, 8, 7]
[2, 3, 4, 1, 5, 0] , [] , [] , [9, 8, 7, 6]
[2, 3, 1, 4, 0] , [] , [] , [9, 8, 7, 6, 5]
[2, 1, 3, 0] , [] , [] , [9, 8, 7, 6, 5, 4]
[1, 2, 0] , [] , [] , [9, 8, 7, 6, 5, 4, 3]
[1, 0] , [] , [] , [9, 8, 7, 6, 5, 4, 3, 2]
[0] , [] , [] , [9, 8, 7, 6, 5, 4, 3, 2, 1]
[] , [] , [] , [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
|
|