The Scratchemup Parking Garage contains a single lane that holds up to ten cars. Cars arrive at the south end of the garage and leave from the north end. If a customer arrives to pick up a car that is not the northernmost, all cars to the north of the car moved out, the car is driven out, and the other cars are restored in the same original order.

Write a program in C++ (parking.cc) that reads a group of input lines. Each line contains an A for arrival or a D for departure, which is terminated by a :, and a license plate number, which is terminated by a :. The program should print a message each time a car arrives or departs. When a car arrives, the message should specify when the garage is full. If there is no room for a car, the car simply leaves. When a car departs, the message should include the number of times the car was moved within the garage, including the departure itself but not the arrival.

For a departure, you need to check if the car is in the garage. If its not, print an error message and ignore the departure. When a car arrives and if the garage is not full, create a C/C++ structure object for the car that contains the id number (starts with 1), the license plate number, and the number of times the car was moved within the garage (with initial value 0), and insert this structure object in a deque container. When a car departs, delete the corresponding structure object from the deque.

To save the original ordering of the cars that are moved out from the deque to open the way for a departing car, define a stack container to temporarily put the moved cars in the stack, and after the departing car, retrieve all cars from the stack back to the deque into their original positions.

Programming Notes:

• To keep all necessary information for a car, define the following structure:

typedef struct { int id; // id starts at 1 string lp; // license plate of car int no_mv; // number times the car has been moved }CAR; 

• In addition to the main() routine, implement the following subroutines in your program:

  • void get_input_vals(const string &line, char &act, string &lp) Extracts individual components from the input line line, where act indicates if the line corresponds to an arrival or a departure event, and lp is the license plate number of the arriving/departing car.
  • void arrival(const CAR &car, deque &D) Prints a message stating that a car is arrived. It gets the id number and the license plate number of the car from the car object, and in the message, species those values. If the garage is not full, inserts the car object in the deque D; otherwise, prints a message stating that the garage is full!.
  • void departure(const string &lp, deque &D, stack &S) Prints a message stating that the car with the license plate number lp is departed, and in that message specifies the number of times the car was moved within the garage. For every car moved from the deque D to the stack S and back to D, it updates the value no_mv in the CAR object of that car.

• The main() routine gets the input data from the stdin, line by line. For each input line, it calls the subroutine get_input_vals() to extract the character act, which indicates an arrival or departure, and the license plate number. If act is not the character A or D, prints an error message indicating the invalid action. For an arrival, it fills the individual components in a Car object and calls the function arrival() to process the arrival. For a departure, it calls the function departure() to process the departure.