0. Introduction. The Ballarat Airline Company (BAC) wants a simple program to process customer requests to fly from some origin city to some destination city: For each customer request, the program has to indicate whether a sequence of BAC flights exists from the origin city to the destination city, and, if such a sequence exists, the program prints it.
The following figure represents the routs that BAC flies (for simplicity cities on the figure are denoted by C1, C2, …, C9): See image.
Notice that not all BAC flights have return flights, for example there is a BAC flight from C1 to C2, but not a BAC flight from C2 to C1.
The algorithm for processing customer requests is described in the following section and uses stacks. You must “translate” the algorithm into C++, and create auxiliary C++ classes as specified below.
1. The Main Algorithm. Let us assume that we have a request to find a sequence of flights from X to Y. The request must be processed in the following way:
(i) Return the stack. If the stack is not empty it contains the sequence of flights from X to Y. If the stack is empty, such sequence does not exist.
2. classes Stack< T > and List< T > [4 marks each]. Create class templates Stack< T > and List< T >. You may need to make appropriate changes to the classes Stack and List discussed in the lectures. Class Stack< T > should contain a function with the following prototype
friend ostream& operator<<(ostream& stream, Stack< T* > &c);
that prints contents of the stack.
3. Class City [4 marks]. Create a class City, which has the following private instance variables:
The class also should contain constructor(s) and get and set functions for the instance variables.
There also should be a public function City* getNextUnvisitedCity() that returns a pointer to some “unvisited” city from the nextCities list, if there is any, otherwise returns NULL.
4. A function with the header
function Stack< City >* isPath(City * originCity, City * destinationCity)
that implements the Main Algorithm described in section 1.
5. main function, in which you create 9 cities according to the information given in the flight map (figure in section 0) and then process customer requests for three different pairs of cities (you can choose the pairs yourself). [