We want to sort an array of $N$ integers in decreasing order using a stack. To do this, you should use two stacks: a current stack ($\texttt{$S_1$}$) and an auxiliary stack ($\texttt{$S_2$}$) that will be used temporarily for eventual pops. 

Write a C program that resolves this problem.

Running Example: Let $tab$ be the following array:

$\begin{array}{|c|c|c|c|c|c|}\hline5 & 0 & 2 & 1 & 7 & 1 \\ \hline\end{array}$

Execution trace:

$\begin{array}{c | c | c }
\texttt{Before manipulating 5}  & \texttt{While manipulating 5} &  \texttt{After manipulating 5} \\ 
\begin{array}{p{2cm} p{2cm} } \begin{array}{|c|}\\  \\  \\  \\  \ \\  \\ \hline \end{array} &   \begin{array}{|c|} \\ \  \\ \\ \\ \\ \\ \hline \end{array} \\ S_1 &   S_2 \end{array}             &
\begin{array}{p{2cm} p{2cm} } \begin{array}{|c|}\\  \\  \\  \\  \\  \\ \hline \end{array} &   \begin{array}{|c|} \\ \  \\ \\  \ \\ \\ \\ \hline \end{array} \\ S_1 &   S_2 \end{array}           &
\begin{array}{p{2cm} p{2cm} } \begin{array}{|c|} \\ \\ \\ \\ \\ 5 \\ \hline \end{array} &  \begin{array}{|c|} \\ \\ \\ \ \\ \\   \\ \hline \end{array} \\ S_1 &   S_2 \end{array}
\end{array}$ 

$\begin{array}{c | c | c }
\texttt{Before manipulating 0}  & \texttt{While manipulating 0} &  \texttt{After manipulating 0} \\ 
\begin{array}{p{2cm} p{2cm} } \begin{array}{|c|}\\  \\  \\  \\  \ \\  5 \\ \hline \end{array} &   \begin{array}{|c|} \\ \  \\ \\ \\ \\ \\ \hline \end{array} \\ S_1 &   S_2 \end{array}             &
\begin{array}{p{2cm} p{2cm} } \begin{array}{|c|}\\  \\  \\  \\  \\  \\ \hline \end{array} &   \begin{array}{|c|} \\ \  \\ \\  \ \\ \\ 5 \\ \hline \end{array} \\ S_1 &   S_2 \end{array}           &
\begin{array}{p{2cm} p{2cm} } \begin{array}{|c|} \\ \\ \\ \\ 5 \\ 0 \\ \hline \end{array} &  \begin{array}{|c|} \\ \\ \\ \ \\ \\   \\ \hline \end{array} \\ S_1 &   S_2 \end{array}
\end{array}$ 

$\begin{array}{c | c | c }
\texttt{Before manipulating 2}  & \texttt{While manipulating 2} &  \texttt{After manipulating 2} \\ 
\begin{array}{p{2cm} p{2cm} } \begin{array}{|c|}\\  \\  \\  \\  5 \\  0 \\ \hline \end{array} &   \begin{array}{|c|} \\ \  \\ \\ \\ \\ \\ \hline \end{array} \\ S_1 &   S_2 \end{array}             &
\begin{array}{p{2cm} p{2cm} } \begin{array}{|c|}\\  \\  \\  \\  \\  0 \\ \hline \end{array} &   \begin{array}{|c|} \\ \  \\ \\  \ \\ \\ 5 \\ \hline \end{array} \\ S_1 &   S_2 \end{array}           &
\begin{array}{p{2cm} p{2cm} } \begin{array}{|c|} \\ \\ \\ 5 \\ 2 \\ 0 \\ \hline \end{array} &  \begin{array}{|c|} \\ \\ \\ \ \\ \\   \\ \hline \end{array} \\ S_1 &   S_2 \end{array}
\end{array}$ 

$\begin{array}{c | c | c }
\texttt{Before manipulating 1}  & \texttt{While manipulating 1} &  \texttt{After manipulating 1} \\ 
\begin{array}{p{2cm} p{2cm} } \begin{array}{|c|}\\  \\  \\  5 \\  2  \\  0 \\ \hline \end{array} &   \begin{array}{|c|} \\ \  \\ \\ \\ \\ \\ \hline \end{array} \\ S_1 &   S_2 \end{array}             &
\begin{array}{p{2cm} p{2cm} } \begin{array}{|c|}\\  \\  \\  \\  \\  0 \\ \hline \end{array} &   \begin{array}{|c|} \\ \  \\ \\  \ \\ 2 \\ 5 \\ \hline \end{array} \\ S_1 &   S_2 \end{array}           &
\begin{array}{p{2cm} p{2cm} } \begin{array}{|c|} \\ \\ 5 \\ 2 \\ 1 \\ 0 \\ \hline \end{array} &  \begin{array}{|c|} \\ \\ \\ \ \\ \\   \\ \hline \end{array} \\ S_1 &   S_2 \end{array}
\end{array}$ 

