Stacks: Railroad switching network (IN JAVA) A program is to be written to model
ID: 3661629 • Letter: S
Question
Stacks: Railroad switching network (IN JAVA)
A program is to be written to model a railroad switching yard. One part of the switching network consists of a main track and a siding that contains four exits onto which cars may be shunted and removed later. Railroad cars are numbered 1-7 on the right track(randomly arranged or entered by the user), they have to be moved to the left track (they have to be sorted in the left track), using the four exits. A car may be moved directly to the left track, or to one of the exits then to the left track. Use stacks to solve the problem.
Input
The order of the cars on the right track (random or by user)
Output
You should show a script showing the car number and the source and destination till the final solution is reached
Explanation / Answer
Good wishes,
I wrote two class
1. ArrayStack class which would help do stack operations on a stack implemented using arrays
2. RailroadSwitchingNetwork class which does all the needed work specified in the problem i.e. moving the cars on right track to left track either directly to left track or by using any one of the exits. finally the left track consists cars in order.
public class ArrayStack
{
public int[] a;
public int size,i,top,d;
public ArrayStack()
{
top=0;
i=0;
}
public ArrayStack(int s)
{
size=s;
top=0;
i=0;
a=new int[size];
}
public void push(int ele)
{
a[i]=ele;
top++;
}
public int pop()
{
d=top;
top--;
return a[d];
}
public boolean empty()
{
if(top==-1)
return true;
else
return false;
}
public int peek()
{
return a[top];
}
}
public class RailroadSwitchingNetwork
{
private static ArrayStack [] track; // array of holding tracks
private static int numberOfCars;
private static int numberOfTracks;
private static int smallestCar; // smallest car in any holding track
private static int itsTrack; // holding track with car smallestCar
public static boolean railroad(int [] inputOrder,
int theNumberOfCars, int theNumberOfTracks)
{
numberOfCars = theNumberOfCars;
numberOfTracks = theNumberOfTracks;
// create stacks track[1:numberOfTracks] for use as holding tracks
track = new ArrayStack [numberOfTracks + 1];
for (int i = 1; i <= numberOfTracks; i++)
track[i] = new ArrayStack();
int nextCarToOutput = 1;
smallestCar = numberOfCars + 1; // no car in holding tracks
// rearrange cars
for (int i = 1; i <= numberOfCars; i++)
if (inputOrder[i] == nextCarToOutput)
{// send car inputOrder[i] straight out
System.out.println("Move car " + inputOrder[i]
+ " from input track to output track");
nextCarToOutput++;
// output from holding tracks
while (smallestCar == nextCarToOutput)
{
outputFromHoldingTrack();
nextCarToOutput++;
}
}
else
// put car inputOrder[i] in a holding track
if (!putInHoldingTrack(inputOrder[i]))
return false;
return true;
}
private static void outputFromHoldingTrack()
{
// remove smallestCar from itsTrack
track[itsTrack].pop();
System.out.println("Move car " + smallestCar + " from holding "
+ "track " + itsTrack + " to output track");
// find new smallestCar and itsTrack by checking top of all stacks
smallestCar = numberOfCars + 2;
for (int i = 1; i <= numberOfTracks; i++)
if (!track[i].empty() &&
((Integer) track[i].peek()).intValue() < smallestCar)
{
smallestCar = ((Integer) track[i].peek()).intValue();
itsTrack = i;
}
}
private static boolean putInHoldingTrack(int c)
{
// find best holding track for car c
// initialize
int bestTrack = 0, // best track so far
bestTop = numberOfCars + 1; // top car in bestTrack
// scan tracks
for (int i = 1; i <= numberOfTracks; i++)
if (!track[i].empty())
{// track i not empty
int topCar = ((Integer) track[i].peek()).intValue();
if (c < topCar && topCar < bestTop)
{
// track i has smaller car at top
bestTop = topCar;
bestTrack = i;
}
}
else // track i empty
if (bestTrack == 0) bestTrack = i;
if (bestTrack == 0) return false; // no feasible track
// add c to bestTrack
track[bestTrack].push(new Integer(c));
System.out.println("Move car " + c + " from input track "
+ "to holding track " + bestTrack);
// update smallestCar and itsTrack if needed
if (c < smallestCar)
{
smallestCar = c;
itsTrack = bestTrack;
}
return true;
}
public static void main(String args[])
{
int [] rt=new int[7];
System.out.println("Please enter the cars(1-7) in the order you wish:");
Scanner in = new Scanner(System.in);
for(int i=0;i<7;i++)
{
rt[i]=in.nextInt();
}
boolean result=railroad(rt,7,2);
}
}
The push method in ArrayStack class is used to push elements into the stack.
The pop method in ArrayStack class is used to return the top element an dremove it from the stack
The peek method in ArrayStack class is used to return the top element in the stack
The empty method in ArrayStack class is used to return true if stack is empty else return false.
The outputFromHoldingTrack() method in class RailroadSwitchingNetwork is used to move a car from an exit to the left track
The putInHoldingTrack() method in class RailroadSwitchingNetwork is used to move car from right track to one of the exits.
The railroad() method in class RailroadSwitchingNetwork is used to take the input right track cars and all required data and then either move car from right track to left track directly or put it to one of the exits by calling putInHoldingTrack() method in class RailroadSwitchingNetwork and calls outputFromHoldingTrack() method in class RailroadSwitchingNetwork when a car is to be moved from exit to left track.
The main() method is used to take the cars in right track from the used according to his wish and then call railroad() method which carries on the reqired problem solving process.
During the process it develops a script showing the car number and the source and destination till the final solution is reached.
Hope this is clear.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.