In a shopping mall, the parking garage contains a single lane that holds up to 50 vehicles. However, first 10 locations are dedicated to some customers. For the remaining parking places, there is only a single entrance/exit to the garage. If a customer arrives to pick up a vehicle and it is not nearest the exit, all vehicles blocking its path are moved out. The customers vehicle is driven out and the other vehicles are restored in the same order as they were in original.

a) Write a C++ program for this problem. Design a simple menu driven interface that lets the user specify

1) Total number of cars currently in the garage

2) Choose the location (number) of the car to exit

3) The interface should tell the steps required to remove the specified car from garage and the final position of all cars.

Provide only the functions that will be needed by your implementation.

b) What data structure(s) do you think is appropriate for the task? Explain the reason (in 3-4 lines) for your choice.

c) Show the working of your program using some sample parking configurations.

d) List the time complexity of each function.