$\begin{array}{c | c | c }
\texttt{Before manipulating 7}  & \texttt{While manipulating 7} &  \texttt{After manipulating 7} \\ 
\begin{array}{p{2cm} p{2cm} } \begin{array}{|c|}\\  \\  5 \\  2 \\  1  \\  0 \\ \hline \end{array} &   \begin{array}{|c|} \\ \  \\ \\ \\ \\ \\ \hline \end{array} \\ S_1 &   S_2 \end{array}             &
\begin{array}{p{2cm} p{2cm} } \begin{array}{|c|}\\  \\ 5  \\ 2  \\  1 \\  0 \\ \hline \end{array} &   \begin{array}{|c|} \\ \  \\ \\  \ \\   \\   \\ \hline \end{array} \\ S_1 &   S_2 \end{array}           &
\begin{array}{p{2cm} p{2cm} } \begin{array}{|c|} \\ 7 \\ 5 \\ 2 \\ 1 \\ 0 \\ \hline \end{array} &  \begin{array}{|c|} \\ \\ \\ \ \\ \\   \\ \hline \end{array} \\ S_1 &   S_2 \end{array}
\end{array}$ 

$\begin{array}{c | c | c }
\texttt{Before manipulating 1}  & \texttt{While manipulating 1} &  \texttt{After manipulating 1} \\ 
\begin{array}{p{2cm} p{2cm} } \begin{array}{|c|}\\  7\\  5 \\  2 \\  1  \\  0 \\ \hline \end{array} &   \begin{array}{|c|} \\ \  \\ \\ \\ \\ \\ \hline \end{array} \\ S_1 &   S_2 \end{array}             &
\begin{array}{p{2cm} p{2cm} } \begin{array}{|c|}\\  \\    \\    \\  1 \\  0 \\ \hline \end{array} &   \begin{array}{|c|} \\ \  \\ \\  2 \\  5 \\   7\\ \hline \end{array} \\ S_1 &   S_2 \end{array}           &
\begin{array}{p{2cm} p{2cm} } \begin{array}{|c|} 7 \\ 5 \\ 2 \\ 1 \\ 1 \\ 0 \\ \hline \end{array} &  \begin{array}{|c|} \\ \\ \\ \ \\ \\   \\ \hline \end{array} \\ S_1 &   S_2 \end{array}
\end{array}$ 

void sort(int tab[], int n)
{
	stack s1, s2; /* Principe : La pile s1 est utilisee pour empiler les tab[i] par ordre decroissant.
				 tab[i] ne peut donc etre empile dans s1 que s'il est <= sommet(s1) ou bien s1 est vide */
	int i, x;
	element e;
	s1=CreateStack();
	s2=CreateStack();
	for (i = 0; i<n; i++)
	{
		//printf("** Manipulating tab[%d]=%d\n", i, tab[i]);
		x = Top(s1, &e);
		if (isEmptyStack(s1) || (x && tab[i] > e)) /* tab[i] peut etre empile dans s1 */
		{
			Push(&s1,tab[i]);
			printf("push %d in S1\n", tab[i]);
		}
		else /* tab[i] ne peut etre empile dans s1; il faut lui trouver un emplacement
			 dans s1 en vidant les elements de s1 superieurs a tab[i] dans s2 provisoirement */
		{
			x = Top(s1, &e);
			while (!isEmptyStack(s1) && tab[i] < e)
			{
				x = Pop(&s1);
				printf("pop S1\n");
				Push(&s2, e);
				printf("push %d in S2\n", e);
				x = Top(s1, &e);
			}
			Push(&s1,tab[i]); /* Ca y est, tab[i] est a sa place dans s1 */
								  /* On remet donc les elements de s2 a leur place dans s1 */
			printf("push %d in S1\n", tab[i]);
			while (!isEmptyStack(s2))
			{
				x = Top(s2, &e);
				x = Pop(&s2);
				printf("pop S2\n");
				Push(&s1,e);
				printf("push %d in S1\n", e);
			}
		}
	}
	/* On vide la pile ordonnee decroissante s1 dans le tableau qui devient trie croissant */
	for (i = n-1; !isEmptyStack(s1); i--)
	{
		Top(s1, &tab[i]);
		Pop(&s1);
	}

}