Consider a queue of tasks each having an identifier (integer) and a priority between 0 and \(N-1\) (\(N\) constant).
We want to transform the queue so that tasks of priority 0 are in front, followed by tasks of priority 1 ... finally, tasks of priority \(N-1\) are at the end of the queue. Tasks of same priority must be stored in reverse order of their arrival.

1. Give the corresponding declarations.
2. Write a function that converts such a queue so it can verify the above property. Use exclusively the operations
   of the ADT given in lectures.
3. Calculate the complexity of the preceding function.
   
   

The following queue :
\(
\begin{array}{c}
\hline
\\
\begin{array}{c}
Id\\
Pr\\
\end{array}
\begin{array}{|c|}
\hline
1\\ \hline
5\\
\hline
\end{array}
\begin{array}{|c|}
\hline
2\\ \hline
3\\
\hline
\end{array}
\begin{array}{|c|}
\hline
3\\ \hline
1\\
\hline
\end{array}
\begin{array}{|c|}
\hline
4\\ \hline
3\\
\hline
\end{array}
\begin{array}{|c|}
\hline
5\\ \hline
3\\
\hline
\end{array}
\begin{array}{|c|}
\hline
6\\ \hline
5\\
\hline
\end{array}
\begin{array}{|c|}
\hline
7\\ \hline
2\\
\hline
\end{array}
\begin{array}{|c|}
\hline
8\\ \hline
1\\
\hline
\end{array}
\\
\\
\hline
\end{array}
\
\\
\
\\
becomes
\
\\
\begin{array}{c}
\hline
\\
\begin{array}{|c|}
\hline
8\\ \hline
1\\
\hline
\end{array}
\begin{array}{|c|}
\hline
3\\ \hline
1\\
\hline
\end{array}
\begin{array}{|c|}
\hline
7\\ \hline
2\\
\hline
\end{array}
\begin{array}{|c|}
\hline
5\\ \hline
3\\
\hline
\end{array}
\begin{array}{|c|}
\hline
4\\ \hline
3\\
\hline
\end{array}
\begin{array}{|c|}
\hline
2\\ \hline
3\\
\hline
\end{array}
\begin{array}{|c|}
\hline
6\\ \hline
5\\
\hline
\end{array}
\begin{array}{|c|}
\hline
1\\ \hline
5\\
\hline
\end{array}
\\
\\
\hline
\end{array}
\)

void sort(queue *q)
{
	element e;
	int i;
	stack s[M];
	for(i=0;i<M;i++)
		s[i]=CreateStack();

	while(Front(*q,&e))
	{
		DeQueue(q);
		Push(&s[e.priority],e);
	}

	for(i=0;i<M;i++)
	{
		while(Top(s[i],&e))
		{
			Pop(&s[i]);
			EnQueue(q,e);
		}
	}
}