The purpose of this question is to simulate the work done on the boarding desks of an airline company at the airport. Passengers wanting to leave on a flight, and after going through the check-in phase, must go through the boarding phase which gives them access to the plane. During the boarding phase, all passengers line up so that the agent validates their boarding passes. Passengers are served according to the FIFO structure.

Part A: Passengers include pregnant women and disabled passengers. In order not to keep these two types of people waiting, the company asks you to find a solution that gives them priority. On the other hand, the company does not want to create two queues but to put all the passengers in a single queue.

1. Define the \(\texttt{Passenger}\) type and the \(\texttt{Counter}\) structure representing all the passengers wanting to board the plane. Remember that passengers are not allowed to align in more than one queue.
2. Write the function \(\texttt{addPassager}\) which adds a passenger \(\texttt{p}\) having the type \(\texttt{t}\) (\(\texttt{t} = '\texttt{h}'\) for handicapped or pregnant, and \(\texttt{t} = '\texttt{a}'\) for others) to the list of passengers waiting in the queue for boarding. Without performing any calculations, give the worst case time complexity of your function. Justify your answer.
3. Write the function \(\texttt{servePassenger}\) that removes and returns a passenger from the list while respecting the FIFO structure and priorities. Without performing any calculations, give the worst case time complexity of your function. Justify your answer.
   
   

Part B: The same company wants to change the way passengers are served in order to give a little priority to passengers traveling in business class over passengers traveling in economy class.
In this case, the type of passenger becomes: \(\texttt{t = 'h'}\) for handicapped or pregnant, \(\texttt{t = 'b'}\) for business who are not disabled or pregnant and \(\texttt{t = 'a'}\) for others.
In this version, passengers of type \('\texttt{h}'\) are served before others. On the other hand, if no passenger of type \('\texttt{h}'\) can be found in the queue, the passengers are served in the following order: a passenger of type \('\texttt{b}'\) then a passenger of type \('\texttt{a}'\) and so on.
It must be taken into account that at any moment we can add a passenger to the list.
In this part, you are allowed to use more than one queue if you wish.

Rewrite questions 1., 2., and 3. of part A.

Part A
1.
typedef struct
{
	char p;
	char type;
} passenger;
typedef passenger element;
typedef struct 
{
	element data[M]; /* queue content */
	int front, rear;
} queue;
typedef queue Counter;

Solution 1
2.  complexity: O(1)
int addPassenger(Counter *counter, char p, char type)
{
	passenger pass = { p, type };
	if (isFullQueue(*counter))		return 0;
	EnQueue(counter, pass);
	return 1;
}

3. complexity: O(n) where n is the number of passengers in the queue
int servPassenger(Counter *counter, passenger *passtoserve)
{
	passenger pass,p;
	Counter aux = CreateQueue();
	int countA= 0, counth=0;
	if (isEmptyQueue(*counter))	return 0;

	while (Front(*counter, &pass))
	{
		DeQueue(counter);

		if (pass.type == 'a')
			EnQueue(&aux, pass);
		if (pass.type == 'h' && counth > 0)
			EnQueue(&aux, pass);
		if (pass.type == 'a' && countA == 0)
		{
			countA++;
			p = pass;
		}
		else if (pass.type == 'h' && counth == 0)
		{
			*passtoserve = pass;
			counth++;
		}
	}
	if (counth == 0)
	{
		Front(aux, &pass);
		*passtoserve = pass;
		DeQueue(&aux);
	}	

	while (Front(aux, &pass) && DeQueue(&aux) && EnQueue(counter, pass));
	return 1;
}
Solution 2
2.  complexity:  O(n) where n is the number of passengers in the queue
int addPassenger(Counter *counter, char p, char type)
{
	passenger pass = { p, type }, passenger;
	Counter aux=CreateQueue();
	int added=0;
	if (isFullQueue(*counter))
		return 0;
	// insert sorted
	while(Front(*counter, &passenger))
	{
		DeQueue(counter);
		if(added==0 && type=='h'  && passenger.type=='a' ) 
		{
			EnQueue(&aux,pass);
			added=1;
		}
		EnQueue(&aux,passenger);
	}

	while(Front(aux,&passenger)  && DeQueue(&aux) && 
		EnQueue(counter,passenger));

	if(added==0)
		EnQueue(counter,pass);

	return 1;
}

3. complexity: O(1)
int servPassenger(Counter *counter, passenger *passtoserve)
{

	if (isEmptyQueue(*counter))
		return 0;
	Front(*counter,passtoserve);
	DeQueue(counter);
	return 1;


}







Part B
1.
typedef struct
{
	char p;
	char type;
} passenger;
typedef passenger element;
typedef struct 
{
	element data[M]; /* queue content */
	int front, rear;
} queue;
typedef struct{
	queue typeH, typeB, typeA;
}Counter;

2.  complexity: O(1)
int addPassenger(Counter *counter, char p, char type)
{
	passenger pass = { p, type };

	if ((type=='a' && isFullQueue(counter->typeA)) ||
			(type=='b' && isFullQueue(counter->typeB)) ||
			(type=='h' && isFullQueue(counter->typeH)) 
	)
	return 0;

	if(type=='a') EnQueue(&(counter->typeA),pass);
	if(type=='b') EnQueue(&(counter->typeB),pass);
	if(type=='h') EnQueue(&(counter->typeH),pass);
	return 1;
}

3. complexity: O(1) 
int servPassenger(Counter *counter, passenger *passtoserve, char *last)
{
	passenger p;
	if (isEmptyQueue(counter->typeH) && isEmptyQueue(counter->typeB) 
		&& isEmptyQueue(counter->typeA))
		return 0;

	if(Front(counter->typeH, &p) && DeQueue(&(counter->typeH)))
    	{
        	*passtoserve = p;
        	*last='h';
    	}
	else if(((*last =='h' || *last=='a') 
			&& Front(counter->typeB, &p) && DeQueue(&(counter->typeB))) 
			|| ||  isEmptyQueue(counter->typeA) 
                && Front(counter->typeB, &e) &&
                DeQueue(&(counter->typeB)) )
	{		
		*passtoserve=p;
		*last='b';
	}
	else if(Front(counter->typeA, &p) && DeQueue(&(counter->typeA)))
	{	*passtoserve=p;
		*last='a';
	}
	return 1;
}